Why Bit Manipulation Matters in Interviews
Bit manipulation problems test your understanding of how integers are represented in binary and how bitwise operations work at the hardware level. They frequently appear at Google, Meta, and other top companies because they require precise thinking and often have elegant O(1) solutions that are non-obvious. The key operations: AND (&): both bits must be 1. OR (|): at least one bit must be 1. XOR (^): exactly one bit must be 1 (used for toggling and finding unique elements). NOT (~): flips all bits. Left shift (<>): divide by power of 2. Arithmetic right shift (>>) preserves the sign bit; logical right shift fills with 0 (language-dependent).
XOR: The Find-Unique-Element Swiss Army Knife
XOR properties: a ^ 0 = a. a ^ a = 0 (a number XORed with itself is 0). XOR is commutative and associative. Application: in an array where every element appears twice except one, XOR all elements — the pairs cancel (a ^ a = 0) and the single element remains.
def single_number(nums: list[int]) -> int:
result = 0
for n in nums:
result ^= n
return result # O(n) time, O(1) space
# Single Number III (LC 260): two elements appear once, all others twice
def single_number_iii(nums: list[int]) -> list[int]:
xor = 0
for n in nums: xor ^= n # xor = a ^ b (the two unique numbers)
# Find a bit where a and b differ (any set bit in xor)
diff_bit = xor & (-xor) # isolate lowest set bit
# Partition numbers by this bit; each group has one unique number
a = 0
for n in nums:
if n & diff_bit:
a ^= n
return [a, xor ^ a]Bit Masks: Subsets and State Compression
Represent a set of n elements as an integer bitmask (bit i = 1 means element i is in the set). Enumerate all subsets: iterate from 0 to 2^n – 1. Check if element i is in mask: (mask >> i) & 1. Add element i: mask | (1 << i). Remove element i: mask & ~(1 << i). Toggle element i: mask ^ (1 << i).
def enumerate_subsets(nums: list[int]) -> list[list[int]]:
n = len(nums)
result = []
for mask in range(1 <> i) & 1]
result.append(subset)
return result
# DP with bitmask: Traveling Salesman (Held-Karp)
def tsp(dist: list[list[int]]) -> int:
n = len(dist)
# dp[mask][i] = min cost to visit all cities in mask, ending at city i
INF = float('inf')
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # start at city 0, visited = {0}
for mask in range(1, 1 <> u) & 1: continue
for v in range(n):
if (mask >> v) & 1: continue # already visited
new_mask = mask | (1 << v)
dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])
full = (1 << n) - 1
return min(dp[full][i] + dist[i][0] for i in range(1, n))Power of Two, Counting Bits, and Tricks
# Is n a power of 2? Exactly one bit set.
def is_power_of_two(n: int) -> bool:
return n > 0 and (n & (n - 1)) == 0
# n & (n-1) clears the lowest set bit. If result is 0, only one bit was set.
# Count number of 1-bits (Hamming weight / popcount)
def hamming_weight(n: int) -> int:
count = 0
while n:
n &= (n - 1) # clear lowest set bit
count += 1
return count
# Each iteration clears one 1-bit; O(number of 1-bits)
# Counting Bits (LC 338): count 1-bits for all numbers 0..n
def count_bits(n: int) -> list[int]:
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i >> 1] + (i & 1)
# i >> 1 is i with the lowest bit removed (already computed)
# (i & 1) adds 1 if i is odd
return dp
# Reverse bits (LC 190)
def reverse_bits(n: int) -> int:
result = 0
for _ in range(32):
result = (result <>= 1
return result
# Missing number (LC 268): array of 0..n with one missing
def missing_number(nums: list[int]) -> int:
return len(nums) ^ sum(range(len(nums) + 1)) ^ sum(nums)
# XOR all indices 0..n with all values; duplicates cancel, leaving the missing oneBit tricks cheatsheet: isolate lowest set bit: x & (-x). Clear lowest set bit: x & (x-1). Get all 1s in lowest k bits: (1 <> k) & 1. Set kth bit: x | (1 << k). Clear kth bit: x & ~(1 << k).
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How does XOR find the single unique element in a "pairs plus one unique" array?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”XOR has two key properties: a ^ a = 0 (identical values cancel) and a ^ 0 = a (XOR with 0 is identity). When you XOR all elements in an array where every element appears exactly twice except one: all paired elements XOR to 0 (since they cancel each other). The result is 0 ^ unique = unique. Order does not matter because XOR is commutative and associative. This runs in O(n) time and O(1) space — optimal. The same trick extends to Single Number II (each element appears 3 times except one): use modular bit counting — count the number of 1s at each bit position, take mod 3. Remaining 1-bits form the unique number.”}},{“@type”:”Question”,”name”:”How does the bitmask DP pattern work for the Traveling Salesman Problem?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Held-Karp algorithm: dp[mask][i] = minimum cost to visit exactly the cities in mask, ending at city i. Start: dp[1<<0][0] = 0 (only city 0 visited, at city 0, cost 0). Transition: for each (mask, u) pair, try extending to each unvisited city v: dp[mask | (1<<v)][v] = min(dp[mask | (1<<v)][v], dp[mask][u] + dist[u][v]). Final answer: min over all cities i of dp[(1<<n)-1][i] + dist[i][0] (return to start). State space: 2^n * n states. Time: O(2^n * n^2). This is exponential but far better than the O(n!) brute-force permutation enumeration. Practical for n <= 20 (2^20 = 1M, fits in memory and runs in seconds).”}},{“@type”:”Question”,”name”:”What is the most efficient way to count the number of 1-bits in an integer?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Kernighan's algorithm: while n != 0: n &= (n-1); count++. Each iteration clears the lowest set bit. Runs in O(k) where k = number of 1-bits (best case O(1) for n=0, worst case O(32) for n with all bits set). This is better than checking every bit (always O(32)). In practice: most languages have a built-in popcount: Python bin(n).count('1') or int.bit_count() (Python 3.10+). In competitive programming: use __builtin_popcount(n) in C++. For counting bits for all numbers 0..n (LC 338): DP using dp[i] = dp[i>>1] + (i&1). i>>1 drops the last bit (already computed); (i&1) adds 1 if i is odd. O(n) total.”}},{“@type”:”Question”,”name”:”How does isolating the lowest set bit help in the Single Number III problem?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Single Number III: two unique numbers a and b, all others appear twice. XOR all numbers: result = a ^ b. Since a != b, result != 0, so at least one bit differs between a and b. Isolate the lowest set bit of result: diff_bit = result & (-result). This bit is 1 in a and 0 in b (or vice versa). Partition all numbers into two groups: those with this bit set, and those without. XOR each group separately: the pairs cancel within each group, leaving a in one group and b in the other. The key insight: -x in two's complement equals ~x + 1. x & (-x) leaves only the lowest set bit because all lower bits of x are 0 (by definition of lowest set bit) and all those bits in ~x+1 are 1, canceling out, leaving just the lowest set bit.”}},{“@type”:”Question”,”name”:”How do you use bit manipulation to enumerate all subsets of a set?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Represent the set as an integer bitmask. For n elements, there are 2^n subsets, represented by masks 0 to 2^n – 1. Bit i set in mask means element i is in the subset. To enumerate all subsets: for mask in range(1 << n): process the subset. To enumerate all non-empty subsets of a given mask (useful in DP): for sub = mask; sub > 0; sub = (sub-1) & mask. This iterates over exactly the subsets of mask in decreasing order. The trick (sub-1) & mask clears the lowest set bit of sub and masks back to only bits in mask. Terminates when sub = 0. Time: O(3^n) total across all masks (each element is in 3 states: not in mask, in mask but not in sub, in both mask and sub).”}}]}
See also: Meta Interview Prep
See also: Atlassian Interview Prep
See also: Apple Interview Prep