Bitwise XOR Pattern

Why XOR Cancels Noise

XOR problems feel magical until you focus on one algebraic fact: a ^ a = 0 and a ^ 0 = a. That means paired values cancel each other completely, leaving only information that appears an odd number of times. Because XOR is also commutative and associative, the cancellation works no matter what order the numbers arrive. You can stream through the array once, accumulate XOR, and let arithmetic cancellation remove the noise.

The pattern is powerful when the problem guarantees regular repetition except for a few anomalies. If every normal value appears twice and one value appears once, XOR isolates the single value immediately. If the list should contain all numbers from 0..n but one is missing, XOR the full expected range and the actual array together; every matched number disappears, leaving the missing one.

The deeper insight is that XOR acts like parity bookkeeping at the bit level. Each bit records whether it has been seen an odd or even number of times across the input. When duplicates appear exactly twice, their parity returns to even, which is why they vanish. When a value or a bit pattern is left unmatched, its odd parity survives in the final accumulator.

Worked Example

Take [4, 1, 2, 1, 2]. Start with x = 0. XOR 4 to get 4. XOR 1 to get 5. XOR 2 to get 7. XOR the next 1 and the effect of the earlier 1 disappears, so the accumulator returns to 6. XOR the final 2 and the earlier 2 disappears too, leaving 4. The array never had to be sorted, counted, or stored in a set; duplicates deleted themselves through parity.

The two-single-numbers variant adds one more idea. Suppose every number appears twice except a and b. XOR of the whole array yields a ^ b, which is not enough to identify them directly. But any set bit in a ^ b marks a position where a and b differ. Use one such bit as a partition rule: split numbers into two groups based on whether that bit is on. The duplicate pairs still cancel within their own group, while a and b land in different groups and survive separately.

Implementation

Pattern Extensions

For Single Number II, where every normal value appears three times, plain XOR is not enough because a ^ a ^ a = a, not zero. The right extension is to count set bits per position modulo 3, reconstructing the unique value from the leftover residues. For missing-number problems, XOR works because the expected set of values is fully known. XOR the expected range with the observed array, and only the missing element remains uncancelled.

Use XOR when the repetition structure is rigid and the question asks for the anomaly. Do not use it when values can repeat arbitrary numbers of times or when the guarantees are too loose to predict cancellation. In those cases, maps or sorting carry the necessary information more explicitly.

Practice Problems

Quiz