XOR 교체 알고리즘
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8f/XOR_Swap.svg/220px-XOR_Swap.svg.png)
XOR 교체 알고리즘(XOR swap algorithm) 또는 XOR 스왑 알고리즘은 임시 변수를 두지 않고, 두 개의 변수를 배타적 논리합(XOR) 비트 연산을 이용하여 교체(swap)하는 알고리즘이다. 이 알고리즘은 컴퓨터 프로그래밍 분야에서 프로세서의 최적화 능력이 부족했을 때 대안으로 자주 사용되었다.
개요
XOR 교체 알고리즘은 세 개의 XOR 연산을 사용하여 임시 변수 없이 두 변수를 교환한다. 의사코드로는 다음과 같이 표현할 수 있다.
X ← X XOR Y Y ← X XOR Y X ← X XOR Y
보통 위의 세 줄은 각각 하나씩 세 개의 기계어 명령에 대응될 수 있다. 예를 들어 IBM System/370에서 위 코드는 다음과 같은 어셈블리 코드로 변환된다:
XR R1,R2 XR R2,R1 XR R1,R2
여기서 R1과 R2는 레지스터이고 XR은 첫째 레지스터와 둘째 레지스터의 값을 XOR해서 그 결과값을 첫째 레지스터에 저장하는 명령이다.
하지만 이 알고리즘은 X와 Y가 같은 기억 장소를 가리킬 경우 제대로 동작하지 않는다. 예상했던 대로라면 두 값이 같으므로 아무 일도 일어 나지 않아야 하지만, 위 알고리즘은 첫 문장에서 X와 Y를 모두 0으로 초기화해 버리기 때문에 기억 장소에는 0이 저장된다. 만약 위의 알고리즘을 임의의 경우에도 쓸 수 있게 하려면 다음과 같은 수정이 필요하다.
만약 X ≠ Y이면, 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 |
코드 예제
다음은 XOR 교체 알고리즘을 구현한 C 코드이다.
void swap(int *x, int *y) { if (x != y) { *x ^= *y; *y ^= *x; *x ^= *y; } }
이 코드는 두 포인터가 서로 다른 메모리 공간을 가리킬 때에만 교체 연산을 수행해서 문제를 제거한다.
이 코드는 종종 다음과 같은 형태로 쓰이기도 한다.
if (x != y) *x ^= *y ^= *x ^= *y;
하지만 이 코드는 시퀀스 포인트의 부재 때문에 올바른 C 코드가 아니며, 이 코드의 수행 결과는 컴파일러에 따라 다를 수 있다.
실제 사용에서의 장단점
XOR 교체 알고리즘은 대부분의 현대적인 프로세서에서는 임시 변수를 사용하는 방법보다 더 느린데, 그 이유 중 하나로는 임시 변수를 사용하는 방법은 여러 명령어를 동시에 실행할 수 있도록 (명령어 수준 병렬성) 최적화하기가 더 쉽기 때문이다. XOR 교체 알고리즘은 3 연산 모두 데이터 의존성 (Read-After-Write)을 만들기에 반드시 순서대로만 실행해야한다. 따라서 현대 비순차 프로세서나 VLIW 컴파일러가 XOR 교체 알고리즘을 최적화할 수 있는 방법은 거의 없다.
반면, XOR 교체 알고리즘은 속도가 그리 빠르지 않아도 되고 메모리 (혹은 캐시) 사용을 최소화해야 하는 환경에서는 유용하게 사용될 수 있다. 따라서 이 방식은 임베디드 개발 환경에서 많이 이용된다.
같이 보기
외부 링크
- 두 변수 값 바꾸기에 대한 고찰 Archived 2007년 7월 20일 - 웨이백 머신
- swap