I wannabe FALCON

지난 글에서 XOR 연산을 이용한 스왑 알고리즘을 소개했습니다. 그리고 이 알고리즘의 문제점에 대해서도 언급했는데, 그때는 제가 그 문제점을 이해하지 못해서 자세히는 못 다루었네요.

그때 소개한 문제점을 다시 보겠습니다.

코드를 이해하기 어렵다.

두 변수의 메모리 위치가 동일할 때 동작하지 않는다.

제가 이해하지 못한 것이 2번이었죠. 두 변수의 메모리 위치가 동일하다는 말은 의미 그대로입니다. 아래 예를 보겠습니다.

void Swap(int* data, int limit)
{
    int a = 0;
    int b = 0;
    
    for(i = a; a < limit; a++)
    {
        for(b = 0; b < limit; b++)
        {
            data[b] ^= data[a];
            data[a] ^= data[b];
            data[b] ^= data[a];
        }
    }
}

별 의미없는 함수입니다. 그러나 위에서 언급했던 메모리 위치가 동일하다는 조건을 이 이중반복문에서 쉽게 찾을 수 있습니다. 변수 a와 b가 조건을 만족하며 순환하고 있습니다. 그러다가 어느 순간 a와 b가 같은 값을 나타냅니다. 즉, a가 5일 때 b도 5가 될 수 있습니다. 이것은,

data[5] ^= data[5];
data[5] ^= data[5];
data[5] ^= data[5];

이렇게 적용됩니다. XOR 연산은 양쪽의 두 값을 비트 단위로 비교하여 같으면 0을, 다르면 1을 내보냅니다. 그러므로 위에서 data[5]에는 0이 저장됩니다. 두 값을 맞바꾼 게 아닌 0으로 만들어 버리는거죠.

이것이 XOR 스왑 알고리즘의 치명적인 문제점입니다. 하지만 간단하게 두 값이 같지 않다는 조건을 붙이면 해결할 수 있는 단순한 문제점이기도 합니다. 그런 의미에서 정렬 알고리즘에서 사용할 경우는 문제 없겠지요. 일단 '크다', '작다'라는 조건을 선행하니까요.

아, 그리고 XOR 연산 알고리즘을 사용한다고 임시 변수를 사용하는 알고리즘보다 속도가 빠른 것은 아니랍니다. 컴파일러마다 다르지만, gcc 기준으로는 동일하다네요. 단지, 변수에 의한 메모리를 더 차지하냐 아니냐의 차이입니다.

참고 문헌

XOR 교체 알고리즘 - 위키백과 :: http://ko.wikipedia.org/wiki/XOR_스왑_알고리즘

두 변수 값 바꾸기에 대한 고찰 :: http://minjang.egloos.com/1241820

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

6l4ck3y3 0x07 알고리즘 Programming, XOR, 교환, 스왑, 알고리즘