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
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.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.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
easy19
01Add Binary— LC 67→02Single Number— LC 136→03Reverse Bits— LC 190→04Number of 1 Bits— LC 191→05Power of Two— LC 231→06Missing Number— LC 268→07Power of Three— LC 326→08Counting Bits— LC 338→09Power of Four— LC 342→10Find the Difference— LC 389→11Convert a Number to Hexadecimal— LC 405→12Fizz Buzz— LC 412→13Hamming Distance— LC 461→14Number Complement— LC 476→15Complement of Base 10 Integer— LC 1009→16Number of Steps to Reduce a Number to Zero— LC 1342→17Sort Integers by The Number of 1 Bits— LC 1356→18XOR Operation in an Array— LC 1486→19Check if the Sentence Is Pangram— LC 1832→
medium20
01Reverse Integer— LC 7→02Divide Two Integers— LC 29→03Pow(x, n)— LC 50→04Subsets— LC 78→05Single Number II— LC 137→06Repeated DNA Sequences— LC 187→07Bitwise AND of Numbers Range— LC 201→08Single Number III— LC 260→09Maximum Product of Word Lengths— LC 318→10Sum of Two Integers— LC 371→11Maximum XOR of Two Numbers in an Array— LC 421→12Total Hamming Distance— LC 477→13Beautiful Arrangement— LC 526→14Partition to K Equal Sum Subsets— LC 698→15Maximum Length of a Concatenated String with Unique Characters— LC 1239→16Number of Steps to Reduce a Number in Binary Representation to One— LC 1404→17Decode XORed Permutation— LC 1734→18Minimum Number of Work Sessions to Finish the Tasks— LC 1986→19Fair Distribution of Cookies— LC 2305→20Bitwise XOR of All Pairings— LC 2425→
hard7
01Shortest Path Visiting All Nodes— LC 847→02Find the Shortest Superstring— LC 943→03Smallest Sufficient Team— LC 1125→04Parallel Courses II— LC 1494→05Maximum Number of Achievable Transfer Requests— LC 1601→06Minimum One Bit Operations to Make Integers Zero— LC 1611→07Distribute Repeating Integers— LC 1655→