XOR Tricks

XOR has three properties that make it constantly useful: it's commutative ($a \oplus b = b \oplus a$), associative ($(a \oplus b) \oplus c = a \oplus (b \oplus c)$), and self-inverse ($a \oplus a = 0$, and $a \oplus 0 = a$).

Single number among pairs

An array contains all integers in pairs except one. Find the unique one. XOR everything; the pairs cancel; the unique value remains. $O(n)$ time, $O(1)$ space.

Swap without temp

``` a = a ^ b b = a ^ b // now b == old a a = a ^ b // now a == old b ```

Mostly a parlor trick — modern compilers optimize a temp-variable swap to the same thing — but it shows the structure.

Two unique numbers among pairs

XOR everything to get $x \oplus y$ for the two unique values $x, y$. The lowest set bit in $x \oplus y$ is a position where $x$ and $y$ differ. Partition the array by that bit; each partition contains exactly one of $x, y$ (plus pairs). XOR each partition separately to recover both. $O(n)$.

Range XOR

XOR of $0, 1, 2, \dots, n$ has a periodic pattern of length 4. Useful for quickly computing range XORs without prefix arrays.

Hashing and parity

XOR is also used in fast hash functions (often combined with shifts and rotations) and in parity bits for error detection. It's the only logical operator that's both reversible and uniform — every bit of the output depends on bits from both inputs equally.

Cautions

XOR doesn't replace addition. `a + b` and `a ^ b` agree only when there are no carries. The bit-level relation: `a + b == (a ^ b) + 2 * (a & b)` — the XOR is the sum without carries, the AND is the carry pattern.