XOR 교체 알고리즘

XOR 교체 알고리즘은 임시 변수를 사용하지 않고 비트연산을 통해 두 변수의 값을 교체하는 알고리즘이다.

과거 프로세서의 최적화 능력이 부족했을 때 대안으로 자주 사용되었다.

알고리즘은 아래와 같다.

X ← X XOR Y
Y ← X XOR Y
X ← X XOR Y

각 줄은 기계어 명령에 대응될 수 있다.

증명은 아래와 같다.

비트 문자열에 대한 XOR 이항 연산은 다음과 같은 성질을 갖는다. 여기서 는 XOR 연산자를 뜻한다.

• L1. 교환법칙: 
• L2. 결합법칙: 
• L3. 항등원의 존재: 어떤 에 대하여서도, 가 되는 값 이 존재한다.
• L4. 각 원소에 대해 유일한 역원의 존재: 각 에 대하여, 가 되는 가 존재한다.
  • L4a. 각 원소의 역원은 사실 자기 자신임: 

L1부터 L4까지의 성질은 아벨 군(ablian group)의 정의이다. L4a는 XOR 연산의 구조적 성질에 해당하는 것이며, 아벨 군이나 다른 군에 꼭 있는 성질은 아니다.

R1과 R2의 두 레지스터에 값 A와 B가 저장되어 있을 때, XOR 교체 알고리즘을 수행할 때 각각의 결과는 다음과 같다.

과정	수행된 명령	R1의 값	R2의 값	사용된 성질
1	(초기 상태)	A	B	--
2	R1 ← R1 XOR R2	A^B	B	--
3	R2 ← R1 XOR R2	A^B = B^A	(A^B)^B = A^(B^B) = A^0 = A	L1, L2, L4, L3
4	R1 ← R1 XOR R2	(B^A)^A = B^(A^A) = B^0 = B	A	L2, L3, L4

코드 예제는 아래와 같다.

void swap(int *x, int *y)
{
    if (x != y) {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}

또는

if (*x != *y) *x ^= *y ^= *x ^= *y;

> 다만, 아래 코드는 시퀀스 포인트의 부재로 컴파일러마다 결과가 다를 수 있다.

XOR 교체 알고리즘 이외에도 변수르 사용하지 않는 방법은 아래방법이 있다.

void swap(int *x, int *y)
{
    *x += *y;

*y = *x - *y;
*x -= *y;

}

일반적인 swap은 아래와 같다.

void swap(int *x, int *y)
{
    temp = *x;
*x = *y;
*y = temp;

}

결론

취향껏 쓰자.

참고

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