XOR 교체 알고리즘

보통 swap를 생각하면 다음과 같이 정의하곤 한다.

1. algorithm 헤더를 이용한 swap

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include <iostream> #include <algorithm>   using namespace std;   int main() {     int a, b;     cin >> a >> b;       cout << "swap 전 a :: " << a << " b :: " << b << endl;       swap(a, b);       cout << "swap 후 a :: " << a << " b :: " << b << endl;       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

2. 임시 변수를 이용한 swap

#include <iostream>
 
#define swap(a, b){int tmp = a; a = b; b = tmp;}
 
using namespace std;
 
int main()
{
    int a, b;
    cin >> a >> b;
 
    cout << "swap 전 a :: " << a << " b :: " << b << endl;
 
    swap(a, b);
 
    cout << "swap 후 a :: " << a << " b :: " << b << endl;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

이번에는 이러한 메모리 낭비를 없애는 XOR의 성질을 이용한 swap를 해보고자 한다.

우선 XOR의 성질에 대해 알아보자.

1 - 교환 법칙 :: A ^ B = B ^ A

2 - 결합 법칙 :: (A ^ B) ^ C = A ^ (B ^ C)

3 - 항등원의 존재 :: 어떤 A에 대해서도, A ^ Z = A가 되는 값 Z = 0이 존재한다.

4 - 각 원소에 대해 유일한 역원의 존재 :: 각 A에 대하여  가 되는 이 존재한다.

이제 a와 b를 xor을 이용하여 swap을 해보자.

과정	의사 코드	A 값	B 값	사용된 XOR 성질
1	초기 상태	A	B	-
2	A = A ^ B	A ^ B	B	-
3	B = B ^ A	A ^ B = B ^ A	B = B ^ (B ^ A) = 0 ^ A = A	L1, L2, L4, L3
4	A = A ^ B	B ^ (A ^ A) = B	A	L2, L3, L4

따라서 A와 B가 서로 XOR 교체 알고리즘에 의해 스왑을 이룰 수 있다.

3. XOR 교체 알고리즘을 이용한 swap

#include <iostream>
 
#define swap(a, b){a = a ^ b; b = b ^ a; a = a ^ b;}
 
using namespace std;
 
int main()
{
    int a, b;
    cin >> a >> b;
 
    cout << "swap 전 a :: " << a << " b :: " << b << endl;
 
    swap(a, b);
 
    cout << "swap 후 a :: " << a << " b :: " << b << endl;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

XOR 교체 알고리즘의 장단점

XOR 교체 알고리즘은 대부분의 현대적인 프로세서에서는 임시 변수를 사용하는 방법보다 더 느린데, 그 이유 중 하나로는 임시 변수를 사용하는 방법은 여러 명령어를 동시에 실행할 수 있도록 (명령어 수준 병렬성) 최적화하기가 더 쉽기 때문이다. XOR 교체 알고리즘은 3 연산 모두 데이터 의존성 (Read-After-Write)을 만들기에 반드시 순서대로만 실행해야한다. 따라서 현대 비순차 프로세서나 VLIW 컴파일러가 XOR 교체 알고리즘을 최적화할 수 있는 방법은 거의 없다.

반면, XOR 교체 알고리즘은 속도가 그리 빠르지 않아도 되고 메모리 (혹은 캐시) 사용을 최소화해야 하는 환경에서는 유용하게 사용될 수 있다. 따라서 이 방식은 임베디드 개발 환경에서 많이 이용된다.

출처 :: https://ko.wikipedia.org/wiki/XOR_%EA%B5%90%EC%B2%B4_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98