XOR 스왑 알고리즘

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

XOR 스왑 알고리즘은 임시 변수를 두지 않고, 두 개의 변수를 XOR 빗와이즈 오퍼레이션(bitwise operation)을 이용하여 스왑하는 알고리즘이다. 컴퓨터 프로그래밍 분야에서 나온 말이다.

목차

[편집] 알고리즘

보통의 스왑 알고리즘은 임시 변수를 이용한다. 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 명령이다. XR 명령은 그 첫번째와 두번째 오퍼레이터를 XOR해서 그 결과값을 첫번째 레지스터에 저장한다.

만약, XY가 같은 기억장소일 때는 문제가 된다. 처음 XOR 동작에서 0값이 나오니까, 그 기억장소에는 결국 0값이 저장된다; "스스로 스왑"은 불가능하다.

[편집] 증명

비트 스트링에 대한 XOR 이항 연산은 다음과 같은 성질을 갖는다 (\otimes는 XOR을 뜻한다):

  • L1. 교환 법칙: A \otimes B = B \otimes A
  • L2. 결합 법칙: (A \otimes B) \otimes C = A \otimes (B \otimes C)
  • L3. 항등원 존재: 어떤 A에 대하여서도, A \otimes Z = A가 되는 값 Z = 0이 존재한다.
  • L4. 각 엘레먼트는 한 개의 역원을 갖는다: 각 A에 대하여, A \otimes A^{-\!1} = Z가 되는 A^{-\!1}가 존재한다.
    • L4a. 사실, 각 엘레먼트는 그 엘레먼트에 대한 역원이다: A \otimes A = 0.

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

R1R2라는 두 개의 레지스터가 있다고 가정하자. 아래 테이블을 보라. 각각 처음에는 값 AB를 갖는다. 아래와 같이 순서대로 오퍼레이션을 수행하고, 상기 성질 L1-L4을 이용하여 그 결과를 정리하면 다음과 같다.

Step Operation Register 1 Register 2 Reduction
1 Initial value A B --
2 R1 := R1 ^ R2 A^B B --
3 R2 := R1 ^ R2 A^B = B^A (A^B)^B = A^(B^B) = A^0 = A L1, L2, L4, L3
4 R1 := R1 ^ R2 (B^A)^A = B^(A^A) = B^0 = B A L2, L3, L4

[편집] 코드 예제

[편집] 실제로 잘 사용하는 이유

[편집] 실제로 잘 사용하지 않는 이유

[편집] 변종

[편집] 함께 보기

이 문서는 전산학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.