04 — Bit Manipulation¶
Phase 5 | Week 32–33 | Mar 9 – Mar 15, 2027
Bit manipulation is the closest thing to a bag of tricks in this roadmap. Unlike segment trees or KMP, there’s no single overarching algorithm to internalize — it’s a collection of identities and techniques that each solve a narrow but recurring problem class. The payoff is disproportionate to the learning time: 3-5 days to learn, and it unlocks a category of interview questions that will make you look like a wizard if you know them and like someone who never studied if you don’t.
Binary Representation Review¶
Unsigned integers: Standard binary. Bit k represents 2^k.
Signed integers (two’s complement): The most significant bit (MSB) is the sign bit. Negative numbers: flip all bits and add 1. This is why -1 in binary (32-bit) is 11111111 11111111 11111111 11111111 — all 1s.
Why two’s complement matters for XOR tricks: ~x (bitwise NOT) = -x - 1, i.e., ~0 = -1, ~1 = -2. When you see -x in bit manipulation, it’s ~x + 1. This is used in the lowbit trick: x & (-x) = x & (~x + 1) = lowest set bit of x.
Core Bit Operations¶
AND (&): 1 & 1 = 1, 1 & 0 = 0 → clears bits
OR (|): 0 | 0 = 0, 0 | 1 = 1 → sets bits
XOR (^): 0 ^ 0 = 0, 1 ^ 1 = 0, 0 ^ 1 = 1 → toggles/cancels
NOT (~): ~x = -x - 1 (in two's complement)
Left shift (<<): x << k = x * 2^k
Right shift (>>): x >> k = x / 2^k (arithmetic right shift for signed)
Key Identities — Learn These Cold¶
# Isolate lowest set bit
x & (-x) → gives 2^k where k = position of lowest 1-bit
e.g., 12 (1100) → 12 & (-12) = 4 (0100)
# Clear lowest set bit
x & (x - 1) → removes the lowest 1-bit from x
e.g., 12 (1100) → 12 & 11 = 8 (1000)
loop: while x: x &= x-1 → iterates over set bits
# Check if power of 2
x > 0 and (x & (x - 1)) == 0 → True iff x is a power of 2
# XOR self-inverse
x ^ x = 0 → anything XOR itself is 0
x ^ 0 = x → XOR with 0 is identity
# XOR commutativity and associativity
a ^ b ^ a = b → this is the foundation for "find single element"
a ^ b = b ^ a
(a ^ b) ^ c = a ^ (b ^ c)
# Set bit k
x | (1 << k)
# Clear bit k
x & ~(1 << k)
# Toggle bit k
x ^ (1 << k)
# Check bit k
(x >> k) & 1
Application 1: Find the Single Non-Duplicate¶
Problem: Every element appears twice except one. Find it.
XOR trick: XOR all elements. Pairs cancel (a ^ a = 0). Single element survives.
result = 0
for x in nums:
result ^= x
return result
O(n) time, O(1) space. The naive solution (hashmap) uses O(n) space. XOR is categorically better.
Extension: Every element appears three times except one. XOR doesn’t work (triple cancellation ≠ 0). Instead: count bits. For each bit position, count how many elements have it set. If the count is not divisible by 3, the single element has that bit set. Reconstruct from bit counts. O(32n) = O(n).
Application 2: Find Two Non-Duplicates¶
Problem: Every element appears twice except two elements x and y. Find both.
Trick: XOR all elements → get x ^ y. Find any set bit in x ^ y (use lowbit: diff & (-diff)). This bit is set in exactly one of x or y. Partition all elements into two groups based on this bit. XOR each group → recovers x and y.
xor_all = 0
for n in nums: xor_all ^= n # xor_all = x ^ y
bit = xor_all & (-xor_all) # any differing bit between x and y
x = 0
for n in nums:
if n & bit:
x ^= n # XOR group where this bit is set → x
y = xor_all ^ x # recover y
Application 3: Missing Number¶
Problem: Array has n distinct numbers in range [0, n]. Find the missing one.
XOR solution: XOR the array with [0..n]. Pairs cancel. The missing number survives.
result = len(nums)
for i, n in enumerate(nums):
result ^= i ^ n
return result
Arithmetic solution (also valid): sum(range(n+1)) - sum(nums). Both are O(n), O(1). XOR is more bit-manipulation idiomatic.
Application 4: Brian Kernighan’s Bit Count¶
Count the number of set bits (popcount) in an integer.
Naive: Loop 32 times, check each bit. O(32).
Brian Kernighan’s: Each iteration clears one set bit using x &= x - 1. Runs exactly k iterations where k = number of set bits. O(k).
def count_bits(x):
count = 0
while x:
x &= x - 1 # clear lowest set bit
count += 1
return count
For k sparse integers (many zeros), this is significantly faster than the naive 32-iteration loop. In C++, __builtin_popcount(x) is a hardware instruction — O(1).
Application 5: Subset Enumeration via Bitmasks¶
To enumerate all subsets of a set represented as bitmask mask:
sub = mask
while sub:
# process subset `sub`
sub = (sub - 1) & mask
This enumerates all 2^k subsets of a k-bit mask in O(2^k) time. Across all possible masks with n bits, total time is O(3^n) — each bit independently contributes to 3 outcomes (in mask and in subset, in mask but not in subset, not in mask). This is the standard technique for sum-over-subsets DP.
Application 6: Power of 2, Power of 4, etc.¶
# Power of 2
x > 0 and (x & (x-1)) == 0
# Power of 4: power of 2 AND set bit is at even position
x > 0 and (x & (x-1)) == 0 and (x & 0xAAAAAAAA) == 0
# 0xAAAAAAAA = ...10101010 in binary — set bits at ODD positions
Bitmask DP (Connection to Phase 4)¶
In Phase 4, you used bitmasks as DP state. The operations above are the mechanics underneath that: checking whether a city has been visited (mask >> k) & 1, adding a city mask | (1 << k), counting cities visited bin(mask).count('1'). These are the same identities — just used as state transitions instead of standalone tricks.
What Most Engineers Get Wrong¶
Operator precedence: In C, Java, and Python, comparison operators bind tighter than bitwise operators. n & 1 == 0 is parsed as n & (1 == 0) = n & 0 = 0, always. Correct: (n & 1) == 0. Always parenthesize bitwise ops when mixing with comparisons. This is a silent bug: compiles without warning, produces wrong answers.
Right shift behavior on negative numbers: Arithmetic right shift (>> in Java/Python) preserves the sign bit — -8 >> 1 = -4. Logical right shift (>>> in Java) fills with zeros — -8 >>> 1 = a large positive number. In Python, >> is always arithmetic (Python integers are arbitrary precision). In C, right shift on signed integers is implementation-defined (usually arithmetic on x86). Know which you’re using.
Practice Problems¶
Easy¶
Single Number — LeetCode 136. The XOR single-element trick. Baseline.
Number of 1 Bits — LeetCode 191. Brian Kernighan’s popcount.
Medium¶
Single Number II — LeetCode 137. Every element appears 3 times except one. Bit counting approach.
Single Number III — LeetCode 260. Two single elements. XOR partition trick.
Counting Bits — LeetCode 338. DP + bit trick:
dp[i] = dp[i >> 1] + (i & 1).
Hard¶
Maximum XOR of Two Numbers in an Array — LeetCode 421. Bit trie / greedy bit construction. Uses XOR properties to find maximum in O(32n).