XOR 교체 알고리즘 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:XOR Swap.svg|섬네일]]
'''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 [[이항 연산]]은 다음과 같은 성질을 갖는다. 여기서 <math>\otimes</math>는 XOR 연산자를 뜻한다.

* '''L1.''' [[교환법칙]]: <math>A \otimes B = B \otimes A</math>
* '''L2.''' [[결합법칙]]: <math>(A \otimes B) \otimes C = A \otimes (B \otimes C)</math>
* '''L3.''' [[항등원]]의 존재: 어떤 <math>A</math>에 대하여서도, <math>A \otimes Z = A</math>가 되는 값 <math>Z = 0</math>이 존재한다.
* '''L4.''' 각 원소에 대해 유일한 [[역원]]의 존재: 각 <math>A</math>에 대하여, <math>A \otimes A^{-\!1} = Z</math>가 되는 <math>A^{-\!1}</math>가 존재한다.
** '''L4a.''' 각 원소의 역원은 사실 자기 자신임: <math>A \otimes A = 0</math>

'''L1'''부터 '''L4'''까지의 성질은 [[아벨 군]](ablian group)의 정의이다. '''L4a'''는 XOR 연산의 구조적 성질에 해당하는 것이며, 아벨 군이나 다른 군에 꼭 있는 성질은 아니다.

<code>R1</code>과 <code>R2</code>의 두 레지스터에 값 ''A''와 ''B''가 저장되어 있을 때, XOR 교체 알고리즘을 수행할 때 각각의 결과는 다음과 같다.

{| class="wikitable"
|- 
! 과정
! 수행된 명령
! <code>R1</code>의 값
! <code>R2</code>의 값
! 사용된 성질
|-
| 1 || (초기 상태) || ''A'' || ''B'' || -- 
|-
| 2 || <code>R1 ← R1 XOR R2</code>  || ''A''^''B'' || ''B'' || -- 
|- 
| 3 || <code>R2 ← R1 XOR R2</code>  || ''A''^''B'' = ''B''^''A'' || (''A''^''B'')^''B'' = ''A''^(''B''^''B'') = ''A''^0 = ''A'' || L1, L2, L4, L3
|-
| 4 || <code>R1 ← R1 XOR R2</code>  || (''B''^''A'')^''A'' = ''B''^(''A''^''A'') = ''B''^0 = ''B'' || ''A'' || L2, L3, L4
|}

== 코드 예제 ==

다음은 XOR 교체 알고리즘을 구현한 [[C (프로그래밍 언어)|C]] 코드이다.
<syntaxhighlight lang="c">
void swap(int *x, int *y)
{
    if (x != y) {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}
</syntaxhighlight>

이 코드는 두 포인터가 서로 다른 메모리 공간을 가리킬 때에만 교체 연산을 수행해서 문제를 제거한다.

이 코드는 종종 다음과 같은 형태로 쓰이기도 한다.

<syntaxhighlight lang="c">if (x != y) *x ^= *y ^= *x ^= *y;</syntaxhighlight>

하지만 이 코드는 [[시퀀스 포인트]]의 부재 때문에 올바른 C 코드가 아니며, 이 코드의 수행 결과는 컴파일러에 따라 다를 수 있다.

== 실제 사용에서의 장단점 ==

XOR 교체 알고리즘은 대부분의 현대적인 프로세서에서는 임시 변수를 사용하는 방법보다 더 느린데, 그 이유 중 하나로는 임시 변수를 사용하는 방법은 여러 명령어를 동시에 실행할 수 있도록 (명령어 수준 병렬성) 최적화하기가 더 쉽기 때문이다. XOR 교체 알고리즘은 3 연산 모두 데이터 의존성 (Read-After-Write)을 만들기에 반드시 순서대로만 실행해야한다. 따라서 현대 비순차 프로세서나 VLIW 컴파일러가 XOR 교체 알고리즘을 최적화할 수 있는 방법은 거의 없다.

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

== 같이 보기 ==
* [[교체 연산]]

== 외부 링크 ==
* [http://minjang.egloos.com/1241820 두 변수 값 바꾸기에 대한 고찰] {{웹아카이브|url=https://web.archive.org/web/20070720003519/http://minjang.egloos.com/1241820}}
* [https://web.archive.org/web/20140330155228/http://talkera.org.cp-in-1.webhostbox.net/wp/?p=60 swap]


[[분류:알고리즘]]