Bit manipulation problems appear at Google, Meta, and Amazon interviews. They test low-level reasoning and often offer O(1) space solutions that seem magical until you understand the patterns. Most interviewers reward recognizing the XOR trick or the n&(n-1) idiom over brute-force approaches.
Core Operators
# Python bit operators
a & b # AND: 1 only if both bits are 1
a | b # OR: 1 if either bit is 1
a ^ b # XOR: 1 if bits differ
~a # NOT: flip all bits (in Python, ~a = -a-1 due to two's complement)
a <> n # right shift: divide by 2^n (arithmetic for signed ints)Pattern 1: XOR for Find-the-Single-Number
XOR has three properties that solve many problems: a ^ a = 0 (XOR with itself = 0), a ^ 0 = a (XOR with 0 = identity), and XOR is commutative and associative. XOR all numbers together — pairs cancel out, leaving the unpaired element.
def singleNumber(nums):
result = 0
for n in nums:
result ^= n
return result
# [4,1,2,1,2] → 4^1^2^1^2 = 4^0^0 = 4Single Number II (every element appears 3 times except one): use a 32-bit counter per bit position, then take mod 3. Or use the two-variable bit accumulation trick (see (ones, twos) state machine).
Pattern 2: n & (n-1) — Clear the Lowest Set Bit
n & (n-1) clears the lowest set bit of n. This is the key to several O(1) or O(number_of_bits) algorithms.
# Count number of 1-bits (Hamming weight) — Brian Kernighan
def hammingWeight(n):
count = 0
while n:
n &= n - 1 # clear lowest set bit
count += 1
return count
# Check if n is a power of two: exactly one bit set
def isPowerOfTwo(n):
return n > 0 and (n & (n - 1)) == 0
# Check if n is a power of four: power of two AND set bit at even position
def isPowerOfFour(n):
return n > 0 and (n & (n-1)) == 0 and (n & 0xAAAAAAAA) == 0Pattern 3: Get / Set / Clear / Toggle Bit
def get_bit(n, i): return (n >> i) & 1
def set_bit(n, i): return n | (1 << i)
def clear_bit(n, i): return n & ~(1 << i)
def toggle_bit(n, i): return n ^ (1 << i)
def update_bit(n, i, v): return clear_bit(n, i) | (v << i)Pattern 4: XOR to Find Two Missing/Extra Numbers
Given an array where two numbers appear once and the rest appear twice (LeetCode 260: Single Number III): XOR all numbers to get a ^ b. Find any set bit in a ^ b (use rightmost: diff = xor & (-xor)). Partition all numbers into two groups by this bit — one group contains a, the other contains b. XOR each group separately to recover a and b.
def singleNumberIII(nums):
xor = 0
for n in nums:
xor ^= n # a ^ b
diff = xor & (-xor) # rightmost differing bit
a = 0
for n in nums:
if n & diff:
a ^= n # XOR one group → recovers a
return [a, xor ^ a] # xor ^ a = bPattern 5: Counting Bits (DP with bit trick)
For all numbers 0 to n, count the 1-bits in each. Brute force: O(n log n). DP trick: the number of 1-bits in i equals the bits in i >> 1 plus the last bit of i.
def countBits(n):
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i >> 1] + (i & 1)
return dp
# dp[6] = dp[3] + 0 = dp[1] + 1 + 0 = 2Pattern 6: Bitmask DP
When state is a subset of n elements (n <= 20), represent it as an integer bitmask. Each bit i indicates whether element i is included. This replaces exponential subset enumeration with bit operations.
# Traveling Salesman Problem (TSP) — O(2^n * n^2)
def tsp(dist, n):
FULL = (1 << n) - 1
dp = [[float("inf")] * n for _ in range(1 << n)]
dp[1][0] = 0 # start at city 0, visited = {0}
for mask in range(1 <> u & 1):
continue # u not in current path
if dp[mask][u] == float("inf"):
continue
for v in range(n):
if mask >> v & 1:
continue # v already visited
new_mask = mask | (1 << v)
dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])
return min(dp[FULL][v] + dist[v][0] for v in range(n))Other bitmask DP problems: Minimum Cost to Connect All Points (when n is small), Shortest Path Visiting All Nodes (LeetCode 847), Stickers to Spell Word.
Pattern 7: Swap Without Temp Variable
a = a ^ b
b = a ^ b # b = (a^b)^b = a
a = a ^ b # a = (a^b)^a = bInteresting but rarely used in practice — modern compilers generate equivalent code and this is less readable. Know it for interviews; avoid it in production.
Pattern 8: Reverse Bits
def reverseBits(n):
result = 0
for _ in range(32):
result = (result <>= 1
return resultOptimized O(1) with divide-and-conquer bit reversal: swap adjacent bits, then pairs, then nibbles, etc. — but the loop version is clearer for interviews.
Bit Tricks Quick Reference
n & 1— check if oddn >> 1— divide by 2 (faster than n // 2 by a constant)n & (n-1)— clear lowest set bit; == 0 means power of twon & (-n)— isolate lowest set bitn | (n-1)— set all bits below lowest set bit~n & (n-1)— trailing zerosx ^ y ^ x == y— XOR cancels paired values
Frequently Asked Questions
What does n & (n-1) do and why is it useful?
n & (n-1) clears the lowest set bit of n. To understand why: subtracting 1 from n flips all bits from the lowest set bit downward. For example, if n = 1100, then n-1 = 1011. ANDing these: 1100 & 1011 = 1000 — the lowest set bit (bit 2) is cleared. This is the foundation of Brian Kernighan's bit-counting algorithm: repeatedly clear the lowest set bit and count how many times you do so before reaching 0. It is also the simplest check for power of two: a power of two has exactly one set bit, so n & (n-1) == 0 (after clearing that single bit, nothing remains). Applications: count set bits in O(k) where k is the number of set bits, check power of two, iterate over all non-zero bit positions of a number.
How does XOR help solve the Single Number problem?
XOR has three key properties: (1) a ^ a = 0 — any number XORed with itself equals zero; (2) a ^ 0 = a — any number XORed with zero equals itself; (3) XOR is commutative and associative, so order does not matter. In the Single Number problem, every element appears twice except one. XOR all elements together: paired elements cancel (a ^ a = 0), leaving only the unpaired element (0 ^ unique = unique). This runs in O(n) time and O(1) space — no hash map needed. Extension: if two elements appear once (Single Number III), XOR all to get a ^ b. The bits where a ^ b has a 1 are bit positions where a and b differ. Pick any such bit (the rightmost: diff = xor & (-xor)). Partition all numbers by this bit — one partition will contain a, the other b. XOR each partition separately to isolate a and b.
What is bitmask DP and when should you use it?
Bitmask DP represents a subset of n elements as an integer where bit i = 1 means element i is included in the subset. This enables DP over all 2^n subsets with O(2^n * n) time and O(2^n * n) space, practical for n up to 20. The key insight: you can enumerate subsets of a bitmask, transition from one subset to another by setting or clearing bits, and check membership with a single AND operation. Classic problems: Traveling Salesman Problem (shortest tour through all cities — state is (current_city, set_of_visited_cities)), Assignment Problem (match tasks to workers — state is set_of_assigned_tasks), Shortest Path Visiting All Nodes (LeetCode 847 — state is (current_node, set_of_visited_nodes)). Recognition signal: problem asks for optimal over all subsets of a small set (n <= 20), and the number of subsets is the key to avoiding exponential enumeration.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What does n & (n-1) do and why is it useful?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “n & (n-1) clears the lowest set bit of n. To understand why: subtracting 1 from n flips all bits from the lowest set bit downward. For example, if n = 1100, then n-1 = 1011. ANDing these: 1100 & 1011 = 1000 — the lowest set bit (bit 2) is cleared. This is the foundation of Brian Kernighan’s bit-counting algorithm: repeatedly clear the lowest set bit and count how many times you do so before reaching 0. It is also the simplest check for power of two: a power of two has exactly one set bit, so n & (n-1) == 0 (after clearing that single bit, nothing remains). Applications: count set bits in O(k) where k is the number of set bits, check power of two, iterate over all non-zero bit positions of a number.”
}
},
{
“@type”: “Question”,
“name”: “How does XOR help solve the Single Number problem?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “XOR has three key properties: (1) a ^ a = 0 — any number XORed with itself equals zero; (2) a ^ 0 = a — any number XORed with zero equals itself; (3) XOR is commutative and associative, so order does not matter. In the Single Number problem, every element appears twice except one. XOR all elements together: paired elements cancel (a ^ a = 0), leaving only the unpaired element (0 ^ unique = unique). This runs in O(n) time and O(1) space — no hash map needed. Extension: if two elements appear once (Single Number III), XOR all to get a ^ b. The bits where a ^ b has a 1 are bit positions where a and b differ. Pick any such bit (the rightmost: diff = xor & (-xor)). Partition all numbers by this bit — one partition will contain a, the other b. XOR each partition separately to isolate a and b.”
}
},
{
“@type”: “Question”,
“name”: “What is bitmask DP and when should you use it?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Bitmask DP represents a subset of n elements as an integer where bit i = 1 means element i is included in the subset. This enables DP over all 2^n subsets with O(2^n * n) time and O(2^n * n) space, practical for n up to 20. The key insight: you can enumerate subsets of a bitmask, transition from one subset to another by setting or clearing bits, and check membership with a single AND operation. Classic problems: Traveling Salesman Problem (shortest tour through all cities — state is (current_city, set_of_visited_cities)), Assignment Problem (match tasks to workers — state is set_of_assigned_tasks), Shortest Path Visiting All Nodes (LeetCode 847 — state is (current_node, set_of_visited_nodes)). Recognition signal: problem asks for optimal over all subsets of a small set (n <= 20), and the number of subsets is the key to avoiding exponential enumeration."
}
}
]
}