Sweaty Imposter

Bitwise XOR Pattern

CodingMid2 min read · 6 problemsUpdated

Use XOR's self-cancellation property to find unique elements or toggle bits efficiently.

When to Use It

Single number among duplicates, find two missing, flip image, complement of base-10.

Classic example: Find the single number in an array where every other appears twice.

How It Works

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).

Key Insight

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.

Templates

int result = 0;
for (int num : nums) {
    result ^= num;
}
return result;

Common Pitfalls

  • 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.

Variations

  • 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.

Big O

Time
O(n)
Space
O(1)
A single pass XORs every element into an accumulator. No data structures needed, duplicates cancel automatically.
Next PatternTop K Elements