알고리즘 :: XOR 연산을 이용하여 스왑 알고리즘을 최적화하자.

한동훈 님의 「프로그래밍 스타일」이라는 글을 읽다가 스왑(Swap) 알고리즘에 대한 코드가 있어서 소개합니다. 아시는 분들도 많겠지만, 모르는 분들도 많을거라 생각되네요.

흔히 두 값을 맞바꿀 때 이런 알고리즘을 사용합니다.

int A = 5;
int B = 23;
int temp;

temp = A;
A = B;
B = temp;

변수 temp를 하나 더 선언해서 중간매개체로 사용하죠. 이 때문에 4byte의 메모리를 더 차지합니다. 하지만 아래에 소개할 알고리즘은 추가적인 메모리가 필요 없습니다.

int A = 5;
int B = 23;

A = A ^ B;
B = A ^ B;
A = A ^ B;

전 이 알고리즘을 처음 보고 와우! 하고 절로 탄성을 내질렀죠. 어쩔 수 없는 공돌인가 봅니다. ㅋ

혹시나 XOR 연산을 모르시는 분을 위해, XOR(A ^ B) 연산은 양 쪽의 값을 비트 단위로 비교하여 같으면 0을, 다르면 1을 반환하는 연산입니다. 0100 과 0001 이 있다고 하면, 첫 번째 비트인 0 과 0은 같으므로 0을, 두 번째 비트인 1 과 0은 다르므로 1을, 세 번째는 0을, 네 번째는 1을 반환하여 결과값으로 0101 이 나옵니다.

그럼 위 알고리즘이 메모리에서 어떻게 구현되는지 보겠습니다.

int A = 5;           00000101
int B = 23;         00010111

A = A ^ B;         (00000101) XOR (00010111) = 00010010
B = A ^ B;         (00010010) XOR (00010111) = 00000101
A = A ^ B;         (00000101) XOR (00010010) = 00010111

이런 과정을 거칩니다. 눈이 좀 어지럽지만, 자세히 보면 A와 B가 바뀐 것을 확인할 수 있습니다. 그리고 변수 temp를 이용한 알고리즘처럼 메모리를 별도로 더 차지하지 않습니다. 앞으로 이런 코드가 보이면 당황해 하지 마시고 스왑 알고리즘이구나 하세요.

하지만 한동훈 님은 이 알고리즘에도 문제가 있다고 합니다.

코드를 이해하기 어렵다.

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

뭐, 첫 번째 문제는 이런 글로 눈에 익히면 해결된다고 생각하는데, 두 번째 문제는 이해를 못하겠네요(죄송해요 ㅜㅜ). 누가 자세히 설명 좀 해주시면… OTL