An integer is a row of switches. Three tricks cover most interview questions: XOR cancels pairs, x & (x - 1) turns off the lowest switch, and a mask is a set you can test in one step.
Bit questions look like puzzles, but they reward a short list of facts rather than cleverness. Learn the operators, learn the three tricks, and learn the one Python-specific trap: Python integers have no fixed width, so negative numbers need a 32-bit mask before they behave like the numbers in a C or Java answer.
+”, “in O(1) memory”. A small n (20 or less) with “every subset” is the other tell: each subset fits in one integer.+”, “divide without /”. Build it from XOR, AND and shifts.x ^ x == 0 and x ^ 0 == x. XOR is also order-free, so XOR-ing a whole list leaves only the values that appear an odd number of times.x & (x - 1) drops the lowest set bit. Subtracting 1 flips the lowest 1 to 0 and every 0 below it to 1. AND-ing with the original clears all of those. Loop it, and the loop runs once per set bit.i on means “item i is in”. Union is |, intersection is &, membership is mask >> i & 1. All O(1).Reading the figure. Each square is one bit, highest bit on the left. Left: the red rows are a pair, and they cancel, so only the blue 3 survives. Middle: amber bits are the ones that subtracting 1 flipped. AND keeps neither, so the red bit is cleared. Right: bit i on means item i is in the set.
Two quick consequences are worth having ready. x & (x - 1) == 0 for a positive x means x is a power of two, because it had exactly one set bit. And x & -x isolates the lowest set bit, which is the move behind Fenwick trees.
a & b — AND. 1 only where both are 1. Use it to test or clear bits.a | b — OR. 1 where either is 1. Use it to set bits.a ^ b — XOR. 1 where they differ. Use it to toggle bits or cancel pairs.~a — NOT. In Python this is -a - 1, because the integer is treated as infinitely sign-extended.a << k — shift left. Same as a * 2**k. Never overflows in Python.a >> k — shift right. Same as a // 2**k, so it rounds toward minus infinity for negatives.(a >> i) & 1 reads bit i. a | (1 << i) sets it. a & ~(1 << i) clears it. a ^ (1 << i) flips it.bin(a), a.bit_count() (3.10+) and a.bit_length() are the built-ins to name.&, which binds tighter than ^, which binds tighter than |. Comparisons bind looser than all of them. So x & 1 == 0 works in Python, unlike in C. Add the brackets anyway. The reader should not have to know.In C or Java an int is 32 bits, and -1 is thirty-two 1s. In Python an integer has no width. -1 behaves as if it had infinitely many 1s to the left. Any loop that shifts a negative number right until it reaches zero never ends, because -1 >> 1 is still -1.
& 0xFFFFFFFF. 0xFFFFFFFF is thirty-two 1 bits. AND-ing with it keeps the low 32 bits and drops the infinite sign bits, so -1 & 0xFFFFFFFF is 4294967295, the same bit pattern Java would hold. Now the value is a finite, non-negative number and loops end. To turn a 32-bit pattern back into a signed Python int, check bit 31. If it is set, the number was negative: ~(x ^ 0xFFFFFFFF) restores it.MASK = 0xFFFFFFFF # 32 one-bits: keeps only the low 32 bits
MAX_INT = 0x7FFFFFFF # 31 one-bits: the largest positive signed 32-bit value
pattern = -1 & MASK # 4294967295: thirty-two 1s, as Java stores -1
signed = pattern if pattern <= MAX_INT else ~(pattern ^ MASK) # back to -1
def xor_all(values: list[int]) -> int:
"""XOR of every value. Pairs cancel, so odd-count values survive.
Example:
>>> xor_all([3, 5, 3])
5
"""
# 0 is the XOR identity: 0 ^ x == x, so starting here changes nothing.
acc = 0
# Invariant: acc is the XOR of every value before this pass.
for value in values:
acc ^= value # a second copy of value cancels the first
return acc
def set_bit_positions(x: int) -> list[int]:
"""Positions of the 1 bits in a non-negative x, lowest first.
Example:
>>> set_bit_positions(0b10110)
[1, 2, 4]
"""
positions: list[int] = []
# Invariant: x holds the set bits not yet reported. Each pass removes one.
# The loop stops at 0: no set bits left.
while x != 0:
lowest = x & -x # -x flips all bits above the lowest 1
# bit_length() - 1: a number with one set bit at position p has length p + 1
positions.append(lowest.bit_length() - 1)
x &= x - 1 # - 1 turns the lowest 1 into 0
return positions
Reading the figure. Each row is one pass of the while loop. The small numbers on top are bit positions. The amber bit is the lowest 1, which x & -x isolates. Its position joins the green list. Then x &= x - 1 clears it, giving the next row.
The loop runs once per set bit, not once per bit position. On a sparse number that is much faster than checking all 32 positions.
def subsets_by_mask(items: list[str]) -> list[list[str]]:
"""Every subset of items. Bit i of mask means items[i] is in.
Example:
>>> subsets_by_mask(["a", "b"])
[[], ['a'], ['b'], ['a', 'b']]
"""
n = len(items)
result: list[list[str]] = []
# 1 << n is 2 ** n: one mask per subset, from 0 (empty) to 2 ** n - 1 (all).
for mask in range(1 << n):
# (mask >> i) & 1 reads bit i. The 1 keeps only that one bit.
result.append([items[i] for i in range(n) if (mask >> i) & 1])
return result
Reading the figure. Each card is one value of mask. The letters above the bits say which item each bit stands for. Green bits are on, so those items are in the subset on the right. Notice that the masks are just the numbers 0 to 7 in order, and together they cover all 8 subsets.
This is the iterative twin of backtracking subsets. It only works while 2 ** n is small, so about n ≤ 20.
0xFFFFFFFF first.^ with power. 2 ^ 3 is 1, not 8. Power is **.~x as “flip 32 bits”. In Python ~5 is -6. To flip only the low 32 bits, use x ^ 0xFFFFFFFF.1 << n - 1 is 1 << (n - 1), because - binds tighter than <<. Bracket every bit expression.bin(x).count("1") on a negative. bin(-5) is '-0b101', which counts 2, not the 31 a 32-bit answer expects.Every value in a non-empty array appears exactly twice, except one value that appears once. Find it in O(n) time and O(1) extra space.
A hash set works but costs O(n) space. XOR is the O(1) answer. XOR is commutative and associative, so the order does not matter. Each pair meets itself and becomes 0. The single value XOR 0 is itself.
def single_number(nums: list[int]) -> int:
"""The one value that appears once when every other appears twice.
Args:
nums: Non-empty integers. Exactly one value appears once.
Returns:
The value that appears once.
Example:
>>> single_number([4, 1, 2, 1, 2])
4
>>> single_number([-3, 7, 7])
-3
"""
# Start at 0: XOR with 0 changes nothing, so 0 is the neutral start.
result = 0
# Invariant: result is the XOR of every number seen so far. Pairs seen
# twice have cancelled to 0, so result holds only the unpaired ones.
for value in nums:
result ^= value
return result
nums = [4, 1, 2, 1, 2], in binary:
result = 000.100.101.111.110. The first 1 is cancelled.100. The first 2 is cancelled. Answer 4.Reading the figure. Each row is result after one XOR, with place values 4, 2, 1 on top. Blue squares are 1 bits. A red square is a bit that a second copy just switched back to 0. The green row is the answer.
mod 3 instead, and mask to 32 bits to rebuild a negative answer.a ^ b. Split the array on any set bit of that, and XOR each half.Return the number of 1 bits in the 32-bit binary form of an integer. This count is also called the Hamming weight.
Checking all 32 positions works. The better answer uses n & (n - 1), which clears one set bit per pass. The loop runs exactly as many times as there are 1s. Mask the input with 0xFFFFFFFF first, so a negative input counts its 32-bit pattern and the loop still ends.
def hamming_weight(n: int) -> int:
"""Number of 1 bits in the 32-bit two's complement form of n.
Args:
n: Any integer. Negatives are read as their 32-bit pattern.
Returns:
The count of set bits, from 0 to 32.
Example:
>>> hamming_weight(11)
3
>>> hamming_weight(-1)
32
"""
# 0xFFFFFFFF is thirty-two 1s. AND keeps the low 32 bits and drops
# Python's infinite sign bits, so -1 becomes 32 ones and the loop ends.
n &= 0xFFFFFFFF
count = 0 # no set bits counted yet
# Invariant: count + (set bits left in n) == the answer.
# The loop stops at 0: no set bits left.
while n != 0:
n &= n - 1 # - 1 flips the lowest 1 to 0, AND clears it
count += 1 # one bit removed, so one more counted
return count
n = 11, binary 1011:
1011 & 1010 = 1010, count 1.1010 & 1001 = 1000, count 2.1000 & 0111 = 0000, count 3. Loop ends. Answer 3.Reading the figure. Each block is one pass. The amber bit is the lowest 1 of n. Subtracting 1 flips it and every 0 below it. After the AND, that bit is the red square, and the green row is the new n. Three passes means three 1 bits.
n = 0: the loop never runs. Answer 0.-1 becomes -2, then -4, then -8. It never reaches 0, so the loop runs forever. The mask is not optional.(n & 0xFFFFFFFF).bit_count() on Python 3.10+. Name it, then write the loop.a and b is hamming_weight(a ^ b). XOR marks the bits that differ.n & (n - 1) clears the lowest set bit, so the loop runs once per 1 bit. I mask with 0xFFFFFFFF first, because Python ints have no width and a negative would never reach zero.”Given n, return a list ans of length n + 1 where ans[i] is the number of 1 bits in i. Aim for O(n), not O(n log n).
This is dynamic programming on bits. Shifting i right by one drops its last bit and gives i >> 1, a smaller number whose count is already known. The dropped bit is i & 1. So ans[i] = ans[i >> 1] + (i & 1). Each cell costs O(1).
def count_bits(n: int) -> list[int]:
"""Set-bit counts for every integer from 0 to n.
Args:
n: The largest integer to count, n >= 0.
Returns:
A list of length n + 1. Entry i is the number of 1 bits in i.
Example:
>>> count_bits(5)
[0, 1, 1, 2, 1, 2]
"""
# n + 1 slots so index n exists: slots 0..n. Slot 0 stays 0, the base
# case, because 0 has no set bits.
ones = [0] * (n + 1)
# Start at 1: slot 0 is the base case. n + 1 so n itself is included.
# Invariant: ones[0..i-1] are final. i >> 1 < i, so it is ready.
for i in range(1, n + 1):
# i >> 1 drops the last bit (shift by 1 = halve). i & 1 is that
# dropped bit: 1 if i is odd, 0 if even.
ones[i] = ones[i >> 1] + (i & 1)
return ones
i = 1 (1): ones[0] + 1 = 1.i = 2 (10): ones[1] + 0 = 1.i = 3 (11): ones[1] + 1 = 2.i = 4 (100): ones[2] + 0 = 1.i = 5 (101): ones[2] + 1 = 2. Result [0, 1, 1, 2, 1, 2].Reading the figure. Each column is one i. Blue arrows point from i back to i >> 1, a smaller cell that is already filled. The amber digit is the last bit, the one the shift drops. So each green count is the count at the arrow tip plus the amber digit.
n = 0: the loop never runs. Result [0].ones[i] = ones[i & (i - 1)] + 1. Drop the lowest set bit, then add it back. Offer it as the second answer.hamming_weight on each i. That is O(n log n). Say why the DP is better: each answer reuses a smaller one.i & 1. So each entry is one lookup plus one bit. That makes it a DP over the integers.”Return a + b without using the + or - operators. Inputs are 32-bit signed integers, and negatives must work.
Binary addition splits into two parts. a ^ b is the sum of each column ignoring carries. (a & b) << 1 is the carries, each moved one column left. Add those two the same way, and repeat until no carry is left. In C this ends in at most 32 rounds, because a carry falls off the top. In Python it does not fall off, so a negative input loops forever. The fix is to mask every step with 0xFFFFFFFF to fake a 32-bit register, then turn the result back into a signed int.
def get_sum(a: int, b: int) -> int:
"""a + b using only bit operations, with 32-bit signed wraparound.
Args:
a: A 32-bit signed integer.
b: A 32-bit signed integer.
Returns:
Their sum as a signed integer.
Example:
>>> get_sum(1, 2)
3
>>> get_sum(-2, 3)
1
>>> get_sum(-5, -7)
-12
"""
mask = 0xFFFFFFFF # 32 one-bits: keeps only the low 32 bits
max_int = 0x7FFFFFFF # 31 one-bits: largest positive signed 32-bit
# Drop Python's infinite sign bits. Negatives become 32-bit patterns.
a &= mask
b &= mask
# Invariant: a + b (as 32-bit numbers) equals the true answer.
# b is the carry. It moves 1 column left each pass, so after at most
# 32 passes the mask pushes it out and it becomes 0.
while b != 0:
# Columns where both are 1 make a carry. << 1 moves it to the next
# column. & mask drops a carry out of bit 31, like real hardware.
carry = ((a & b) << 1) & mask
a = (a ^ b) & mask # column sums with no carry
b = carry # the carries still to add
# Bit 31 clear: a is already the right non-negative value.
if a <= max_int:
return a
# Bit 31 set: a is a negative number's pattern. a ^ mask flips the low
# 32 bits. ~ then flips every bit, so the low 32 come back and the
# infinite upper bits become 1s, which is how Python stores a negative.
return ~(a ^ mask)
a = 5 (0101), b = 3 (0011):
(0001) << 1 = 0010, sum 0110.(0010) << 1 = 0100, sum 0100.(0100) << 1 = 1000, sum 0000.0, sum 1000. Loop ends. Answer 8.-2 + 3, -2 becomes 0xFFFFFFFE. The carry runs up to bit 32, the mask drops it, and a ends at 1.Reading the figure. Each row shows a and b after one pass. Blue bits are the sum so far, without carries. Amber bits are the carries, already moved one column left. Watch the single amber 1 climb from column 1 to column 3. When b is all zeros, the green a is the answer.
get_sum(-1, 1) loops forever in Python. Say this before the interviewer finds it.0x7FFFFFFF + 1 wraps to -2147483648, as Java would. Ask whether that is wanted or whether Python's true sum is.get_sum(a, ~b + 1) in a fixed-width language, two's complement negation. In Python, use get_sum(a, get_sum(~b, 1)) to stay inside the rules.~(a ^ mask) if bit 31 is set.”x ^ x == 0, x ^ 0 == x, and order does not matter.x & (x - 1) drops the lowest set bit. A loop on it runs once per 1 bit. x & -x keeps only that bit.| for union, & for intersection, (mask >> i) & 1 for membership.0xFFFFFFFF before shifting or looping on a negative.~(x ^ 0xFFFFFFFF).Pattern 20, K-way Merge and Two Heaps, goes back to heaps. It covers the two heap moves the top-K page only names: merging many sorted lists, and keeping a running median.