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.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the most important XOR trick for coding interviews?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The most useful XOR trick: XOR of a number with itself is 0, and XOR with 0 is the number unchanged. This means XOR-ing all elements cancels duplicates and isolates unique elements. LC 136 (Single Number): XOR all elements – every duplicate cancels, the unique element remains. For two unique numbers (LC 260): XOR all to get a^b, find any differing bit with a&(-a), split elements into two groups by that bit, XOR each group separately to get a and b individually.”}},{“@type”:”Question”,”name”:”How does n & (n-1) work and what problems does it solve?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”n & (n-1) clears the lowest set bit of n. Intuition: subtracting 1 from n flips all bits from the lowest set bit downward; AND with n cancels them. Applications: (1) Check if n is a power of 2: n > 0 and n & (n-1) == 0 (power of 2 has exactly one set bit). (2) Count set bits in O(k) where k = number of set bits: while n: count += 1; n &= n-1. (3) Iterate over all set bits: while mask: process(mask & -mask); mask &= mask-1. LC 191, 231, 338 all use this trick.”}},{“@type”:”Question”,”name”:”How do you enumerate all subsets of a bitmask?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”To enumerate all non-empty subsets of mask: start with sub = mask, then iterate sub = (sub-1) & mask until sub reaches 0. The expression (sub-1) & mask efficiently finds the next smaller submask. This O(3^n) total complexity across all masks is optimal for bitmask DP. Use case: bitmask DP where you need to consider all ways to split a set into two subsets (LC 1723, TSP). For the full powerset of n elements: iterate mask from 0 to (1<<n)-1, extract elements where bit i is set.”}},{“@type”:”Question”,”name”:”Why does Python require special handling for bit problems involving negative numbers?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Python integers have arbitrary precision – there is no 32-bit overflow. In problems like LC 371 (Sum Without +) or LC 190 (Reverse Bits) that assume 32-bit integers: use mask = 0xFFFFFFFF to simulate 32-bit truncation. After computation, check if the result exceeds 0x7FFFFFFF (maximum positive 32-bit int); if so, interpret as negative: return ~(result ^ mask). C/Java get overflow for free; Python requires explicit masking. This is a common source of wrong answers when porting solutions between languages.”}},{“@type”:”Question”,”name”:”What is the bit counting DP trick for LC 338?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”LC 338 asks for the number of set bits in every integer from 0 to n. Brute force: O(n log n). Optimal DP: dp[i] = dp[i >> 1] + (i & 1). Intuition: right-shifting i by 1 is equivalent to integer division by 2, which we already computed. The last bit (i & 1) is either 0 or 1. So dp[i] = popcount(i//2) + last_bit. This gives O(n) time and O(n) space. The recurrence works because every number i is either even (dp[i] = dp[i//2]) or odd (dp[i] = dp[i//2] + 1).”}}]}
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.