Bit Manipulation Tricks You Should Know for Interviews
XOR tricks, bit counting, power of two checks — practical bit manipulation techniques that come up in coding interviews.
Bit manipulation is niche, but it shows up just often enough that you need the fundamentals. The good news: the set of tricks is small and learnable.
Essential Bit Operations
- AND (
&): Both bits must be 1. Masking and clearing bits. - OR (
|): At least one bit is 1. Setting bits. - XOR (
^): Bits must differ. Toggling bits, finding unique elements. - NOT (
~): Flips all bits. - Left shift (
<<): Multiply by 2. - Right shift (
>>): Divide by 2.
Let's see these operations in action with some fundamental examples.
# Python Examples
n = 5 # Binary: 0101
m = 3 # Binary: 0011
print(f"n & m = {n & m}") # 0101 & 0011 = 0001 (1)
print(f"n | m = {n | m}") # 0101 | 0011 = 0111 (7)
print(f"n ^ m = {n ^ m}") # 0101 ^ 0011 = 0110 (6)
print(f"~n = {~n}") # ~0101 = ...11111010 (-6) in two's complement
print(f"n << 1 = {n << 1}") # 0101 << 1 = 1010 (10)
print(f"n >> 1 = {n >> 1}") # 0101 >> 1 = 0010 (2)
XOR: The Interview Workhorse
Three key properties: x ^ x = 0, x ^ 0 = x, and XOR is commutative/associative.
Single Number: Every element appears twice except one. XOR all elements -- pairs cancel, leaving the unique one. O(n) time, O(1) space.
def singleNumber(nums):
result = 0
for num in nums:
result ^= num
return result
# Example: [4, 1, 2, 1, 2]
# 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4
print(singleNumber([4, 1, 2, 1, 2])) # Output: 4
Single Number II (three times): For each bit position, count how many numbers have it set. If the count is not divisible by 3, the single number has that bit.
def singleNumberII(nums):
result = 0
for i in range(32): # For 32-bit integers
count = 0
for num in nums:
# Check if the i-th bit is set
if (num >> i) & 1:
count += 1
# If count % 3 != 0, set the i-th bit in result
if count % 3:
result |= (1 << i)
# Handle negative numbers in Python (two's complement)
if result >= (1 << 31):
result -= (1 << 32)
return result
print(singleNumberII([2, 2, 3, 2])) # Output: 3
Single Number III (two unique elements): XOR all to get x ^ y. Find any set bit (rightmost: diff & (-diff)). Partition numbers by that bit into two groups. XOR each group to get x and y.
def singleNumberIII(nums):
# Step 1: XOR all numbers to get x ^ y
xor_all = 0
for num in nums:
xor_all ^= num
# Step 2: Find the rightmost set bit
diff = xor_all & -xor_all
# Step 3: Partition and XOR
x = 0
for num in nums:
if num & diff: # Numbers with the bit set
x ^= num
y = xor_all ^ x
return [x, y]
print(singleNumberIII([1, 2, 1, 3, 2, 5])) # Output: [3, 5]
Missing Number: XOR all array elements with 0 through n. Everything pairs except the missing number.
def missingNumber(nums):
result = 0
# XOR all numbers from 0 to n
for i in range(len(nums) + 1):
result ^= i
# XOR all numbers in the array
for num in nums:
result ^= num
return result
print(missingNumber([3, 0, 1])) # Output: 2
Power of Two Check
n & (n - 1) == 0 for positive n. Subtracting 1 flips the single set bit and sets all lower bits. AND produces zero. Example: 8 = 1000, 7 = 0111, 1000 & 0111 = 0000.
def isPowerOfTwo(n):
if n <= 0:
return False
return (n & (n - 1)) == 0
print(isPowerOfTwo(8)) # True
print(isPowerOfTwo(6)) # False
print(isPowerOfTwo(0)) # False
print(isPowerOfTwo(1)) # True (2^0)
Counting Set Bits (Brian Kernighan's)
Clear the lowest set bit with n = n & (n - 1) and count iterations. Each iteration removes exactly one set bit.
Number of 1 Bits: Direct application.
def hammingWeight(n):
count = 0
while n:
n &= (n - 1) # Clear the lowest set bit
count += 1
return count
print(hammingWeight(11)) # 11 = 1011 in binary, output: 3
print(hammingWeight(128)) # 128 = 10000000, output: 1
Counting Bits (0 to n): DP approach: result[i] = result[i & (i - 1)] + 1 since i & (i-1) has one fewer set bit.
def countBits(n):
result = [0] * (n + 1)
for i in range(1, n + 1):
# i & (i-1) removes the lowest set bit
result[i] = result[i & (i - 1)] + 1
return result
print(countBits(5)) # Output: [0, 1, 1, 2, 1, 2]
# Explanation:
# 0: 0 -> 0 bits
# 1: 1 -> 1 bit
# 2: 10 -> 1 bit
# 3: 11 -> 2 bits
# 4: 100 -> 1 bit
# 5: 101 -> 2 bits
Bit Masking
Use an integer as a set where each bit represents an element. For n elements, iterate from 0 to 2^n - 1, checking each bit.
Subsets enumeration: Each integer in [0, 2^n) is a subset. Check bit j: mask & (1 << j).
def subsets(nums):
n = len(nums)
result = []
total_subsets = 1 << n # 2^n
for mask in range(total_subsets):
subset = []
for i in range(n):
if mask & (1 << i): # Check if i-th bit is set
subset.append(nums[i])
result.append(subset)
return result
print(subsets([1, 2, 3]))
# Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Bitmask DP: Traveling Salesman, Partition to K Equal Sum Subsets -- state is a bitmask of used elements.
Common Recipes
- Get ith bit:
(n >> i) & 1 - Set ith bit:
n | (1 << i) - Clear ith bit:
n & ~(1 << i) - Toggle ith bit:
n ^ (1 << i) - Lowest set bit:
n & (-n) - Clear lowest set bit:
n & (n - 1) - Check even/odd:
n & 1
Let's implement these common operations:
def bit_operations_demo(n, i):
print(f"Original number: {n} (binary: {bin(n)})")
print(f"Get bit {i}: {(n >> i) & 1}")
set_bit = n | (1 << i)
print(f"Set bit {i}: {set_bit} (binary: {bin(set_bit)})")
clear_bit = n & ~(1 << i)
print(f"Clear bit {i}: {clear_bit} (binary: {bin(clear_bit)})")
toggle_bit = n ^ (1 << i)
print(f"Toggle bit {i}: {toggle_bit} (binary: {bin(toggle_bit)})")
lowest_set = n & -n
print(f"Lowest set bit: {lowest_set} (binary: {bin(lowest_set)})")
clear_lowest = n & (n - 1)
print(f"Clear lowest set bit: {clear_lowest} (binary: {bin(clear_lowest)})")
is_even = (n & 1) == 0
print(f"Is even: {is_even}")
bit_operations_demo(13, 1) # 13 = 1101 in binary
When to Use Bit Manipulation
Use it when the problem explicitly involves binary representations, you need O(1) space for a problem that seems to require O(n) (Single Number), or you need to represent small sets as bitmasks. Otherwise, hash maps or sorting are usually simpler.
Bit manipulation is particularly useful in:
- Space optimization: When you need to track presence/absence of elements and the number of elements is small (≤ 32 or ≤ 64).
- Performance-critical code: Bit operations are among the fastest operations a CPU can perform.
- Low-level programming: Device drivers, graphics programming, and compression algorithms often use bit manipulation.
- Competitive programming: Problems with constraints that suggest bitmask solutions.
Practice Problems
XOR tricks:
- Single Number
- Single Number III
- Missing Number
Bit counting: 4. Number of 1 Bits 5. Counting Bits 6. Hamming Distance
Basic operations: 7. Power of Two 8. Reverse Bits
Bitmask: 9. Subsets (bitmask approach) 10. Letter Case Permutation
Let's implement the Hamming Distance problem as an example:
def hammingDistance(x, y):
# XOR gives 1 where bits differ
xor_result = x ^ y
# Count the number of 1 bits
distance = 0
while xor_result:
xor_result &= (xor_result - 1)
distance += 1
return distance
print(hammingDistance(1, 4)) # 1 = 0001, 4 = 0100, output: 2
Check the CodeJeet dashboard for bit manipulation problems by company. They appear at Apple, Amazon, and Google.