XOR: 컴퓨터 공학에서 가장 마법 같은 연산
컴퓨터 공학에는 수많은 논리 연산(AND, OR, NOT...)이 존재하지만, XOR(Exclusive OR, 배타적 논리합)만큼 독특하고 강력한 응용력을 가진 연산은 없습니다.
암호학(Cryptography), 데이터 복구(RAID), 그리고 그래픽 처리까지. 단순해 보이는 이 연산이 어떻게 "정보의 흔적"을 남기고 복원하는지 알아봅니다.
1. 정의: "다르면 1, 같으면 0"
XOR은 두 입력 비트가 서로 다를 때만 참(1)을 반환합니다.
수학기호로는 $\oplus$ (Circle Plus)를 사용하며, 프로그래밍 언어(C, Python, Java 등)에서는 ^ 기호를 사용합니다.
진리표 (Truth Table)
| 입력 A | 입력 B | 결과 ($A \oplus B$) | 설명 |
|---|---|---|---|
| 0 | 0 | 0 | 같음 |
| 0 | 1 | 1 | 다름 |
| 1 | 0 | 1 | 다름 |
| 1 | 1 | 0 | 같음 |
직관적 이해: * 비트의 덧셈 (올림수 버림): $1 + 1 = 2$이지만, 이진수 1비트 세상에서는
0이 됩니다. 즉, Carry-less Addition입니다. * 차이 검출기 (Difference Detector): 두 값이 차이가 나면 신호(1)를 줍니다.
2. XOR의 3가지 핵심 성질 (The Laws of XOR)
이 성질들이야말로 XOR을 마법처럼 만드는 수학적 기반입니다.
① 항등원 (Identity)
어떤 수에 0을 XOR 하면 원래의 수가 나옵니다.
$$A \oplus 0 = A$$
② 자기 소거 (Self-Inverse)
가장 중요한 성질입니다. 똑같은 수를 두 번 XOR 하면 0이 되어 사라집니다. $$A \oplus A = 0$$
③ 교환 및 결합 법칙 (Commutative & Associative)
순서를 바꿔도 결과는 같습니다. $$A \oplus B = B \oplus A$$ $$(A \oplus B) \oplus C = A \oplus (B \oplus C)$$
3. 응용: 이 성질들이 만들어내는 마법
(1) 데이터 복구 (RAID 5의 원리)
하드디스크 A, B, C가 있고, C에 패리티 정보를 저장한다고 가정합시다. $$A \oplus B = C$$
만약 디스크 A가 고장 나서 사라졌다면? 남은 B와 C를 XOR 하면 A가 부활합니다.
$$ \begin{aligned} B \oplus C &= B \oplus (A \oplus B) & (\because C = A \oplus B) \\ \\ &= A \oplus (B \oplus B) & (\text{결합 법칙}) \\ \\ &= A \oplus 0 & (\text{자기 소거}) \\ \\ &= A & (\text{항등원}) \end{aligned} $$
결론: 사라진 $A$가 수학적으로 완벽하게 복구되었습니다.
(2) 암호화 (One-Time Pad)
평문($P$)에 키($K$)를 XOR 하여 암호문($C$)을 만듭니다. $$P \oplus K = C$$
암호를 풀려면? 암호문($C$)에 다시 키($K$)를 XOR 하면 됩니다. $$C \oplus K = (P \oplus K) \oplus K = P \oplus 0 = P$$
특징: 암호화 과정과 복호화 과정이 완벽하게 동일합니다. (같은 키로 한 번 더 때리면 원래대로 돌아옴)
(3) 변수 값 교체 (Swap without temp)
임시 변수(temp) 없이 두 변수 x, y의 값을 바꿀 수 있는 유명한 트릭입니다. (메모리 제약이 극심한 임베디드 환경에서 사용되곤 했습니다.)
// 초기값: x=10, y=20
x = x ^ y;
y = x ^ y; // y는 원래 x값이 됨
x = x ^ y; // x는 원래 y값이 됨