Xor (Exclusive-OR) Swap

swap함수를 XOR연산을 통한 비트연산으로 구현할 수 있다.

void swap_pointer() 함수는 전형적으로 사용하는 swap함수이다.
구현하기 쉽고, 결과값에 확신을 가지기 때문에, STL의 swap 함수 만큼이나 많이 쓰는 함수이기도 하다.
그렇지만, 이 함수는 temp 영역 만큼의 추가 공간이 필요한 점 등이 단점이기도 하다.

void swap_xor() 함수는 오늘 소개할 swap 함수이다.
디지털 논리회로 시간에 배웠던 비트 XOR 연산으로 구현되어 있다.
상당히 빠른 속도로 동작하고, 추가 공간을 필요로 하지 않다.

코드는 다음과 같다.

#include <stdio.h>

#pragma warning(disable:4996)

void swap_pointer(int *x, int *y);
void swap_xor(int *x, int *y);

int main() {
    int x = 2, y = 9;
    fprintf(stdout, "init= x: %d, y: %d\n\n", x, y);
    swap_pointer(&x, &y);
    fprintf(stdout, "swap_pointer= x: %d, y: %d\n", x, y);
    swap_xor(&x, &y);
    fprintf(stdout, "swap_xor= x: %d, y: %d\n", x, y);
    return 0;
}

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

void swap_xor(int *x, int *y) {
    *x ^= *y;
    *y ^= *x;
    *x ^= *y;
}

결과는 다음과 같다.

이 함수의 로직은 다음과 같다.
int x = 2, y = 9;
비트로 표현하면,
x: 0000 0000 0000 0010
y: 0000 0000 0000 1001

*x ^= *y; 를 수행한다.
x: 0000 0000 0000 0010 (x = 2)
y: 0000 0000 0000 1001 (y = 9)
———————————-
(xor) 0000 0000 0000 1011 (x = 11)

*y ^= *x; 를 수행한다.
x: 0000 0000 0000 1011 (x = 11)
y: 0000 0000 0000 1001 (y = 9)
———————————
(xor) 0000 0000 0000 0010 (y = 2)

*x ^= *y; 를 수행한다.
x: 0000 0000 0000 1011 (x = 11)
y: 0000 0000 0000 0010 (y = 2)
———————————
(xor) 0000 0000 0000 1001 (x = 9)

이러한 연산을 거치게 되어 결과적으로 x와 y의 값이 swap되게 된다.
다만 이러한 로직은 부동소수점 연산에 대해서는 올바르게 작동하지 않는다.
(메모리상에서 비트가 구분되어져 있기 때문이다.)
결과적으로, int 형과 char형으로 특정짓기보다는, 각각의 동질한 메모리를 서로 교체해주는 연산이라고 보는 게 더 좋겠다.

*XOR(Exclusive OR) 연산과 OR연산은 다음과 같이 정의된다.
<OR 연산의 진리표>

OR   :  x = 0   x = 1

y = 0 :   0        1
y = 1 :   1        1

<XOR 연산의 진리표>

XOR  : x = 0  x = 1

y = 0  :    0      1
y = 1  :    1      0

댓글 남기기