XOR 교체 알고리즘

위키백과, 우리 모두의 백과사전.

XOR 교체 알고리즘은 임시 변수를 두지 않고, 두 개의 변수를 배타적 논리합(XOR) 비트 연산을 이용하여 교체하는 알고리즘이다. 이 알고리즘은 컴퓨터 프로그래밍 분야에서 프로세서의 최적화 능력이 부족했을 때 대안으로 자주 사용되었다.

개요

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 교체 알고리즘은 속도가 그리 빠르지 않아도 되고 메모리 (혹은 캐시) 사용을 최소화해야 하는 환경에서는 유용하게 사용될 수 있다. 따라서 이 방식은 임베디드 개발 환경에서 많이 이용된다.

바깥 고리

원본 주소 "https://ko.wikipedia.org/w/index.php?title=XOR_교체_알고리즘&oldid=12240083"