Bitwise XOR
Use XOR's self-cancellation property to find unique elements or toggle bits efficiently.
Single number among duplicates, find two missing, flip image, complement of base-10.
A single pass XORs every element into an accumulator. No data structures needed — duplicates cancel automatically.
XOR has three properties that drive the pattern: x ^ x = 0, x ^ 0 = x, and it's commutative/associative. Together these mean XORing a sequence cancels every duplicated value, leaving only what appeared an odd number of times. 'Single number among pairs' is the canonical application: XOR everything, get the unique.
For the 'two singles among pairs' variant, XORing everything gives a ^ b. Find any set bit in that XOR — at that bit, a and b differ. Partition the array by that bit and XOR each partition independently to recover a and b. O(n) time, O(1) space, no hash set.
XOR also enables sum-without-carry: a ^ b is the addition of a and b ignoring carries, and (a & b) << 1 is the carry. Looping this gives addition with only bitwise operators. Less commonly seen but high-signal: missing number in 0..n via XOR of indices XOR values, and gray-code generation via i ^ (i >> 1).
Because XOR is its own inverse (x ^ x = 0) and order-independent, it can detect oddly-occurring elements in O(n) time and O(1) space — a strict improvement over hash-set solutions whenever the duplication structure is known.
- Applying XOR-cancellation when elements appear an even-but-not-2 number of times — still cancels, but if appearance counts mix even and odd, the result is the XOR of all odd-occurring values, which may not be a single element.
- For 'every element appears 3 times except one', plain XOR doesn't work — you need bit-counting mod 3 or a two-variable state machine.
- Choosing the lowest set bit incorrectly with `xor & -xor` in languages with no native unsigned integers, hitting overflow on INT_MIN.
- Forgetting that XOR of a range 1..n has a closed-form (depends on n mod 4), and computing it linearly when not needed.
- Confusing XOR with addition — they agree only when there are no carries, i.e. when (a & b) == 0.
- Single number (others appear twice): XOR everything.
- Two singles (others appear twice): XOR all, isolate a differing bit, partition.
- Single number (others appear three times): bit-count mod 3 across positions.
- Missing number in 0..n: XOR indices XOR values.
- Sum of two integers without +: XOR for sum-without-carry, AND<<1 for carry, loop.
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;Problems using this pattern
2Easiest first · Blind 75 above NeetCode 150