Bit manipulation questions look like puzzles, but there’s a small kit behind nearly all of them. If you know four single-bit operations, two identities built on n - 1 and -n, and what XOR does to a repeated value, you can solve the common interview set (Single Number, Missing Number, Number of 1 Bits, Power of Two, Counting Bits, Subsets) and explain why each answer works. The explanation is what gets marked. An interviewer who sees x & (x - 1) will almost always ask what it does to the binary digits.
The examples below are Python, with notes on JavaScript and Java where integer width changes the behaviour. Every output shown was produced by running the code.
A number as a row of switches
Bit i of a non-negative integer is the coefficient of 2^i in its binary form. 180 is 10110100: bits 2, 4, 5 and 7 are on. The expression 1 << i builds a mask with only bit i set, and the four basic operations combine that mask with n:
def get_bit(n, i): return (n >> i) & 1
def set_bit(n, i): return n | (1 << i)
def clear_bit(n, i): return n & ~(1 << i)
def toggle_bit(n, i): return n ^ (1 << i)
n = 180 # 0b10110100
print(f"{n:08b}", get_bit(n, 2), get_bit(n, 3))
print(f"{set_bit(n, 0):08b} {clear_bit(n, 7):08b} {toggle_bit(n, 2):08b}")10110100 1 0
10110101 00110100 10110000OR forces a bit on, AND with an inverted mask forces it off, and XOR flips it. Shifting n right and masking with 1 gives you a clean 0 or 1, which is nicer to return than n & (1 << i), a value that is either zero or 2^i. Candidates sometimes write if n & (1 << i) == 1, which is false for 180 and i = 2 because the AND produces 4, not 1. Compare against zero or shift first. Drop the parentheses in C or JavaScript and there’s a second bug, because == binds tighter than & there (Java rejects the mixed types outright). Python ranks comparisons below bitwise operators.
These four lines are the whole vocabulary for flag fields (Unix permission bits, feature flags packed into one integer) and for the subset masks later in this guide.
The two identities: n & (n - 1) and n & -n
Subtracting 1 from a number flips its lowest set bit to 0 and every zero below it to 1. The borrow runs through the trailing zeros until it finds a 1. Everything above that bit is untouched. So n & (n - 1) keeps the upper bits and wipes the lowest set bit:
n = 180
print(f"n {n:08b}")
print(f"n - 1 {n - 1:08b}")
print(f"n & (n-1) {n & (n - 1):08b}")
print(f"n & -n {n & -n:08b}")n 10110100
n - 1 10110011
n & (n-1) 10110000
n & -n 00000100The second line, n & -n, comes from two’s complement: -n equals ~n + 1. Inverting every bit and adding one produces a number that agrees with n only at the lowest set bit, so the AND isolates it. Here it’s 4, the bit at position 2.
Two classic problems fall out of the first identity. A power of two has exactly one bit set, so removing it leaves zero. And because each n & (n - 1) removes one set bit, looping until zero counts the set bits, the method usually credited to Brian Kernighan:
def is_power_of_two(x):
return x > 0 and x & (x - 1) == 0
def popcount(x):
count = 0
while x:
x &= x - 1 # drop the lowest set bit
count += 1
return count
print([x for x in range(-2, 70) if is_power_of_two(x)])
print(popcount(180), popcount(0), popcount(2**64 - 1), (180).bit_count())[1, 2, 4, 8, 16, 32, 64]
4 0 64 4The x > 0 guard matters. Zero passes x & (x - 1) == 0 because 0 & -1 is 0, and zero isn’t a power of two. Interviewers check for this edge case on purpose.
The popcount loop runs once per set bit, not once per bit position. For 180 that’s 4 iterations instead of 8. The worst case is still the full width, so say “O(number of set bits), at most O(w)” rather than claiming it’s always faster. In production code you’d call the built-in: int.bit_count() in Python 3.10+, Integer.bitCount in Java, __builtin_popcount in GCC. Mention that, then write the loop anyway, because the loop is what’s being tested.
XOR cancels whatever appears twice
XOR has three properties that make it useful: a ^ a == 0, a ^ 0 == a, and it’s commutative and associative, so order doesn’t matter. Fold XOR over a list and every value that appears an even number of times disappears. Watch the accumulator for [4, 1, 2, 1, 2]:
def single_number(nums):
acc = 0
for x in nums:
acc ^= x
print(f"^ {x} -> {acc:03b} ({acc})")
return acc
print(single_number([4, 1, 2, 1, 2]))^ 4 -> 100 (4)
^ 1 -> 101 (5)
^ 2 -> 111 (7)
^ 1 -> 110 (6)
^ 2 -> 100 (4)
4The middle values look meaningless (5, 7, 6), and that’s fine. The accumulator isn’t tracking anything readable mid-loop. It only becomes meaningful once each pair has been fully applied. That’s O(n) time and O(1) extra space, which is the point of the question. A hash set also works in O(n) time, but it needs O(n) memory, and the follow-up “can you do it without extra space?” is coming.
The same trick finds the missing value in 0..n when one number is absent. XOR every index and every value together, plus n itself. Each present number meets its own index and cancels; the missing one has no partner:
def missing_number(nums):
acc = len(nums)
for i, v in enumerate(nums):
acc ^= i ^ v
return acc
print(missing_number([3, 0, 1]), missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]))2 8The sum formula n(n+1)/2 - sum(nums) also works. In Python it’s equally good. In Java or C++ with 32-bit int, the sum can overflow for large n while the XOR version can’t, and that’s a fair point to raise.
Splitting into two groups with the lowest set bit
A harder variant: every number appears twice except two of them. Fold XOR and you get a ^ b, which isn’t either answer. But a ^ b is non-zero because a != b, so it has at least one set bit, and at that bit a and b differ. Isolate it with n & -n, then split the list on that bit. Each pair lands in the same group (equal numbers have equal bits), and a and b land in different groups, so XOR-ing one group gives one of them:
def two_singles(nums):
both = 0
for v in nums:
both ^= v # a ^ b, the pairs cancel
low = both & -both # a bit where a and b differ
a = 0
for v in nums:
if v & low:
a ^= v # only one single lands in this group
return sorted((a, both ^ a))
print(two_singles([1, 2, 1, 3, 2, 5]))
print(f"{3 ^ 5:03b} {(3 ^ 5) & -(3 ^ 5):03b}")[3, 5]
110 0103 ^ 5 is 110, and the lowest set bit is 010. Three has that bit, five doesn’t, so they separate. The code is short, but every line rests on a property you’ve already justified, so talk it through aloud.
Bitmasks as subsets
With k items, each integer from 0 to 2^k - 1 describes one subset: bit i says whether item i is in it. Counting through the integers enumerates every subset exactly once:
items = ["a", "b", "c"]
for mask in range(1 << len(items)):
print(f"{mask:03b}", [items[i] for i in range(len(items)) if mask >> i & 1])000 []
001 ['a']
010 ['b']
011 ['a', 'b']
100 ['c']
101 ['a', 'c']
110 ['b', 'c']
111 ['a', 'b', 'c']This is an alternative to recursive backtracking for the Subsets problem, and it’s the representation behind bitmask dynamic programming. In the travelling salesman DP, the state is “which cities have I visited” (a mask) plus “where am I now”, giving 2^n * n states. That’s why bitmask DP only fits small n: 20 items means about a million masks, and 30 means about a billion. If an interviewer gives you n <= 20 and a “choose any subset” flavour, that constraint is a hint to reach for masks.
Where integer width breaks the tricks
The identities above assume a fixed number of bits. Languages disagree about that, and this is where correct-looking answers fail.
Python integers are unbounded. A negative number behaves as if it had infinitely many leading 1 bits, so ~5 is -6 and -5 >> 1 is -3. The popcount loop never terminates on a negative input: x & (x - 1) keeps producing larger negative numbers instead of reaching zero. When a problem says “treat the input as a 32-bit integer”, mask first:
print(~5, -5 >> 1, bin(-5), -5 & 0xFFFFFFFF)
print(bin(-1 & 0xFFFFFFFF).count("1"))-6 -3 -0b101 4294967291
32JavaScript converts operands of &, |, ^, << and >> to 32-bit signed integers. 1 << 31 is -2147483648, 1 << 32 is 1 (the shift count is taken mod 32), and (2**32 + 5) | 0 is 5. Use >>> for an unsigned right shift (-16 >>> 1 is 2147483640), and switch to BigInt when you genuinely need more than 32 bits.
Java has fixed 32-bit int and 64-bit long. >> copies the sign bit and >>> fills with zeros, so a popcount loop that shifts right with >> on a negative number never ends. A classic slip is 1 << 40 on an int, which silently becomes 1 << 8; write 1L << 40.
Mention the width of your language unprompted; it shows you’ve debugged this kind of code.
Interview practice: popcounts for a whole range
Given n, return a list where position i holds the number of 1 bits in i, for every i from 0 to n. Calling popcount on each value costs O(n log n). Can you do it in O(n)?
Answer and reasoning
Reuse earlier answers. i & (i - 1) is i with its lowest set bit removed, so it’s smaller than i and has exactly one fewer 1 bit. Its count is already in the list:
def count_bits(n):
ones = [0] * (n + 1)
for i in range(1, n + 1):
ones[i] = ones[i & (i - 1)] + 1
return ones
print(count_bits(8))
print(count_bits(1000) == [i.bit_count() for i in range(1001)])[0, 1, 1, 2, 1, 2, 2, 3, 1]
TrueEach entry is one AND, one lookup and one addition, so the whole thing is O(n) time and O(n) space for the output. The second line checks the result against Python’s built-in for the first thousand values. An equally valid recurrence is ones[i] = ones[i >> 1] + (i & 1): shifting right drops the lowest bit, and i & 1 adds it back if it was a 1. Either way, the interviewer wants to hear that this is dynamic programming where the subproblem is chosen by a bit identity, and that you can say why i & (i - 1) is always smaller than i (it removes a set bit, so it can’t grow).
Related reading
- DSA interview questions and the DSA multiple-choice quiz
- Hash maps for frequency and membership problems, the extra-space alternative to XOR tricks
- Dynamic programming and state definition, for the counting-bits recurrence and bitmask DP
- Backtracking and safe pruning rules, the recursive way to enumerate subsets
- Python bitwise operations on integer types