왜 되냐고!
Table of Contents
들어가기 전에
•
이 글은 XOR Swap algorithm이 어떠한 과정으로 동작하는지 — 해당 코드가 어떻게 두 변수의 값을 교체하는지 — 에 대해 최대한 알기 쉽게 설명한다.
•
다른 Swap algorithm(임시 변수 사용 등)과의 성능 비교, 프로세서/컴파일러 수준의 최적화 과정, 실무에서 유용하게 사용할 수 있는지에 대한 의견 등에 대해서는 이 글에서 다루지 않는다.
무엇에 대한 이야기인가?
두 변수 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++
복사
각 코드 라인마다 x와 y의 값이 어떻게 변하는지 차근차근 알아보자.
설명의 편의를 위해, 변수 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 | - |