Core Bit Operations Reference
# Fundamental bit tricks
n & (n-1) # clear lowest set bit (check power of 2: n & (n-1) == 0)
n & (-n) # isolate lowest set bit (lowbit)
n | (n+1) # set lowest unset bit
n ^ n # 0 (XOR with itself)
n ^ 0 # n (XOR with 0)
a ^ b ^ a # b (XOR is commutative and associative)
# Test, set, clear, toggle bit at position i
(n >> i) & 1 # test bit i
n | (1 << i) # set bit i
n & ~(1 << i) # clear bit i
n ^ (1 << i) # toggle bit i
# Count set bits (popcount)
bin(n).count('1') # Python built-in
n.bit_count() # Python 3.10+
# Manual: n & (n-1) loop counts in O(set_bits)
# Swap without temp
a ^= b; b ^= a; a ^= bXOR Patterns
# Single Number (LC 136): find the one number not duplicated
def single_number(nums: list[int]) -> int:
result = 0
for n in nums:
result ^= n
return result
# XOR of all nums: duplicates cancel out (a^a=0), single remains
# Single Number III (LC 260): two non-duplicated numbers
def single_number_iii(nums: list[int]) -> list[int]:
xor = 0
for n in nums: xor ^= n # xor = a ^ b
# Find any differing bit between a and b
diff_bit = xor & (-xor) # lowest set bit
# Split nums into two groups by this bit, XOR each group
a = b = 0
for n in nums:
if n & diff_bit:
a ^= n
else:
b ^= n
return [a, b]
# Find missing and repeated number using XOR
def find_error_nums(nums: list[int]) -> list[int]:
xor = 0
n = len(nums)
for i, num in enumerate(nums):
xor ^= num ^ (i + 1) # XOR with expected 1..n
# xor = repeated ^ missing
diff_bit = xor & (-xor)
a = b = 0
for i, num in enumerate(nums):
if num & diff_bit: a ^= num
else: b ^= num
if (i+1) & diff_bit: a ^= (i+1)
else: b ^= (i+1)
for num in nums:
if num == a: return [a, b]
return [b, a]Bitmask Enumeration of Subsets
# Enumerate all subsets of n elements using bitmasks
def all_subsets(nums: list[int]) -> list[list[int]]:
n = len(nums)
result = []
for mask in range(1 <> i & 1]
result.append(subset)
return result
# Enumerate all non-empty subsets of a given mask (submask enumeration)
def submasks(mask: int):
sub = mask
while sub > 0:
yield sub
sub = (sub - 1) & mask # next submask of mask
# This is O(3^n) total across all masks (each bit is in / out / not in mask)
# Maximum AND of two subsets (greedy from MSB)
def max_and(nums: list[int]) -> int:
result = 0
for bit in range(30, -1, -1):
candidate = result | (1 <= 2:
result = candidate
return resultBit-Based Interval and Range Problems
# Count bits for 0..n (LC 338): DP with bit trick
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)
# dp[i] = dp[i//2] + last bit of i
return dp
# Reverse bits of a 32-bit integer (LC 190)
def reverse_bits(n: int) -> int:
result = 0
for _ in range(32):
result = (result <>= 1
return result
# Sum of two integers without + (LC 371)
def get_sum(a: int, b: int) -> int:
mask = 0xFFFFFFFF # 32-bit mask
while b & mask:
carry = (a & b) << 1
a = a ^ b
b = carry
# Handle Python negative numbers (no fixed-width overflow)
return a if a <= 0x7FFFFFFF else ~(a ^ mask)Interview Strategy for Bit Problems
Key patterns to recognize: (1) XOR to find unique elements – when every other element appears twice, XOR cancels duplicates. (2) n & (n-1) removes lowest set bit – use to check power of 2, or iterate over set bits in O(k) instead of O(32). (3) Bitmask DP – when n is small (n >1] + (i&1) avoids O(32) popcount per number. Common interview mistakes: forgetting Python has arbitrary-precision integers (no overflow unlike C/Java – need explicit masking for LC 371); confusing arithmetic right shift (>> in Java/C fills with sign bit) vs logical right shift. In Python >> is always arithmetic but integers are unbounded.
Meta coding interviews include advanced bit manipulation. See common patterns for Meta interview: bit manipulation and low-level coding problems.
Coinbase interviews include bit-level operations relevant to cryptography. Review patterns for Coinbase interview: bit manipulation and cryptography problems.
LinkedIn coding interviews test bit manipulation. See common patterns for LinkedIn interview: bit manipulation and integer problems.