patternDSA/Bitwise XOR
Core Pattern → Pattern 21

Bitwise XOR

Two laws — a ^ a = 0 and a ^ 0 = a — turn O(n) space solutions into O(1). Pairs cancel. Singles survive.

Frequency:★★★☆☆
·~20 min·Beginner–Intermediate·4 problems
The Core Shock

HashMap uses O(n) space to find one number. XOR uses O(1) space — pairs annihilate each other at the bit level.

HashMap count
O(n) space
Store every number's count. The single is what has count=1. Works but wastes memory.
XOR accumulate
O(1) space
4^1^2^1^2 = 4. Pairs cancel bit by bit. One variable, no extra memory.

XOR is the toggle operator: flip a bit once (on), flip it again (off). Since XOR is commutative and associative, order doesn't matter. Every number that appears twice cancels itself out. The one number that appears once — the single — is all that remains in the accumulator.

The 4 XOR Properties

Memorise all four — they appear in every XOR problem explanation.

Identity
a ^ 0 = a5 ^ 0 = 5
XOR with 0 changes nothing — 0 bits don't flip any bit.
Self-Inverse
a ^ a = 05 ^ 5 = 0
XOR with itself cancels — every bit flips twice, back to 0.
Commutative
a ^ b = b ^ a3 ^ 5 = 5 ^ 3
Order of operands doesn't matter. Allows reordering accumulation.
Associative
(a^b)^c = a^(b^c)(1^2)^3 = 1^(2^3)
Grouping doesn't matter. Pairs anywhere in the array can cancel.

The 3-Step Framework

The same three steps appear in every XOR pattern problem.

01
XOR all → pairs cancel, singles remain

For single-number problems: initialize result=0, XOR every element. All duplicates cancel (a^a=0). The unpaired element XOR'd with 0 stays (a^0=a). Works for any count of duplicates as long as only one element is unpaired.

result = 0
for num in nums:
    result ^= num
return result   # O(n) time, O(1) space
The commutative + associative properties mean you don't need to sort or group. 4^1^2^1^2 = 4^(1^1)^(2^2) = 4^0^0 = 4. Position doesn't matter.
02
For two singles: isolate a differing bit

When two singles exist, XOR gives a^b. Since a≠b, at least one bit differs. Use rightmost_bit = xor_all & (-xor_all) to isolate the lowest set bit. This bit is 1 in exactly one of {a,b} — it partitions all numbers cleanly.

xor_all = reduce(^, nums)          # a ^ b
rightmost_bit = xor_all & (-xor_all)  # isolate lowest bit
num1 = reduce(^ for n if n & bit)
num2 = reduce(^ for n if not n & bit)
n & (-n) isolates the lowest set bit by exploiting two's complement. -n in binary is the bitwise NOT of n plus 1, which clears all bits below the lowest set bit and keeps only that bit when AND'd.
03
For complement/flip: XOR with a crafted mask

Complement of n: XOR with all-ones mask of same length. Create mask = (1 << n.bit_length()) - 1. Flip image: XOR each pixel with 1 (0→1, 1→0). The mask targets only the relevant bits, leaving higher bits untouched.

# Complement
mask = (1 << n.bit_length()) - 1
return n ^ mask

# Flip pixel
pixel ^= 1   # toggles 0↔1
XOR with 1 is the cleanest bit-flip. (1 << k) - 1 creates k ones in binary. Together these let you target exactly the bits you want to flip without touching others.

Pattern Recognition

Space constraint + pairs/singles = XOR.

Use XOR When
"Find the single element" — all others appear twice
"Two numbers appear once, rest appear twice"
Complement of a number (flip bits within its length)
Flip and invert a binary image
Determine if two strings are anagrams (XOR char codes)
Swap two integers without a temp variable
Find missing number in [0..n] range
Detect single differing bit between two numbers
Common Pitfalls
Complement: not masking high bits → wrong result for n.bit_length() edge cases
Two singles: forgetting to XOR all first before partitioning
Two singles: using arbitrary bit instead of rightmost (any set bit works, but rightmost is canonical)
n & (-n) isolates lowest bit — n & (n-1) CLEARS lowest bit (different!)
XOR swap: a^=b; b^=a; a^=b — fails if a and b are the SAME variable/reference
bit_length() of 0 is 0 — complement of 0 needs special case
Confusing ^ (XOR) with ** (power) in Python — easy typo
Sign bits in negative numbers — use & 0xFFFFFFFF for 32-bit problems