Bit Manipulation Tricks

Every integer is already a compact array of bits, and the CPU’s bitwise instructions operate on all of them at once — no loop required. That makes bit manipulation one of the few genuinely $O(1)$-space, $O(1)$-time tools in the whole CP toolkit: checking membership, toggling a flag, finding the one odd-one-out in a list, or enumerating every subset of up to ~20 items all reduce to a handful of bitwise operations.

What you’ll learn

• Binary representation in Python — bin(), zero-padded formatting, and bit_length().
• The five core operators: AND, OR, XOR, NOT, and shifts, and what each one means bit-by-bit.
• The four bit-mask idioms: check, set, clear, and toggle a single bit.
• Two O(1) one-liners: the lowest set bit (x & -x) and counting set bits (x.bit_count()).
• XOR tricks — finding the one non-duplicate in a list, and swapping two variables without a temporary.
• Bitmask subset enumeration — looping over every subset of a small set by counting from 0 to 2^n - 1.

Visual intuition

A machine word is a row of bits, so the same stepper applies. Kernighan’s trick first — one iteration per set bit, not per bit:

bitsn &= n - 1 clears exactly the lowest set bitLC 191

1001021314150607

n156binary10011100count0

1def count_bits(n):2    count = 03    while n:4        n &= n - 1        # clears the LOWEST set bit5        count += 16    return count          # loops once per SET bit, not per bit

n156binary10011100

setupCounting set bits one position at a time takes 8 iterations here — 32 or 64 on a real word. Kernighan's trick takes one iteration per **set** bit instead, which for sparse values is far fewer.

Play‹›1/10⟲

n - 1 flips the lowest set bit to 0 and turns every zero below it into a 1, so ANDing clears that one bit and leaves everything above untouched. The same idiom answers 'is this a power of two' in a single test.

bitsEvery integer's bits ARE a subset2^n enumeration

000102

nums

705132

mask0 = 000subset{}found0

1def subsets(nums):2    n = len(nums)3    for mask in range(1 << n):        # 0 .. 2^n - 14        subset = [nums[i] for i in range(n)5                  if mask & (1 << i)]  # bit i set ⇒ take nums[i]6        yield subset

n3subsets8

setupThere are 2^3 subsets and 2^3 numbers representable in 3 bits, so the two can be put in correspondence: treat each integer's bits as "take this element or not". That turns recursion into a flat loop, which is why bitmask enumeration is the standard trick for small n.

Play‹›1/10⟲

There are 2^n subsets and 2^n values representable in n bits, so the two correspond exactly. That correspondence is what makes bitmask DP possible: a subset becomes an integer, so it can index an array.

The cue

You are looking at bit manipulation when…

• The problem is about the binary representation: count set bits, reverse the bits, find the single number, check for a power of two — LC 191, 190, 136, 231, 338.
• You need a set of up to ~20 items as a state you can compare, hash, or index — that is a bitmask, and it is the doorway to bitmask DP and subset enumeration.
• The constraint says $O(1)$ space where a hash map or a boolean array is the obvious answer.
• Arithmetic must be done without +, -, * or / — LC 371, 29.
• Something appears an even number of times and you want the odd one out — XOR cancels pairs, which gets its own page in Bitwise XOR Patterns.

The reframe: an integer is a fixed-size array of booleans that you can compare, add and hash in one instruction. That is the whole value proposition — a set operation that would cost a loop becomes a single &, | or ^.

Reach for something else when the set has more than ~64 members (use a real set; a Python int can hold more bits, but the code stops being readable and the operations stop being $O(1)$), when the problem is about values rather than their bit patterns, or when a clear solution already exists — bit tricks are frequently a micro-optimisation dressed up as an insight, and reaching for them first reads badly.

Binary representation

Python integers are arbitrary-precision and always signed, but bin() shows the underlying bit pattern the same way any language would.

binary_representation.py

x = 22
 
print("bin:", bin(x))                  # Python prefixes binary literals with "0b"
print("8-bit padded:", format(x, "08b"))
print("hex:", hex(x))
print("parsed back:", int("10110", 2))
print("bit_length:", x.bit_length())    # minimum bits needed to represent x, ignoring sign

The five core operators

bitwise_operators.py

a, b = 12, 10   # 0b1100, 0b1010
 
print("a & b:", bin(a & b))    # AND: 1 only where BOTH bits are 1
print("a | b:", bin(a | b))    # OR:  1 where EITHER bit is 1
print("a ^ b:", bin(a ^ b))    # XOR: 1 where the bits DIFFER
print("~a:", ~a)               # NOT: flips every bit -- equals -(a + 1) in two's complement
print("a << 2:", a << 2, " (multiply by 4)")
print("a >> 2:", a >> 2, " (integer-divide by 4)")

NOT looks strange because of two’s complement

~a is not “flip the bits you can see” — Python integers have no fixed width, so ~a is defined algebraically as -(a + 1). ~12 is -13, not some positive leftover pattern. In practice ~ almost always shows up combined with a mask, like ~(1 << i), where the surrounding & clips it back down to the bits that matter.

Check, set, clear, toggle: the four bit-mask idioms

Every “does this flag exist / turn it on / turn it off / flip it” question reduces to shifting a single 1 into position i and combining it with &, |, or ^.

bit_masks.py

def get_bit(num, i):
    return (num >> i) & 1                # shift bit i down to position 0, mask off the rest
 
 
def set_bit(num, i):
    return num | (1 << i)                # OR with a 1 in position i -- forces it on
 
 
def clear_bit(num, i):
    return num & ~(1 << i)               # AND with a 0 in position i -- forces it off
 
 
def toggle_bit(num, i):
    return num ^ (1 << i)                # XOR with a 1 in position i -- flips it
 
 
n = 0b1010
print("bit 1 of 1010:", get_bit(n, 1))          # expect 1
print("set bit 0:", bin(set_bit(n, 0)))         # expect 0b1011
print("clear bit 1:", bin(clear_bit(n, 1)))     # expect 0b1000
print("toggle bit 3:", bin(toggle_bit(n, 3)))   # expect 0b10

Two O(1) one-liners: lowest set bit and popcount

bit_tricks.py

x = 44   # 0b101100
 
print("lowest set bit:", bin(x & -x))     # isolates the rightmost 1 bit
print("set bit count:", x.bit_count())    # number of 1 bits (Python 3.10+)
 
 
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0   # a power of two has exactly ONE set bit
 
 
for value in [1, 2, 3, 4, 16, 18]:
    print(value, is_power_of_two(value))

x & -x works because of two’s complement: -x is ~x + 1, which flips every bit of x up to (and including) its lowest set bit, then that +1 carries all the way back to re-set exactly that lowest bit. ANDing x with that pattern cancels every other bit, leaving only the lowest 1.

n & (n - 1) clears the lowest set bit — so a value with exactly one set bit (a power of two) becomes 0 when that bit is cleared.

XOR tricks: cancellation is the whole trick

XOR’s defining property — x ^ x == 0 and x ^ 0 == x — means that XOR-ing a list of numbers where every value appears twice except one leaves only that one behind: every pair cancels itself out, order doesn’t matter.

xor_tricks.py

def single_number(nums):
    result = 0
    for num in nums:
        result ^= num          # duplicates cancel: x ^ x == 0
    return result
 
 
print("the one that appears once:", single_number([4, 1, 2, 1, 2]))
 
a, b = 5, 9
a = a ^ b
b = a ^ b   # b becomes the original a
a = a ^ b   # a becomes the original b
print("swapped without a temp variable:", a, b)

diagram XOR cancels every duplicate pair, leaving only the single number mermaid

  graph LR
    N0["start: 0"] -- "XOR 4" --> N1["4"]
    N1 -- "XOR 1" --> N2["5"]
    N2 -- "XOR 2" --> N3["7"]
    N3 -- "XOR 1" --> N4["6"]
    N4 -- "XOR 2" --> N5["4  (answer)"]

Running the XOR left to right over [4, 1, 2, 1, 2]: the two 1s and the two 2s each cancel out along the way, so whatever’s left at the end has to be the 4 — the only value without a partner.

The swap trick is a curiosity, not a recommendation

a, b = b, a is clearer, equally fast, and doesn’t silently break when a and b are the same variable (the XOR version zeroes it out). The three-XOR swap is worth recognizing when it shows up in older C code or interview trivia, but prefer tuple unpacking in real Python.

Dry run

Every idiom on one value. x = 180 = 10110100₂:

operation	expression	result	binary
check bit 2	x >> 2 & 1	1	00000001
set bit 1	x | (1 << 1)	182	10110110 — bit 1 now on
clear bit 5	x & ~(1 << 5)	148	10010100 — bit 5 now off
toggle bit 0	x ^ (1 << 0)	181	10110101 — bit 0 flipped
lowest set bit	x & -x	4	00000100
clear lowest set bit	x & (x - 1)	176	10110000

• & clears, \| sets, ^ toggles. Once you read them as “force off / force on / flip”, the four idioms stop needing memorisation. The ~ in the clear case is what turns a single 1 into a mask of all-1s-with-one-hole.
• x & -x and x & (x-1) are opposites, and both come from the same fact: subtracting 1 flips the lowest set bit to 0 and turns everything below it into 1s. AND-ing with x keeps only that bit (-x is ~x + 1); AND-ing with x - 1 removes exactly it.

Kernighan’s popcount on the same value. Each iteration clears one set bit:

iteration	n	bits remaining
start	10110100	4
1	10110000	3
2	10100000	2
3	10000000	1
4	00000000	0 → count = 4

Four iterations, not eight. The naive loop tests every bit position regardless; Kernighan’s runs once per set bit, so it is $O(\text{popcount})$ rather than $O(\text{width})$. On a sparse mask that is the difference between 1 iteration and 64. (int.bit_count() in Python 3.10+ beats both by being a single C call — use it, and know this for when you are asked to implement it.)

Power of two. n & (n - 1) == 0 means “clearing the lowest set bit leaves nothing”, i.e. there was exactly one bit. 12 = 1100 → 12 & 11 = 8 ≠ 0, not a power. 16 = 10000 → 16 & 15 = 0 ✓. The n > 0 guard matters: 0 & -1 == 0 would otherwise report zero as a power of two.

Complexity

Operation	Cost	Note
&, |, ^, ~, <<, >>	$O(1)$	on machine-word integers
x & -x, x & (x-1)	$O(1)$	single instruction each
Popcount, naive loop	$O(w)$, w = bit width	tests every position
Popcount, Kernighan	$O(\text{set bits})$	iterates once per 1
int.bit_count()	$O(1)$ effectively	C-level, Python 3.10+
Enumerate all $2^n$ subsets	$O(2^n)$	for m in range(1 << n)
Enumerate submasks of one mask	$O(2^{\text{popcount}})$	sub = (sub - 1) & mask
Submasks of every mask	$O(3^n)$, not $O(4^n)$	each bit is in-sub / in-mask-only / out
Bitmask DP state	$O(2^n \cdot n)$	why n ≤ 20 in these problems

Python integers are arbitrary precision, and that changes three things

1. ~x is -x - 1, not a 32-bit complement — conceptually there are infinitely many leading 1s. Any problem assuming 32-bit wrap (LC 371 add-without-plus, LC 190 reverse bits) needs masking: keep values in x & 0xFFFFFFFF, and convert back with x - (1 << 32) if x >= (1 << 31) else x.
2. Right-shifting a negative number never terminates a while n: loop — -1 >> 1 is -1 forever. Mask first, or iterate a fixed 32 positions.
3. Big masks stop being $O(1)$. A 10,000-bit int is fine as a bitset (and the mask |= mask << k subset-sum trick exploits exactly that, running ~64× faster than a loop) — but the operations are then $O(\text{bits}/64)$, not constant.

Bitmask subset enumeration

For a small set of up to ~20 items, every possible subset corresponds to exactly one integer from 0 to 2^n - 1 — bit i set means “item i is included.” Looping over that range enumerates every subset without any recursion.

bitmask_subsets.py

def subsets(nums):
    n = len(nums)
    result = []
    for mask in range(1 << n):                          # every mask from 0 to 2^n - 1
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result
 
 
for subset in subsets([1, 2, 3]):
    print(subset)

sketch Enumerating every subset of {1, 2, 3} as masks 0..7 p5.js Pause Restart

Each mask lights up exactly the elements whose bit is set -- 8 masks cover every one of the 2^3 subsets.

Complexity: O(1) per operation, O(2^n * n) for subset enumeration

Every single bitwise operation above is $O(1)$ (technically $O(w)$ for a word of w bits, but Python’s ints make that invisible until numbers get huge). Enumerating all subsets of n items is inherently $O(2^n \cdot n)$ — the exponential blowup is in the problem, not the bit trick; masking just makes each subset’s construction cheap and branch-free.

Python-specific: no fixed width, so no silent overflow

In C or Java, shifting or negating near the top of a 32/64-bit integer can silently wrap around. Python integers are arbitrary precision — 1 << 200 just works, and bit_length() / bit_count() (Python 3.10+) give you the bit-level introspection other languages need explicit intrinsics for. On older Python, bin(x).count("1") is the portable equivalent of x.bit_count().

The variant map

Need	Idiom	Notes
Read bit i	x >> i & 1
Set / clear / toggle bit i	x | (1 << i) · x & ~(1 << i) · x ^ (1 << i)	force on / force off / flip
Lowest set bit	x & -x	also how a Fenwick tree walks
Clear the lowest set bit	x & (x - 1)	the basis of Kernighan’s popcount
Power of two?	n > 0 and n & (n - 1) == 0	the n > 0 guard rejects zero
Count set bits	x.bit_count(), or Kernighan’s loop	$O(\text{set bits})$, not $O(\text{width})$
Full mask of n bits	(1 << n) - 1
Iterate all subsets	for m in range(1 << n)	$2^n$
Iterate submasks of mask	sub = mask; while sub: …; sub = (sub - 1) & mask	$O(3^n)$ over all masks
Is bit i the only one?	x == 1 << i
Swap without a temp	a ^= b; b ^= a; a ^= b	a party trick — tuple assignment is clearer and faster
LC 191 Number of 1 Bits	Kernighan
LC 338 Counting Bits	dp[i] = dp[i >> 1] + (i & 1)	DP over bit patterns, $O(n)$
LC 190 Reverse Bits	shift out of one, into the other, 32 times	needs a fixed width — mask in Python
LC 231 / 342 / 326 power of 2/4/3	n & (n-1) for 2; add n % 3 == 0-style checks otherwise
LC 371 Sum without +	while b: a, b = a ^ b, (a & b) << 1	must mask to 32 bits in Python or it never terminates
LC 136 / 260 Single Number	XOR	see Bitwise XOR Patterns
LC 78 Subsets	bitmask enumeration	see Subsets and Combinations

Pitfalls

• Operator precedence. &, \| and ^ bind looser than == in Python, so x & 1 == 0 parses as x & (1 == 0) — always 0. Parenthesise: (x & 1) == 0. This is the single most common bit-manipulation bug in Python and it fails silently.
• Assuming 32 bits. Python ints are arbitrary precision: ~x is -x - 1, and a negative number right-shifted never reaches zero, so while n: loops forever. Mask with 0xFFFFFFFF for any problem that assumes fixed-width wrap-around.
• Forgetting the n > 0 guard in the power-of-two test — 0 & -1 == 0 would call zero a power of two.
• 1 << i with a large i. Fine in Python, undefined behaviour in C/C++ when i exceeds the word width. Worth flagging if the interview is language-agnostic.
• Testing every bit position when the mask is sparse. Kernighan’s runs once per set bit; the naive loop always runs 32 or 64 times.
• Using XOR-swap in real code. It fails when both operands are the same variable (a ^= a zeroes it), and it is slower than the tuple swap on any modern CPU.
• Bit tricks where clarity was fine. n % 2 is clearer than n & 1 to most readers, and the compiler emits the same instruction. Use the trick when it buys something.

Interview follow-ups

They ask	What they’re checking	The answer
“Count the set bits without a built-in”	Whether you know Kernighan’s	while n: n &= n - 1; count += 1. It runs once per set bit rather than once per position, because n - 1 flips the lowest 1 to 0 and AND-ing removes exactly it
“Why does n & (n - 1) == 0 test for a power of two?”	Understanding, not recall	Because clearing the lowest set bit leaves zero only if there was exactly one bit. Add n > 0, or zero passes
“Explain x & -x”	Two’s complement	-x is ~x + 1: every bit below the lowest set bit becomes 0, that bit stays 1, everything above is inverted. AND-ing keeps precisely one bit
“Add two numbers without +”	Composition	a ^ b is the sum without carries, (a & b) << 1 is the carry; loop until the carry is zero. In Python you must mask to 32 bits and sign-convert at the end, or the carry propagates forever
“How would you store a set of 20 flags?”	Practical modelling	One integer. Membership is mask >> i & 1, insertion mask | (1 << i), union |, intersection &, difference & ~. It hashes and compares in one instruction, which is what makes bitmask DP possible
“Enumerate the submasks of a mask”	A specific idiom	sub = mask then sub = (sub - 1) & mask until it hits zero. Over all masks the total is $O(3^n)$, not $O(4^n)$
“Your solution works in C but loops forever in Python”	The language trap	Because Python integers have no fixed width — a negative value never shifts down to zero, and ~ has no top bit to stop at. Mask with 0xFFFFFFFF and convert back if the result exceeds $2^{31}$
“When would you not use bit tricks?”	Judgement	When they do not buy anything. n % 2 reads better than n & 1 for the same instruction, and a set beats a mask past ~64 elements. Bit manipulation earns its place on space, on set-as-a-value, and on genuinely bit-shaped problems

Practice — real LeetCode problems

One trick each: clearing the lowest set bit, reusing an already-computed answer one bit to the right, and counting bits modulo 3 instead of modulo 2.

LC 191 — Number of 1 Bits · Easy

Problem. Return the number of set bits in the binary representation of a positive integer (its Hamming weight).

Constraints. 1 <= n <= 2**31 - 1.

Examples. n = 11 (binary 1011) gives 3 · n = 128 (binary 10000000) gives 1 · n = 2147483645 gives 30

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

Three solutions, and the interviewer wants to hear why the second is better than the first.

Shift and test. Loop 32 times, checking n & 1 each time. Always 32 iterations.

Brian Kernighan. n & (n - 1) clears the lowest set bit. Why: n - 1 flips that lowest 1 to a 0 and all the zeros below it to 1s, so the AND keeps every higher bit and wipes everything from the lowest set bit down. The loop therefore runs once per set bit — 1 iteration for 128, not 32.

Built-in. bin(n).count("1"), or n.bit_count() on Python 3.10 and later. Mention it, but show the trick first — the question exists to test the trick.

Time $O(\text{popcount})$, at most 32. Space $O(1)$.

• n = 0 returns 0 and the loop body never runs. LeetCode’s constraints start at 1, but the test includes 0 because a shift-based loop with a bad terminating condition can hang or miscount there.
• 4294967295 is 32 ones and returns 32 — the maximum. It is above LeetCode’s stated bound and included on purpose: Python integers are arbitrary precision, so nothing overflows, which is worth knowing when the same code is asked for in C.
• Negative inputs are where the language matters. In Python -1 has infinitely many conceptual leading ones and this loop would never terminate; in C it is 32 ones and returns 32. If negatives are possible, mask with n & 0xFFFFFFFF first.

Follow-ups you should expect: “Count bits for every number from 0 to n (LC 338)?” — next problem, and the answer is DP, not 32 independent counts. “Hamming distance between two numbers (LC 461)?” — popcount of a ^ b. “Is n a power of two (LC 231)?” — n > 0 and n & (n - 1) == 0: exactly one set bit. “Constant time, no loop?” — the SWAR bit-twiddling sequence with masks 0x55555555, 0x33333333 and so on; worth knowing that it exists. “Do it in $O(1)$ for a 64-bit word?” — that is what hardware POPCNT is for.

LC 338 — Counting Bits · Easy

Problem. Given n, return an array ans of length n + 1 where ans[i] is the number of set bits in i.

Constraints. 0 <= n <= 10**5.

Examples. n = 2 gives [0,1,1] · n = 5 gives [0,1,1,2,1,2]

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

The point of the problem is the linear-time solution. Calling popcount n + 1 times is $O(n \log n)$ and is what the follow-up (“can you do it in one pass, in $O(n)$?”) is fishing for.

Time $O(n)$, one array write each. Space $O(n)$ for the output, which does not count as extra.

Three equivalent recurrences, all fine to present:

• dp[i] = dp[i >> 1] + (i & 1) — strip the lowest bit. The most common form.

• dp[i] = dp[i & (i - 1)] + 1 — strip the lowest set bit, using Kernighan from the previous problem. The neatest link between the two.

• dp[i] = dp[i - highest_power_of_two] + 1 — strip the highest bit, tracking the current power of two as you go.

• n = 0 must return [0], a list of length 1. The loop simply does not run.

• The array has n + 1 entries, not n. Off by one here is the usual failure.

• i >> 1 < i for all i >= 1, which is exactly the guarantee that an ascending loop respects the dependency order. That sentence is the proof of correctness.

Follow-ups you should expect: ”$O(1)$ extra space?” — impossible: the output itself is $O(n)$. “The single value only?” — LC 191. “Count set bits in all numbers up to $10^{18}$?” — digit DP over bit positions, since you cannot enumerate. “Which numbers in the range have an even popcount?” — the same DP with a parity test; that sequence is the Thue-Morse sequence. “Sort by popcount (LC 1356)?” — this array as a sort key.

LC 137 — Single Number II · Medium

Problem. Every element appears three times except one, which appears once. Find that one. Use linear time and constant extra space.

Constraints. 1 <= len(nums) <= 3 * 10**4, values fit in a 32-bit signed integer, and exactly one element appears once.

Examples. [2,2,3,2] gives 3 · [0,1,0,1,0,1,99] gives 99

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

The lesson is that XOR is addition modulo 2, so it solves the appears-twice version (LC 136) and nothing else. Threes need arithmetic modulo 3, which means two bits of state per position — and ones/twos are those two bits, maintained for all 32 positions simultaneously.

The state machine each bit position runs, as the same bit value arrives:

Occurrences	ones bit	twos bit
0 (mod 3)	0	0
1	1	0
2	0	1

The & ~twos in the first line stops a bit entering ones while it is sitting in twos; the & ~ones in the second uses the freshly updated ones, which is what makes a third occurrence clear both and return the position to 0. The order of the two lines matters — swapping them breaks it.

Time $O(n)$. Space $O(1)$.

• The line order is load-bearing. Compute twos first, and the transitions no longer close the cycle at three.
• Negative numbers work in Python, but for a subtle reason: integers are arbitrary precision and ~ behaves as two’s complement, so the sign bits track correctly. [1,1,1,-2] returning -2 is the check for that.
• Single-element input returns it directly — ones becomes that value on the first iteration and nothing promotes it.

The far more explainable alternative, and a perfectly good interview answer: for each of the 32 bit positions, sum that bit across all numbers and take the sum modulo 3. What remains is the answer’s bit. It is $O(32n)$ — still linear — and much easier to justify at a whiteboard. In Python you must then re-apply the sign: if bit 31 is set, subtract $2^{32}$. Offer this version first, then the two-variable one as the optimisation.

Follow-ups you should expect: “Appears twice instead (LC 136)?” — XOR everything. “Two numbers appear once (LC 260)?” — XOR everything, then split by any set bit of the result. “Appears k times, one appears once?” — the mod-k bit-sum method generalises directly; the two-variable trick does not, without care. “Appears three times, one appears twice?” — bit sums modulo 3 leave a residue of 2 in those positions. “Why not a hash map?” — it works and is what you would ship; the constant-space constraint is what makes this a puzzle.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

12 problems

5 easy5 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○67Add BinaryeasyLeetCode Top Interview 150
• ○136Single NumbereasyThe running-XOR trick above, applied directlyNeetCode 150LeetCode Top Interview 150
• ○190Reverse BitseasyNeetCode 150Blind 75LeetCode Top Interview 150
• ○191Number of 1 Bitseasy`x.bit_count()`, or `n & (n - 1)` in a loop to count how many times the lowest set bit can be clearedNeetCode 150Blind 75LeetCode Top Interview 150
• ○338Counting Bitseasy`dp[i] = dp[i >> 1] + (i & 1)`, a DP built directly on the bit-mask idioms aboveNeetCode 150Blind 75
• ○78SubsetsmediumThe bitmask subset enumeration above, applied to `nums` directlyNeetCode 150
• ○137Single Number IImediumEvery other number appears **three** times; needs per-bit counting mod 3 instead of a plain XORLeetCode Top Interview 150
• ○201Bitwise AND of Numbers RangemediumLeetCode Top Interview 150
• ○371Sum of Two IntegersmediumNeetCode 150Blind 75
• ○421Maximum XOR of Two Numbers in an ArraymediumBuild each number's prefix bit-by-bit in a trie (or a running prefix-mask set) to greedily maximize the XOR, bit by bit from the top
• ○600Non-negative Integers without Consecutive Oneshard
• ○1483Kth Ancestor of a Tree Nodehard

Self-check

pch.quizTag Bit manipulation — self-check

1. In Python, `if x & 1 == 0:` does not do what it looks like. Why?

   A `&` is not defined for integers B `&` binds looser than `==`, so it parses as `x & (1 == 0)` — that is `x & 0`, always falsy C `x` must be cast to bool first D It works correctly
   pch.quizShowAnswer

   B — `&` binds looser than `==`, so it parses as `x & (1 == 0)` — that is `x & 0`, always falsy — Parenthesise: `(x & 1) == 0`. The expression is silently wrong rather than an error, which is what makes it the most common bit bug in Python.

2. Why does `n & (n - 1)` clear exactly the lowest set bit?

   A Because subtraction borrows from the top B Because n − 1 flips the lowest set bit to 0 and turns every zero below it into a 1, so the AND keeps everything above and removes precisely that bit C Because n and n−1 are coprime D It clears the highest set bit, not the lowest
   pch.quizShowAnswer

   B — Because n − 1 flips the lowest set bit to 0 and turns every zero below it into a 1, so the AND keeps everything above and removes precisely that bit — It is the exact complement of `x & -x`, which keeps only that bit. Both fall out of the same fact about how subtracting 1 rewrites the low end of the number.

3. Kernighan's popcount on 10110100 takes how many iterations, and why does that matter?

   A 8 — one per bit position B 4 — one per SET bit, because each iteration clears one; the naive loop always runs the full width regardless of how sparse the value is C 1 — it is O(1) D 3 — one per byte
   pch.quizShowAnswer

   B — 4 — one per SET bit, because each iteration clears one; the naive loop always runs the full width regardless of how sparse the value is — On a sparse 64-bit mask that is 1 iteration versus 64. In production use int.bit_count(); know Kernighan's for when you are asked to implement it.

4. Your `while n:` bit loop works in C++ but hangs in Python on negative input. Why?

   A Python has no bitwise operators for negatives B Python integers are arbitrary precision, so a negative number right-shifted stays negative forever — conceptually it has infinitely many leading 1s C Python's >> is a rotate D The loop condition should be `while n > 0`
   pch.quizShowAnswer

   B — Python integers are arbitrary precision, so a negative number right-shifted stays negative forever — conceptually it has infinitely many leading 1s — `while n > 0` fixes the hang but gives the wrong answer for negatives. The real fix is masking with 0xFFFFFFFF and converting back if the result exceeds 2^31.

5. How do you add two integers without using `+`?

   A Repeated increment B `a ^ b` is the sum without carries and `(a & b) << 1` is the carry; loop until the carry is zero — and in Python mask to 32 bits or the carry propagates forever C Use multiplication by 1 D Convert to strings and concatenate
   pch.quizShowAnswer

   B — `a ^ b` is the sum without carries and `(a & b) << 1` is the carry; loop until the carry is zero — and in Python mask to 32 bits or the carry propagates forever — LC 371. The masking caveat is the whole difficulty in Python, and mentioning it unprompted is what distinguishes knowing the trick from having used it.

6. When is a bitmask the wrong choice for representing a set?

   A Never; it is always faster B Past roughly 64 elements — a Python int can hold more bits, but the operations stop being O(1) and the code stops being readable, so a real `set` is better C When the elements are strings D When you need union and intersection
   pch.quizShowAnswer

   B — Past roughly 64 elements — a Python int can hold more bits, but the operations stop being O(1) and the code stops being readable, so a real `set` is better — The bitmask's value is that a whole set becomes one comparable, hashable, indexable value. Beyond a word's worth of bits that advantage erodes while the readability cost stays.

Recall card

• Cue — the problem is about the binary representation, or you need a small set as a single value (bitmask), or the constraint is $O(1)$ space where a hash map is obvious.
• The four idioms — read x >> i & 1; set x | (1 << i); clear x & ~(1 << i); toggle x ^ (1 << i). Read & as force-off, | as force-on, ^ as flip.
• x & -x isolates the lowest set bit; x & (x - 1) clears it. Same fact, opposite use.
• Power of two — n > 0 and n & (n - 1) == 0.
• Popcount — int.bit_count(), or Kernighan’s while n: n &= n - 1 at $O(\text{set bits})$.
• Full mask (1 << n) - 1; all subsets for m in range(1 << n); submasks sub = (sub - 1) & mask, $O(3^n)$ over all masks.
• Parenthesise comparisons — (x & 1) == 0, because & binds looser than ==.
• Python has no fixed width — ~x == -x-1, negatives never shift to zero. Mask with 0xFFFFFFFF for LC 371 / 190 and convert back above $2^{31}$.

Recap

• Five operators — & | ^ ~ << >> — cover check/set/clear/toggle via a shifted 1 << i mask.
• x & -x isolates the lowest set bit; n & (n - 1) clears it — the basis of popcount loops and power-of-two checks.
• XOR’s cancellation (x ^ x == 0) finds a lone non-duplicate in a single pass with $O(1)$ extra space.
• Counting from 0 to 2^n - 1 enumerates every subset of n items, each one an $O(n)$ bit-check away from a real list.

Next: Advanced DP Optimizations — digit DP, monotonic-deque-optimized DP, and a tour of the classic speedups (convex hull trick, divide and conquer, Knuth) that turn an $O(n^2)$ recurrence into something faster.