Bit Manipulation: The Core Idea

A list holds a million numbers. Every number appears twice, except one. Find it. The obvious answer is a set: add a number the first time you see it, remove it the second time, and the one left at the end is the answer. That works in O(n) time. But the set can hold up to half a million entries at once. Measured in Python, the set version of this exact problem peaked at about 17 MB of extra memory and took 0.17 seconds.

There is a solution that uses no extra memory at all and ran in 0.03 seconds on the same list: combine every number with XOR, one after another. The pairs cancel to zero, and the loner is what remains. It is a four-line loop.

That is the whole appeal of bit manipulation. Some problems are secretly about the binary form of numbers, and once you look at the bits, a data structure disappears. The pattern is narrow — it solves a small family of problems very well and almost nothing else — so the job in an interview is to recognise that family quickly.

Numbers are rows of switches

A computer stores every integer as a row of bits, each 0 or 1. Each position is worth a power of two, counted from the right and starting at position 0. So 13 is 1101 in binary: 8 + 4 + 0 + 1.

A bitwise operator works on each position separately. The result at position 0 depends only on the two bits at position 0. Nothing carries from one position to the next. That is the big difference from +, where 1 + 1 in one column pushes a carry into the next.

How to recognise it

Five signals in a problem statement point here:

• Arithmetic is banned. "Add two integers without using + or -." The only tools left are bit operators.
• Everything is paired except one. "Every element appears twice except one." Also "three times except one", or "two elements appear once". This is the XOR family.
• Subsets of a small set. With n items, there are 2ⁿ subsets, and each one matches one n-bit number. A constraint like n ≤ 20 is the tell: 2²⁰ is about a million, a loop you can afford.
• The bits themselves are the question. "Count the 1 bits." "Reverse the bits of a 32-bit integer." "Is n a power of two?"
• "O(1) extra space" in a problem that a hash set would solve easily.

A quick test: if the numbers could be replaced by strings and the problem would still make sense, it is not a bit problem. The binary form must matter.

The six operators

AND, OR and XOR each combine two bits. Here are all three truth tables in one:

Read them as short questions. AND: are both on? OR: is either on? XOR: are they different? The other three operators take one number:

• NOT (~) flips every bit. For any integer in Python, ~n equals -n - 1, so ~5 is -6.
• Left shift (<<) moves every bit left and fills with zeros. n << k equals n × 2ᵏ.
• Right shift (>>) moves every bit right and drops the lowest bits. n >> k equals n // 2ᵏ.

Now apply them to two real numbers, a = 172 and b = 106, column by column:

Check three rows without binary. a << 1 should be 172 × 2 = 344. a >> 1 should be 172 ÷ 2 = 86. And OR minus AND should equal XOR: 238 − 40 = 198. That last one holds because OR counts every column where either bit is on, AND counts the columns where both are, and XOR is exactly the difference. Every value in this table was printed by Python.

How it works: the XOR properties

Two facts about XOR solve a whole family of problems, and both come straight from the truth table:

1. x ^ x = 0. Every column holds two equal bits, and XOR of equal bits is 0. A value XOR-ed with itself disappears.
2. x ^ 0 = x. Every bit XOR-ed with 0 stays the same. Zero is the "do nothing" value.

Two more facts make them useful. XOR is commutative (a ^ b = b ^ a) and associative ((a ^ b) ^ c = a ^ (b ^ c)). So a chain of XORs gives the same result in any order. That means you can mentally move equal values next to each other:

4 ^ 1 ^ 2 ^ 1 ^ 2= 4 ^ (1 ^ 1) ^ (2 ^ 2)     reorder: allowed, because order does not matter= 4 ^ 0 ^ 0                 fact 1= 4                         fact 2

The code never reorders anything. It just XORs from left to right, and the maths guarantees the same answer. This is the invariant behind every XOR solution: after processing any prefix of the input, the running value is the XOR of the values that have appeared an odd number of times so far. At the end, pairs have appeared an even number of times and vanished.

A useful way to hold it: XOR is its own undo. a ^ b ^ b gives back a. Adding with + needs - to undo it; XOR undoes itself. And XOR never produces a value wider than its inputs, so, unlike a running sum, it cannot overflow.

The template: the standard tricks

Almost every bit solution is built from these one-liners.

1def get_bit(n: int, i: int) -> int:2    """Return bit i of n (0 or 1)."""3    return (n >> i) & 1456def set_bit(n: int, i: int) -> int:7    return n | (1 << i)          # force bit i on8910def clear_bit(n: int, i: int) -> int:11    return n & ~(1 << i)         # force bit i off121314def toggle_bit(n: int, i: int) -> int:15    return n ^ (1 << i)          # flip bit i161718def drop_lowest_set_bit(n: int) -> int:19    return n & (n - 1)           # 44 (101100) -> 40 (101000)202122def lowest_set_bit(n: int) -> int:23    return n & -n                # 12 (1100) -> 4 (0100)242526def is_power_of_two(n: int) -> bool:27    return n > 0 and (n & (n - 1)) == 0

Line by line:

• The mask 1 << i is a number with only bit i on. Every single-bit operation uses it.
• get_bit slides bit i down to position 0, then & 1 throws away everything else.
• set_bit uses OR: OR with 1 forces a 1, OR with 0 changes nothing. So only bit i is touched.
• clear_bit uses ~(1 << i), which is 1 everywhere except position i. AND with it keeps every bit except bit i. Check it: n = 1101, i = 2. The mask is 0100, its NOT is 1011, and 1101 & 1011 = 1001. Bit 2 is cleared, the rest survive.
• toggle_bit uses XOR: XOR with 1 flips, XOR with 0 keeps.
• n & (n - 1) removes the lowest 1 bit. Derive it rather than memorise it. Take n = 44 = 101100. Subtracting 1 borrows through the trailing zeros: 101011. The lowest 1 became 0, every 0 below it became 1, and everything above it is untouched. AND the two: above, the bits agree and survive; at and below the lowest 1, one side is always 0. Result: 101000 = 40.
• n & -n keeps only the lowest 1 bit. In two's complement, -n equals ~n + 1. For 12 = 1100, ~n is 0011 and adding 1 carries up to 0100. AND with n leaves 0100 = 4. One trick removes the lowest bit, the other isolates it.
• is_power_of_two: a power of two has exactly one 1 bit, so removing it leaves 0. The n > 0 guard matters because 0 also gives 0 & -1 == 0.

Python's integers have no width

Most bit-manipulation material is written for C or Java, where an int is exactly 32 bits. Python integers are different: they grow as large as needed, and a negative number behaves as if it had infinitely many 1 bits on the left. That changes several results you might expect:

Two consequences bite in interviews. First, a loop like while n: n >>= 1 never ends on a negative number, because -1 >> 1 is still -1. Second, any problem that says "32-bit" expects wrap-around that Python never does.

The fix is a mask. x & 0xFFFFFFFF keeps the low 32 bits and gives a non-negative number between 0 and 4,294,967,295. When you need to read that pattern back as a signed 32-bit value, convert it:

1MASK32 = 0xFFFFFFFF234def to_signed32(x: int) -> int:5    """Read the low 32 bits of x as a signed 32-bit integer."""6    x &= MASK327    return x - (1 << 32) if x & (1 << 31) else x

So -5 & MASK32 is 4294967291 (0xFFFFFFFB), and to_signed32(0xFFFFFFFB) gives back -5. Mask whenever the problem fixes a width; leave numbers alone when it does not.

Variants: the forms it takes

Complexity

On fixed-width numbers, each operator is one machine instruction: O(1). A loop over the bits of a 32-bit number costs O(32), which is O(1) but worth naming, since interviewers like to hear "O(w) where w is the word size". A loop driven by n & (n - 1) runs once per set bit, which can be far fewer.

Python adds one honest caveat: its integers are arrays of 30-bit chunks, so an operation on a number with thousands of bits costs time in proportion to its length. For numbers that fit in 64 bits, treat every operator as O(1). For subset enumeration, the cost is dominated by the 2ⁿ masks, not the operators: O(n × 2ⁿ).

Where it goes wrong

Four failures cover almost every bit bug, and three of them depend on the language.

1. Operator precedence. In C, C++, Java and JavaScript, == binds tighter than &. So n & 1 == 0 means n & (1 == 0), which is n & 0, which is always 0 — in C and JavaScript it is silently false for every n, and in Java it does not compile. Python is the opposite: its bitwise operators bind tighter than comparisons, so n & 1 == 0 happens to work. Python's trap is different: shifts bind tighter than &, and + binds tighter than shifts. So a & b << 1 means a & (b << 1), not (a & b) << 1. That exact line is the carry in Sum of Two Integers. The fix is the same in every language: parenthesise every bitwise expression.

2. Right shifts of negative numbers. Python's >> and Java's >> copy the sign bit in, so a negative number never shifts down to 0. Java also has >>>, which fills with zeros; Python has no such operator. Mask first, or loop a fixed number of times.

3. Python's missing width. Covered above. ~n is -n - 1, not a 32-bit flip, and no value ever wraps around. Mask with 0xFFFFFFFF when the problem says 32 bits.

4. Off-by-one in positions. Bits are numbered from 0, so "the third bit" is 1 << 2. A 32-bit value has positions 0 to 31. And shifting by the full width behaves differently everywhere: 1 << 32 is undefined in C, is 1 in Java (the shift count wraps to 0), and is 4294967296 in Python.