Search
🤝

XOR 연산을 이용한 Swap algorithm, 이게 왜 됨?

Date
2022/08/04
Tags
Comp. Sci
Created by
왜 되냐고!
Table of Contents

들어가기 전에

이 글은 XOR Swap algorithm이 어떠한 과정으로 동작하는지 — 해당 코드가 어떻게 두 변수의 값을 교체하는지 — 에 대해 최대한 알기 쉽게 설명한다.
다른 Swap algorithm(임시 변수 사용 등)과의 성능 비교, 프로세서/컴파일러 수준의 최적화 과정, 실무에서 유용하게 사용할 수 있는지에 대한 의견 등에 대해서는 이 글에서 다루지 않는다.

무엇에 대한 이야기인가?

XOR 교체 알고리즘(XOR swap algorithm) 또는 XOR 스왑 알고리즘은 임시 변수를 두지 않고, 두 개의 변수를 배타적 논리합(XOR) 비트 연산을 이용하여 교체(swap)하는 알고리즘이다. — 위키백과
두 변수 x, y의 값을 서로 교체(swap)하려면 어떻게 해야 하는가? C++의 std::swap이나 Python의 x, y = y, x 문법을 사용할 것이 아니라면, 보통은 다음과 같이 임시 변수를 이용한 알고리즘을 사용할 것이다.
temp = x; x = y; y = temp;
C++
하지만, 임시 변수를 이용하지 않고도 두 변수의 값을 교체할 수 있는 방법이 있다. PS판에 조금 머물렀거나 주변에 tricky한 문법을 좋아하는 프로그래머가 있다면 한 번쯤은 구경해 보았으리라.
// Swap using bitwise XOR (Wrong Solution in C/C++) x ^= y ^= x ^= y; // Swap using bitwise XOR (Correct Solution in C/C++) // sequence point introduced using comma. (x ^= y), (y ^= x), (x ^= y);
C++
첫 줄의 코드는 UB(Undefined Behavior)를 포함하기 때문에 정확한 표현이라고 보기에는 어렵지만, 아무튼 저렇게 XOR 연산(+ 대입 연산)만을 이용해서 두 변수의 값을 교체할 수 있다.

왜 되는가?

결국 위에서 보았던 XOR을 이용한 코드는 다음과 같이 풀어쓸 수 있다.
x = x ^ y; // 0 y = x ^ y; // 1 x = x ^ y; // 2
C++
각 코드 라인마다 xy의 값이 어떻게 변하는지 차근차근 알아보자.
설명의 편의를 위해, 변수 x의 값을 A라 하고, 변수 y의 값을 B라 하자.
assert(x == A) assert(y == B)
C++

대략적인 설명

L0: x = x ^ y

1.
x == A ^ B가 성립한다.
assert(x == (A ^ B)) assert(y == B)
C++

L1: y = x ^ y

1.
y == (A ^ B) ^ B가 성립한다.
2.
y == A ^ (B ^ B)가 성립한다 (결합법칙).
3.
y == A ^ 0가 성립한다 (자기 자신과의 XOR 연산 결과는 0).
4.
y == A가 성립한다 (0과의 XOR 연산은 값의 변화가 없음).
assert(x == (A ^ B)) assert(y == A)
C++

L2: x = x ^ y

1.
x == (A ^ B) ^ A가 성립한다.
2.
x == (A ^ A) ^ B가 성립한다 (결합법칙, 교환법칙).
3.
x == 0 ^ B가 성립한다 (자기 자신과의 XOR 연산 결과는 0).
4.
x == B가 성립한다 (0과의 XOR 연산은 값의 변화가 없음).
assert(x == B) assert(y == A)
C++
결국 x의 값은 B, y의 값은 A가 되었다.

조금 더 Formal한 설명

XOR 연산의 정의와 몇 가지 성질들을 가지고, 각 단계에서 어떤 성질들에 의해 어떻게 값이 바뀌는지 다시 한번 보자.
XOR 연산의 정의는 다음과 같다.
x
y
x ^ y
0
0
0
0
1
1
1
0
1
1
1
0
다음과 같이 XOR 연산에서 성립하는 몇 가지 성질들이 있다.
L1. 교환법칙: A ^ B == B ^ A
L2. 결합법칙: (A ^ B) ^ C == A ^ (B ^ C)
L3. 0은 XOR의 항등원이다: A ^ 0 == A
L4. XOR의 역원은 자기 자신이다: A ^ A == 0
코드 라인
코드
x의 값
y의 값
사용된 성질
-
(초기 상태)
A
B
-
L0
x = x ^ y
A ^ B
B
-
L1
y = x ^ y
A ^ B
(A ^ B) ^ B = A ^ (B ^ B) = A ^ 0 = A
L1, L2, L4, L3
L2
x = x ^ y
(A ^ B) ^ A = A ^ (B ^ A) = A ^ (A ^ B) = (A ^ A) ^ B = 0 ^ B = B
A
L2, L3, L4
-
(결과)
B
A
-

References