Bit Manipulation
01 / The one-sentence essence
Treat integers as their bits, not their values. XOR a number against itself zeroes it; against zero keeps it. The pattern is recognizing when a problem hides a bit-level structure.
Problemfind the unique elementInput[2, 3, 5, 4, 5, 3, 4]
arr
2
3
5
4
5
3
4
acc
0
0
0
0
0
0
0
0
= 0
Array of 7 integers. Every value appears twice — except one. Find it by XOR-folding the whole array.
step
0 / 15
accumulator
0
current
—
result
—
0 / 15
02 / The pattern signature
# XOR fold — find the element that appears onceresult ← 0for x in arr:result ← result ⊕ xreturn result# XOR is commutative + associative + a ⊕ a = 0:# every duplicate pair cancels itself, the unique survivor remains.# Same skeleton for: bit-count (popcount), bitmask DP, subset enumeration via bits.
03 / When to recognize this pattern
"appears once / twice / k times"
Duplicates and uniqueness invite XOR. Two of every element except one is the canonical XOR-fold problem; every element appears three times except one shifts to per-bit modulo counting.
"subset / power set"
Each subset of
N elements is a bitmask of N bits. Iterating mask from 0 to 2^N − 1 enumerates every subset exactly once — faster and tighter than recursion when N ≤ 20."count set bits / parity"
Population count (
x & (x − 1) clears the lowest set bit) and parity are the two pillars. They show up in Hamming distance, balanced strings, gray codes."swap without temp / no extra memory"
A constraint of O(1) extra space on a problem that obviously wants a hash set is the loudest hint. The constraint is almost always there because XOR can hold the answer in a single integer.
04 / Common pitfalls
i.
Mixing up XOR and OR.
XOR (
⊕, ^) is "different bits". OR (|) is "either bit". They look similar in symbol soup but do opposite jobs for the "two of every except one" problem — OR will just give you the bitwise OR of every element, which is useless.ii.
Forgetting XOR's identity element is 0.
Initialize the accumulator to
0, not to arr[0]. 0 ⊕ x = x, so starting at 0 lets the loop body handle every element uniformly. Starting at arr[0] works but the off-by-one is a magnet for bugs when the problem generalizes.iii.
Confusing logical AND with bitwise AND.
In most languages
&& short-circuits and returns a boolean; & is the bitwise operator. Mixing them silently changes the type of the expression and breaks the math. In Python the keyword and is logical, & is bitwise — be especially careful around boolean-looking values.05 / Go practice — on LeetCode
Four problems, ordered by difficulty. No solutions here, by design.