-
Notifications
You must be signed in to change notification settings - Fork 0
030 — Bit Manipulation Tricks
Picture a row of 32 light switches on a wall, each one either on or off, representing a single number. Most problems treat that number as an opaque value — you add it, compare it, print it. But some problems are really asking you to reach behind the wall and flip individual switches directly: turn this bit off, check if that bit is on, count how many switches are flipped on in total. The switches don't care about carrying or borrowing the way decimal addition does — flipping one switch never affects its neighbors, which is exactly what makes bit tricks so fast and so different in flavor from every other pattern in this book. Once you notice a problem is really about the switches themselves rather than the number they represent, a small toolbox of switch-flipping moves — XOR to toggle, AND with a shifted 1 to test, n & (n - 1) to clear the lowest set switch — solves it in a handful of operations instead of a loop over the number's magnitude.
Reach for bit manipulation when you see:
- "Without using extra space" combined with numbers that could be duplicated or paired up — "single number" (every element appears twice except one, find it) is the textbook case: XOR-ing everything together cancels every pair, leaving only the unpaired value, in O(1) space and one pass.
- The word "XOR" appears explicitly, or the problem is phrased as "find the difference between two arrays/strings using minimal extra structure" — swapping two values without a temp variable, finding a missing number in a range, finding the two non-repeated elements among duplicates.
-
"Power of two," "power of four," or "count sits/set bits" — checking
n & (n - 1) == 0for power-of-two, or Brian Kernighan's trick (n & (n - 1)repeatedly to strip the lowest set bit) for counting set bits — these have a recognizable one-liner bit trick as the entire solution. -
"Without using arithmetic operators" or "add/subtract using bit operations only" — explicitly bans
+/-and asks you to simulate them with&,^, and<<, forcing you to think in terms of carry bits.
The unifying tell: the problem's constraints highlight O(1) extra space, explicitly mention XOR/bitwise operators, or ask about a number's binary representation directly (power-of-two, set-bit count) rather than its numeric value.
XOR canceling paired values, leaving only the unpaired one — the mechanic behind "Single Number":
array: [4, 1, 2, 1, 2]
XOR every element together, one at a time:
result = 0
result ^= 4 -> 0100
result ^= 1 -> 0100 ^ 0001 = 0101
result ^= 2 -> 0101 ^ 0010 = 0111
result ^= 1 -> 0111 ^ 0001 = 0110
result ^= 2 -> 0110 ^ 0010 = 0100 = 4
why it works: x ^ x == 0 (a value XORed with itself cancels to 0)
x ^ 0 == x (XOR with 0 is a no-op)
so every PAIR cancels itself out, in any order,
leaving only the single unpaired value standing: 4
Brian Kernighan's trick for counting set bits — n & (n - 1) always clears exactly the lowest set bit:
n = 0b1011000 (=88)
n - 1 = 0b1010111
n & (n-1) = 0b1010000 <- lowest set bit (the rightmost 1) cleared
repeat until n == 0; the number of iterations = number of set bits
// Shape A: XOR-accumulate to cancel out paired values.
func xorCancelTemplate(_ nums: [Int]) -> Int {
var result = 0
for n in nums {
result ^= n // 🔧 Fill in: XOR is the whole trick — pairs cancel, singles survive
}
return result
}
// Shape B: inspect/manipulate individual bits directly.
func bitInspectionTemplate(_ n: Int) -> Int {
var n = n
var count = 0
while n != 0 {
n = n & (n - 1) // 🔧 Fill in: clears the lowest set bit — swap for whatever bit op you need
count += 1
}
return count // 🔧 Fill in: return whatever the problem actually asks for
}
// Common single-bit helpers, useful building blocks across many bit problems:
func isBitSet(_ n: Int, _ position: Int) -> Bool {
return (n & (1 << position)) != 0
}
func setBit(_ n: Int, _ position: Int) -> Int {
return n | (1 << position)
}
func clearBit(_ n: Int, _ position: Int) -> Int {
return n & ~(1 << position)
}Single Number — given a non-empty array of integers nums where every element appears twice except for one, find that single one. Must run in linear time with O(1) extra space.
func singleNumber(_ nums: [Int]) -> Int {
var result = 0
for n in nums {
result ^= n
}
return result
}
// smoke test
print(singleNumber([2, 2, 1])) // 1
print(singleNumber([4, 1, 2, 1, 2])) // 4
print(singleNumber([1])) // 1
print(singleNumber([7, 3, 5, 3, 7])) // 5This is Shape A of the template applied with zero modification: XOR-ing every element together in a single pass leaves exactly the unpaired element standing, since x ^ x = 0 cancels every duplicate pair regardless of the order they appear in, and x ^ 0 = x means the running result is unaffected until the lone unpaired value shows up. The O(1) extra space requirement is what should point straight at this pattern — a hashmap-counting approach solves it too, but at O(n) space, which is the tell that the problem wants the bit trick specifically.
Bit manipulation is the row of light switches behind the wall — stop thinking about the number and start flipping, testing, and counting the switches directly.
"Single Number II" changes the rule so every element appears three times except for one that appears once — the simple result ^= n XOR-accumulate no longer works, since XOR-ing a value with itself three times leaves the value itself, not zero. Without writing the full solution, explain in one or two sentences why counting set bits at each bit position (mod 3) is the direction this variant pushes you toward.