Bit Manipulation Patterns
The Intuition
Picture a row of light switches on a wall. Each switch is either up (1) or down (0). That row of switches IS a binary number. Every integer your computer works with is just a pattern of on/off switches hiding under the hood. Once you see it that way, bit operations become physical actions you can visualize with your hands.
XOR is the simplest trick to internalize. Imagine you and a friend each have a switch. XOR says "flip the output if your switches are different." If you both have the same position, the result is off. So when you XOR a number with itself, every switch pair matches and everything cancels to zero. XOR any number with zero and nothing changes. That cancellation property is why XOR finds the lone unique number in an array full of duplicates: every paired number annihilates itself, leaving only the loner behind.
AND means "both switches must be on for the output to be on." OR means "either switch on is enough." These let you mask out specific bits or merge bit patterns together. Setting a bit means forcing one switch on with OR. Clearing a bit means forcing one switch off with AND and a flipped mask. Toggling means flipping one specific switch with XOR.
Shifting is even more concrete. Slide all your switches one position to the left, and you get a zero on the right end. You just doubled the number. Slide them right, and you halve it (dropping the last switch off the edge). Left shift by k positions multiplies by 2^k. Right shift by k divides by 2^k.
Once you see numbers as rows of switches, you stop memorizing bit tricks and start deriving them. "Clear the lowest set bit" is just flipping the rightmost up-switch down, which happens to be what n & (n - 1) does because subtracting 1 flips everything from the lowest set bit downward. "Isolate the lowest set bit" is n & (-n) because negation in two's complement flips everything except that lowest set bit. You can reconstruct every trick from the switch mental model.
Finding single/unique numbers, checking or toggling specific bits, counting set bits, power-of-two checks, bitmask DP, subset enumeration, or any problem where binary representation reveals structure.
Numbers are very large (arbitrary precision, bits don't help), need floating point operations, or the problem is about string/array manipulation disguised as a bit problem.
Variations:
- Single bit operations: Check if kth bit is set, set/clear/toggle kth bit, find rightmost set bit position.
- XOR tricks: Find single number, find two unique numbers, find missing number, swap without temp.
- Bit counting: Hamming weight, Hamming distance, count bits in range.
- Bitmask enumeration: Generate all subsets using binary masks.
- Bitmask DP: Use bitmask as DP state for subset problems (TSP, assignment).
- Input value is zero
- Input contains negative numbers
- All bits are set (e.g., 0xFFFFFFFF)
Key Points
- •x & (x - 1) clears the lowest set bit
- •x & (-x) isolates the lowest set bit
- •Check kth bit: (x >> k) & 1 returns 1 if set, 0 if not
- •Set kth bit: x | (1 << k); Clear kth bit: x & ~(1 << k); Toggle: x ^ (1 << k)
- •XOR of a number with itself is 0; XOR with 0 is the number
- •XOR all elements to find the single unique number in a duplicate array
- •Bit shifts: << multiplies by 2, >> divides by 2
- •Swap without temp: a ^= b; b ^= a; a ^= b
Code Template
1 # --- Bit checking & manipulation ---
2 def is_kth_bit_set(n, k):
3 """Check if kth bit (0-indexed from right) is set."""
4 return (n >> k) & 1 == 1
5
6 def set_kth_bit(n, k):
7 """Set the kth bit to 1."""
8 return n | (1 << k)
9
10 def clear_kth_bit(n, k):
11 """Clear the kth bit to 0."""
12 return n & ~(1 << k)
13
14 def toggle_kth_bit(n, k):
15 """Toggle the kth bit."""
16 return n ^ (1 << k)
17
18 def swap_without_temp(a, b):
19 """Swap two numbers using XOR (no temp variable)."""
20 a ^= b
21 b ^= a
22 a ^= b
23 return a, b
24
25 def rightmost_set_bit_pos(n):
26 """Find position of the rightmost set bit (0-indexed)."""
27 if n == 0:
28 return -1
29 pos = 0
30 while (n & 1) == 0:
31 n >>= 1
32 pos += 1
33 return pos
34
35 # --- Classic patterns ---
36 def single_number(nums):
37 """Find the number that appears once (others appear twice)."""
38 result = 0
39 for num in nums:
40 result ^= num
41 return result
42
43 def count_bits(n):
44 """Count number of set bits (Hamming weight)."""
45 count = 0
46 while n:
47 n &= n - 1 # clear lowest set bit
48 count += 1
49 return count
50
51 def is_power_of_two(n):
52 """Check if n is a power of 2."""
53 return n > 0 and (n & (n - 1)) == 0
54
55 def subsets_bitmask(nums):
56 """Generate all subsets using bitmask enumeration."""
57 n = len(nums)
58 result = []
59 for mask in range(1 << n):
60 subset = []
61 for i in range(n):
62 if mask & (1 << i):
63 subset.append(nums[i])
64 result.append(subset)
65 return result
66
67 def two_single_numbers(nums):
68 """Find two numbers that appear once (others twice)."""
69 xor_all = 0
70 for num in nums:
71 xor_all ^= num
72
73 # Find a set bit (difference between the two numbers)
74 diff_bit = xor_all & (-xor_all)
75
76 a = b = 0
77 for num in nums:
78 if num & diff_bit:
79 a ^= num
80 else:
81 b ^= num
82 return [a, b]Common Mistakes
- Operator precedence: bitwise & has higher precedence than |, but both have lower precedence than comparison operators (==, <, >). Always use parentheses: `if ((n & mask) == 0)` not `if (n & mask == 0)`.
- Sign extension with right shift on negative numbers (use >>> in Java)
- Forgetting that Python integers have arbitrary precision (no overflow)
- Off-by-one on bit position: bit 0 is the rightmost (least significant) bit