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해서 그 결과값을 첫번째 레지스터에 저장한다.
만약, X와 Y가 같은 기억장소일 때는 문제가 된다. 처음 XOR 동작에서 0값이 나오니까, 그 기억장소에는 결국 0값이 저장된다; "스스로 스왑"은 불가능하다.
[편집] 증명
비트 스트링에 대한 XOR 이항 연산은 다음과 같은 성질을 갖는다 (는 XOR을 뜻한다):
- L1. 교환 법칙:
- L2. 결합 법칙:
- L3. 항등원 존재: 어떤 A에 대하여서도,
가 되는 값 Z = 0이 존재한다.
- L4. 각 엘레먼트는 한 개의 역원을 갖는다: 각 A에 대하여,
가 되는
가 존재한다.
- L4a. 사실, 각 엘레먼트는 그 엘레먼트에 대한 역원이다:
.
- L4a. 사실, 각 엘레먼트는 그 엘레먼트에 대한 역원이다:
L1부터 L4까지의 성질은 아벨군(ablian group)의 정의이다. L4a는 XOR 의 구조적 성질에 해당하는 것이며, 아벨 군이나 다른 군에 꼭 있는 성질은 아니다.
R1
과 R2
라는 두 개의 레지스터가 있다고 가정하자. 아래 테이블을 보라. 각각 처음에는 값 A와 B를 갖는다. 아래와 같이 순서대로 오퍼레이션을 수행하고, 상기 성질 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 |
[편집] 코드 예제
[편집] 실제로 잘 사용하는 이유
[편집] 실제로 잘 사용하지 않는 이유
[편집] 변종
[편집] 함께 보기
![]() |
이 문서는 전산학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다. |