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).
See also: Meta Interview Prep
See also: Atlassian Interview Prep
See also: Apple Interview Prep