Bit Manipulation: XOR Tricks, Bit Masking & Power-of-Two Patterns
Bit manipulation problems appear at Google, Amazon, and Meta — often as hard problems with elegant O(1) or O(n) solutions. Master XOR properties (self-inverse, commutative), bit masking for subset enumeration, Brian Kernighan's algorithm for counting set bits, and the classic single-number, missing number, and power-of-two patterns.
Why Bit Manipulation Appears in Interviews
Bit manipulation problems test whether you understand the underlying representation of data, not just how to use high-level data structures. They often have deceptively simple problem statements with elegant solutions: "Find the single non-duplicated number in an array" → one XOR pass over the whole array.
The core properties used in 90% of bit problems:
a XOR a = 0— a number XOR'd with itself is zeroa XOR 0 = a— a number XOR'd with zero is itself- XOR is commutative and associative:
a XOR b XOR a = b n & (n-1)— clears the lowest set bit of nn & (-n)— isolates the lowest set bit of nn & (n-1) == 0— true iff n is a power of 2 (and n > 0)
Signal words: "find the unique number," "find the missing number," "count the number of 1 bits," "subsets of a set," "check if power of 2," "swap without a temp variable."
What Interviewers Evaluate
6/10: Knows basic bitwise operators. Can solve simple bitmask problems with some hints.
8/10: Immediately recognizes the XOR self-inverse property for "find single number." Knows Brian Kernighan's algorithm for counting set bits. Implements subset enumeration with bitmasks. Explains the n & (n-1) trick.
10/10: Derives the XOR solution from first principles ("XOR is its own inverse, so duplicates cancel"). Extends single-number to "every element appears 3 times" using bit counting. Explains two's complement to justify n & (-n). Knows the full bit-twiddling hacks (SWAR popcount, parallel prefix). Names real applications: Redis bitmaps, bloom filters, chess engine move generation.
Core Bit Manipulation Techniques
XOR Self-Inverse: eliminate pairs
XOR all elements together. Duplicates cancel to 0 (a^a=0). Only the unique element survives (a^0=a). Works for any number of pairs: [1,2,1,3,2] → 1^2^1^3^2 = (1^1)^(2^2)^3 = 0^0^3 = 3. Used for: find the unique number in an array where all others appear exactly twice.
Bit Counting: Brian Kernighan's Algorithm
n & (n-1) clears the rightmost set bit of n. Loop: while n != 0: count += 1; n = n & (n-1). Loop runs exactly once per set bit — if n has k set bits, this is O(k). Much faster than testing each bit individually O(32). Alternative: Python's bin(n).count('1') or Java's Integer.bitCount(n) (uses hardware popcount instruction — O(1)).
Power of Two Check
A power of 2 has exactly one set bit: 8 = 1000₂, 16 = 10000₂. So n & (n-1) (which clears one bit) equals 0. Check: n > 0 and (n & (n-1)) == 0. Handle n=0 explicitly (0 is not a power of 2, but 0 & (-1) = 0). Used in: hash table size validation, memory alignment checks, segment tree implementation.
Bit Masking: Subset Enumeration
For n elements, each subset can be represented as an n-bit mask. Enumerate all 2^n subsets: for mask in range(1 << n): — iterate from 0 to 2^n - 1. For each bit i set in mask: element i is in this subset. Check if bit i is set: (mask >> i) & 1. Iterate only over set bits in a mask: temp = mask; while temp: i = temp.bit_length()-1; use element i; temp &= temp-1.
Isolate and Extract Bits
Get bit at position i: (n >> i) & 1. Set bit at position i: n | (1 << i). Clear bit at position i: n & ~(1 << i). Toggle bit at position i: n ^ (1 << i). Lowest set bit: n & (-n) (because -n = ~n + 1 in two's complement, and & preserves only the bit that's set in both). Clear lowest set bit: n & (n - 1).
XOR Trick: Find Single Number
Problem Templates
Single Number (exactly one element appears once, all others twice):
def single_number(nums: list[int]) -> int:
result = 0
for n in nums:
result ^= n
return result
# O(n) time, O(1) space — XOR self-inverse eliminates pairs
Missing Number (0 to n, one missing):
def missing_number(nums: list[int]) -> int:
n = len(nums)
# XOR all indices 0..n and all array values
# The complete set XOR'd with itself = 0; missing number survives
result = n # start with n (not in array indices 0..n-1)
for i, num in enumerate(nums):
result ^= i ^ num
return result
# Alternative: expected sum = n(n+1)/2; return expected - sum(nums)
# XOR approach avoids integer overflow for large n
Count Set Bits (Hamming Weight):
def hamming_weight(n: int) -> int:
count = 0
while n:
n &= n - 1 # clear rightmost set bit
count += 1
return count
# O(k) where k = number of set bits
Subsets using bitmask:
def all_subsets(nums: list[int]) -> list[list[int]]:
n = len(nums)
result = []
for mask in range(1 << n): # 2^n masks
subset = []
for i in range(n):
if (mask >> i) & 1: # bit i set → include nums[i]
subset.append(nums[i])
result.append(subset)
return result
# O(n × 2^n) — 2^n subsets, each O(n) to build
Single Number III (two unique numbers, all others appear twice):
def single_number_iii(nums: list[int]) -> list[int]:
# Step 1: XOR all nums → a ^ b (where a, b are the two unique numbers)
xor_ab = 0
for n in nums: xor_ab ^= n
# Step 2: find a bit where a and b differ (any set bit of xor_ab)
diff_bit = xor_ab & (-xor_ab) # isolate lowest set bit
# Step 3: split nums into two groups by that bit; XOR each group
a = b = 0
for n in nums:
if n & diff_bit: a ^= n
else: b ^= n
return [a, b]
# O(n) time, O(1) space
Bit Tricks Quick Reference
| Operation | Code | What it does |
|---|---|---|
| Check bit i | (n >> i) & 1 | Returns 1 if bit i is set, 0 otherwise |
| Set bit i | n | (1 << i) | Forces bit i to 1 |
| Clear bit i | n & ~(1 << i) | Forces bit i to 0 |
| Toggle bit i | n ^ (1 << i) | Flips bit i |
| Clear lowest set bit | n & (n - 1) | Removes the rightmost 1-bit (Brian Kernighan) |
| Isolate lowest set bit | n & (-n) | Returns value with only the rightmost 1-bit |
| Power of 2 check | n > 0 and (n & (n-1)) == 0 | True iff exactly one bit is set |
| XOR swap (no temp) | a ^= b; b ^= a; a ^= b | Swaps a and b without a temporary variable |
| Check if bit i is set in mask | (mask >> i) & 1 | Used in subset enumeration |
| Enumerate all subsets of mask | sub = mask; while sub: use sub; sub=(sub-1)&mask | Iterates all subsets of a bitmask |
Common Mistakes
1. Forgetting n=0 for power-of-two check. 0 & (0-1) = 0 & 0xFFFF... = 0, so the formula says 0 is a power of 2. Always add n > 0 guard: n > 0 and (n & (n-1)) == 0.
2. Integer overflow in missing number via sum. n(n+1)/2 for n = 10^9 overflows a 32-bit int. Use XOR approach or Python (arbitrary precision integers). In Java: use long for the sum.
3. XOR swap edge case: a and b are the same variable. a ^= a → a = 0, then a ^= 0 → a stays 0. Never use XOR swap when a and b might alias (e.g., swap(arr[i], arr[i]) in place sort — use only when guaranteed i ≠ j).
4. Shift by more than 31 in Java (undefined behavior in C/C++). 1 << 32 in Java = 1 << 0 = 1 (shift wraps modulo 32). In C/C++, shifting by >= word size is undefined behavior. Use 1L << n for long-sized shifts.
5. Treating bitmask problems as requiring extra space. When you see "all elements appear k times except one": instead of a HashMap counting occurrences, count bits at each position modulo k. If the unique element has a 1 at bit position i, the sum of bit i across all elements ≡ 1 (mod k). This O(32k) solution uses O(1) space.
Interview Communication
When you see "find the unique element" or "find the missing number," verbalize the XOR intuition before coding: "XOR has two useful properties: a number XOR'd with itself is 0, and a number XOR'd with 0 is itself. So if I XOR all elements together, pairs cancel to 0 and the unique element survives."
For power of two: "A power of 2 has exactly one set bit. Subtracting 1 flips all bits below that set bit and clears it. So n & (n-1) is 0 if and only if n has exactly one bit set — which means n is a power of 2."
This verbal derivation shows you understand the underlying bit representation, not just memorized the trick.