Essential Bit Operations
x & y # AND: both bits must be 1 x | y # OR: at least one bit is 1 x ^ y # XOR: exactly one bit is 1 (differs) ~x # NOT: flip all bits x <> n # right shift: divide by 2^n (arithmetic in Python) # Key tricks: x & (x-1) # clear the lowest set bit of x x & (-x) # isolate the lowest set bit of x x ^ x = 0 # XOR with itself = 0 x ^ 0 = x # XOR with 0 = x
Single Number (LC 136)
Find the element that appears once when all others appear twice. XOR all elements: pairs cancel (a^a=0), leaving the lone element.
def singleNumber(nums):
result = 0
for n in nums:
result ^= n
return result
LC 137 (appears once, others appear 3 times): use a state machine with two variables (ones, twos) tracking the count of each bit mod 3. LC 260 (two single numbers): XOR gives A^B. Find any set bit in A^B, partition nums by that bit into two groups, XOR each group to get A and B separately.
Count Set Bits (Brian Kernighan’s Algorithm)
Repeatedly clear the lowest set bit until x == 0. Each iteration removes one set bit.
def count_bits(x):
count = 0
while x:
x &= x - 1 # clear lowest set bit
count += 1
return count
LC 191 (Number of 1 Bits). Python built-in: bin(x).count(‘1’) or x.bit_count() (Python 3.10+).
Power of Two (LC 231)
A power of two has exactly one set bit. Check: n > 0 and n & (n-1) == 0.
def isPowerOfTwo(n):
return n > 0 and (n & (n - 1)) == 0
Subsets via Bitmask
Enumerate all 2^n subsets of an n-element array using bitmasks. Bit i of mask represents whether element i is in the subset.
def all_subsets(nums):
n = len(nums)
result = []
for mask in range(1 << n): # 0 to 2^n - 1
subset = [nums[i] for i in range(n) if mask & (1 << i)]
result.append(subset)
return result
Also used in: bitmask DP for TSP (Traveling Salesman Problem) and set cover problems. State: dp[mask] = min cost to visit the set of cities in mask.
Reverse Bits (LC 190)
Reverse the 32 bits of an integer. Process bit by bit or use divide-and-conquer (swap halves, then quarters, etc.).
def reverseBits(n):
result = 0
for _ in range(32):
result = (result <>= 1
return result
Sum of Two Integers Without + (LC 371)
XOR computes sum without carry. AND shifted left gives the carry. Repeat until no carry.
def getSum(a, b):
mask = 0xFFFFFFFF # 32-bit mask
while b & mask:
carry = (a & b) << 1
a = a ^ b
b = carry
return a if b == 0 else a & mask # handle Python's arbitrary-precision ints
Common Patterns
- Check bit k:
(x >> k) & 1 - Set bit k:
x | (1 << k) - Clear bit k:
x & ~(1 << k) - Toggle bit k:
x ^ (1 << k) - XOR cancels pairs: use for “find the unique” problems
- x & (x-1) clears lowest bit: use for “count set bits” and “is power of 2”
- Bitmask = subset: n bits represent membership in a set of n elements
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What are the most important bit manipulation tricks for interviews?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Five essential tricks: (1) x & (x-1) clears the lowest set bit — use for counting set bits (Brian Kernighan's) and testing powers of two (n>0 && (n&(n-1))==0). (2) x & (-x) isolates the lowest set bit — used in Fenwick Tree (BIT) updates. (3) x ^ x = 0, x ^ 0 = x — XOR cancels duplicate pairs, leaving the unique element (LC 136, 268). (4) (mask >> k) & 1 checks if bit k is set; mask | (1<<k) sets bit k; mask & ~(1<<k) clears bit k; mask ^ (1<<k) toggles bit k. (5) 1<<n = 2^n — enumerate all 2^n subsets of n elements with for mask in range(1<<n).”}},{“@type”:”Question”,”name”:”How do you find the single number when all others appear twice (LC 136)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”XOR all elements. Since a^a=0 for any a, all pairs cancel. The remaining value is the single element. Python: return reduce(lambda x,y: x^y, nums) or result=0; for n in nums: result^=n; return result. Time O(n), Space O(1). Extension — LC 137 (all appear 3 times except one): maintain two bitmask variables ones and twos representing bits seen 1 and 2 times mod 3. For each number: twos |= (ones & n); ones ^= n; temp = ~(ones & twos); ones &= temp; twos &= temp. Extension — LC 260 (two unique numbers): XOR all to get A^B. Find any set bit in A^B (use lowest_bit = x & -x). Partition nums by whether that bit is set — XOR each partition to get A and B separately.”}},{“@type”:”Question”,”name”:”How do you use bitmasks to represent and enumerate subsets?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”For an array of n elements, represent each subset as an integer mask where bit i=1 means element i is included. Total subsets: 2^n (including empty set = 0). Enumerate: for mask in range(1 << n). Extract elements in subset mask: [nums[i] for i in range(n) if mask & (1<<i)]. Check if mask contains element i: (mask >> i) & 1. Add element i: mask | (1<<i). Remove element i: mask & ~(1<<i). Enumerate all submasks of mask (for DP): for sub_mask = mask; sub_mask > 0; sub_mask = (sub_mask-1) & mask. This iterates through all submasks in O(3^n) total for all 2^n masks. Used in bitmask DP for TSP and set cover problems.”}},{“@type”:”Question”,”name”:”How do you add two integers without using the + operator?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”XOR computes the sum without carry (bit-by-bit addition ignoring carry). AND shifted left gives the carry. Repeat until carry is 0. In Python, handle the 32-bit constraint with a mask: while b & 0xFFFFFFFF: carry = (a & b) << 1; a = a ^ b; b = carry. Python integers have arbitrary precision, so negative numbers don't wrap — mask the result to get 32-bit signed behavior: return a if b==0 else a & 0xFFFFFFFF. In Java/C++: the natural 32-bit int overflow handles this correctly, so the loop runs until b==0. This is LC 371. The same principle is used in hardware adder circuits (ripple carry adder).”}},{“@type”:”Question”,”name”:”How does the Fenwick Tree use bit manipulation?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A Fenwick Tree (Binary Indexed Tree) uses the lowest set bit of an index to determine which cells to update and query. The lowest set bit of index i is i & (-i). Update at position i: advance by i += (i & -i) to propagate the update to all ancestors. Query prefix sum [1..i]: advance by i -= (i & -i) to sum over all responsible ranges. This bit manipulation makes the tree operations O(log n) without explicitly storing the tree structure. The Fenwick Tree stores partial sums where index i is responsible for the range [i – (i&-i) + 1, i]. The bit manipulation elegantly encodes this responsibility without any division or multiplication.”}}]}
Meta coding interviews test bit manipulation patterns. See common questions for Meta interview: bit manipulation problems.
Apple coding interviews test bit manipulation and binary arithmetic. See patterns for Apple interview: bit manipulation and binary problems.
Google coding interviews test bit manipulation patterns. Review problems for Google interview: bit manipulation and bitwise operations.