Bit Manipulation · bigonotes

Every integer is a row of bits, and a handful of operators work on all of them at once. Bit problems look like puzzles, but nearly all of them reuse four or five identities. Learn those and the problems become short loops. Python adds one twist, because its integers never overflow.

The idea#

These are the operators and what each one is good for:

Operator	Python	Use it to
AND	`a & b`	test or clear bits: `n & 1` reads the lowest bit
OR	`a \| b`	set bits
XOR	`a ^ b`	flip bits; equal bits cancel
Left shift	`n << k`	multiply by $2^k$ , or move a bit into place
Right shift	`n >> k`	divide by $2^k$ , or bring bit `k` down to position 0

The identities that solve most problems follow from those rules:

n & (n - 1) drops the lowest set bit. Subtracting 1 flips the lowest 1 and every 0 below it, so the AND clears exactly that bit. Repeat until n is 0 to count the 1s.
n & -n keeps only the lowest set bit, and n > 0 and n & (n - 1) == 0 tests for a power of two, since a power of two has exactly one set bit.
XOR cancels pairs. x ^ x == 0 and x ^ 0 == x, and order doesn't matter. XOR everything together and every value that appears twice disappears.
Bits of i come from bits of i >> 1. i >> 1 is i without its last bit, so bits[i] = bits[i >> 1] + (i & 1). That turns counting bits for 0..n into a one-line DP.
Addition is XOR plus carry. a ^ b adds without carrying; (a & b) << 1 is the carry. Repeat until the carry is 0.
Reversing is shifting out and in. Take the lowest bit of n, push it onto the result from the right, shift n right, 32 times.

Python's integers are unbounded. In C or Java, a 32-bit int wraps around and negative numbers are stored in two's complement. In Python, -1 behaves as if it had infinitely many leading 1s, so loops that wait for a carry to reach 0 can run forever. Mask with 0xFFFFFFFF to keep 32 bits, and convert back at the end: if the result is above 0x7FFFFFFF, it represents a negative number, which is ~(x ^ 0xFFFFFFFF).

How to spot it#

These signals point to bit tricks:

The problem says "bits", "binary representation" or "32-bit unsigned integer".
Every element appears twice except one, or one number is missing from 0..n: XOR.
"Without using + or -": XOR and carry.
Count of 1s for every number up to n: the i >> 1 DP.
$O(1)$ extra space is required and the values are integers: a bit trick may replace a set.

Template#

The two loops below cover most of these problems: one walks the set bits, the other walks all 32 positions.

# walk only the set bits
count = 0
while n:
    n = n & (n - 1)      # drop the lowest set bit
    count += 1

# walk all 32 positions, lowest first
result = 0
repeat 32 times:
    bit = n & 1
    result = (result << 1) | bit
    n = n >> 1

For "everything appears twice except one", the template is a single fold: start at 0 and XOR in every value.

Pitfalls#

These are the mistakes that most often cost a correct answer.

Infinite loops on negatives. A carry loop for a + b with a negative number never ends in Python. Mask both values and the carry with 0xFFFFFFFF on every step.
Forgetting to convert back. A masked result above 0x7FFFFFFF stands for a negative number. Convert it with ~(x ^ 0xFFFFFFFF) before you return it.
Stopping early when reversing. Reversing needs all 32 iterations, even after n reaches 0, so leading zeros move into place.
Precedence. &, | and ^ bind more loosely than == and + in many languages, and more loosely than + in Python. Write (n & 1) == 1 and (a & b) << 1 with parentheses.
Using bin(n).count("1") blindly. It works for non-negative ints in Python, but it hides the idea an interviewer is asking about. Know the n & (n - 1) loop too.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Number of 1 Bits and Single Number.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Number of 1 Bits

Repeat n &= n - 1 and count the steps. The loop runs once per set bit, not once per position.

Hint: Counting Bits

Build the answers from 0 upward: bits[i] = bits[i >> 1] + (i & 1). The smaller number is always already filled in.

Hint: Reverse Bits

Run exactly 32 times: shift the result left, OR in n & 1, then shift n right. Don't stop when n becomes 0.

Hint: Missing Number

XOR every index 0..n with every value. Each present number cancels with its index, and only the missing one is left. The sum formula n * (n + 1) // 2 minus the array sum also works.

Hint: Single Number

XOR all the numbers together. Every pair cancels to 0, and the single number is what remains.

Hint: Sum of Two Integers

The sum without carries is a ^ b and the carry is (a & b) << 1. Repeat with those two until the carry is 0. In Python, mask with 0xFFFFFFFF each round and convert a result above 0x7FFFFFFF back to a negative number.

Key takeaways#

n & (n - 1) drops the lowest set bit; loop on it to count 1s.
XOR cancels pairs, so it finds the single or missing value in $O(1)$ space.
bits[i] = bits[i >> 1] + (i & 1) counts bits for every number up to n.
Addition without + is XOR for the sum and AND shifted left for the carry.
Python ints are unbounded: mask with 0xFFFFFFFF and convert back for 32-bit signed results.

Core idea#

A few bit identities solve most bit problems. Python ints are unbounded, so mask with 0xFFFFFFFF for 32-bit results.

Key points#

n & 1 reads the lowest bit. n >> 1 drops it.
n & (n - 1) drops the lowest set bit. Loop on it to count 1s.
XOR cancels pairs: x ^ x == 0, x ^ 0 == x, in any order.
Counting bits for 0..n: bits[i] = bits[i >> 1] + (i & 1).
Add without +: sum is a ^ b, carry is (a & b) << 1. Repeat until carry is 0.
Reverse: shift the result left, OR in n & 1, shift n right, 32 times.
A masked result above 0x7FFFFFFF is negative. Convert with ~(x ^ 0xFFFFFFFF).

Operators#

Operator	Use
`&`	test or clear bits
`\|`	set bits
`^`	flip bits, cancel pairs
`<<`, `>>`	multiply or divide by powers of 2, move bits

Template#

count = 0
while n:
    n = n & (n - 1)      # drop the lowest set bit
    count += 1

result = 0
repeat 32 times:
    result = (result << 1) | (n & 1)
    n = n >> 1

Pitfalls#

Carry loops on negatives never end in Python. Mask every step.
Forgetting to convert a masked result back to a signed int.
Stopping a reverse early. Run all 32 iterations.
Missing parentheses around &, | and ^.

Say it in an interview#

"XOR cancels every pair, so the single number is what's left."
"n & (n - 1) clears the lowest set bit, so the loop runs once per 1."