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
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.