XOR: The Most Magical Operation in Computer Science
In Computer Science, there are many logical operations (AND, OR, NOT...), but none are as unique or powerfully applicable as XOR (Exclusive OR).
From Cryptography and Data Recovery (RAID) to Graphics Processing, let's explore how this seemingly simple operation manages to preserve and restore "traces of information."
1. Definition: "1 if Different, 0 if Same"
XOR returns True (1) only when the two input bits are different.
In mathematics, it is denoted by $\oplus$ (Circle Plus), and in programming languages (C, Python, Java, etc.), the caret symbol ^ is used.
Truth Table
| Input A | Input B | Result ($A \oplus B$) | Description |
|---|---|---|---|
| 0 | 0 | 0 | Same |
| 0 | 1 | 1 | Different |
| 1 | 0 | 1 | Different |
| 1 | 1 | 0 | Same |
Intuitive Understanding: * Carry-less Addition: $1 + 1 = 2$, but in the 1-bit binary world, it becomes
0(ignoring the carry). * Difference Detector: It outputs a signal (1) only when a difference is detected between values.
2. The 3 Core Laws of XOR
These properties form the mathematical foundation that makes XOR so magical.
① Identity Law
XORing any number with 0 returns the original number.
$$A \oplus 0 = A$$
② Self-Inverse Law
The most critical property. XORing the same number twice results in 0 (they cancel each other out). $$A \oplus A = 0$$
③ Commutative & Associative Laws
Order does not matter. $$A \oplus B = B \oplus A$$ $$(A \oplus B) \oplus C = A \oplus (B \oplus C)$$
3. Applications: The Magic in Action
(1) Data Recovery (RAID 5 Logic)
Assume we have Hard Drives A, B, and C, where C stores the parity information. $$A \oplus B = C$$
What if Drive A fails and is lost? By XORing the remaining drives B and C, A is resurrected.
$$ \begin{aligned} B \oplus C &= B \oplus (A \oplus B) & (\because C = A \oplus B) \\ \\ &= A \oplus (B \oplus B) & (\text{Associative Law}) \\ \\ &= A \oplus 0 & (\text{Self-Inverse Property}) \\ \\ &= A & (\text{Identity Law}) \end{aligned} $$
Conclusion: The missing data $A$ is mathematically perfectly recovered.
(2) Cryptography (One-Time Pad)
To encrypt, XOR the Plaintext ($P$) with a Key ($K$) to get Ciphertext ($C$). $$P \oplus K = C$$
To decrypt? Simply XOR the Ciphertext ($C$) with the Key ($K$) again. $$C \oplus K = (P \oplus K) \oplus K = P \oplus 0 = P$$
Feature: The encryption and decryption processes are identical. (Hitting it with the same key one more time reverts it to the original state).
(3) Variable Swap (Swap without temp)
A famous trick to swap values of two variables x and y without using a temporary variable temp. (Often used in embedded systems with extreme memory constraints).
// Initial: x=10, y=20
x = x ^ y;
y = x ^ y; // y becomes the original x
x = x ^ y; // x becomes the original y