Python integers never overflow. Half the bit problems assume they do.

These are my data structures and algorithms notes, cleaned up into nineteen posts, one pattern at a time. This one covers bit manipulation: the handful of bitwise identities the problems turn on, and how to fake 32-bit integers in a language whose integers never overflow.

Bit manipulation treats an integer as a row of switches instead of a quantity. Most problems in this topic are a few lines long, and each one hinges on a single identity: XOR cancels pairs, n & (n - 1) drops the lowest 1, a shifted 1 picks out one position. If you know the identities cold, you can spot the problem. If you don’t, no amount of cleverness gets you there.

In the order this series follows, this topic comes after 1-D Dynamic Programming, and together with 2-D Dynamic Programming it leads to the last part, Math & Geometry. The prerequisite here is Bit Operations. Python adds a complication on top of it. Its integers are unbounded, while several problems on this list are specified for 32-bit integers, so there’s one extra module on imitating fixed-width integers.

How to use this post: the method. Checkpoints have no answers on the page: work them out, then open the linked chat to have your answer checked.

Bit Operations

Foundation

An integer in binary is a row of positions, and position i is worth 2^i. 12 is 1100, meaning 8 + 4. A bitwise operator works on every position independently, as if you had 32 (or 64, or infinitely many) tiny one-bit machines working in parallel. There is no carrying between positions, which is the difference from +.

That’s why the technique is useful. A single integer can act as a set of flags, and one bitwise instruction does something to all of them at once. A handful of identities then turn questions like “which bit is lowest?”, “is exactly one bit set?” or “which value is left after pairs cancel?” into O(1) expressions.

Negative numbers use two’s complement. In a w-bit integer the top position is worth −2^(w−1) instead of +2^(w−1), so a pattern with the top bit set reads as its unsigned value minus 2^w. Two consequences you’ll use constantly:

-x == ~x + 1. Negating means flip every bit, then add 1.
In Python, ~x == -x - 1 for every integer, because Python behaves as if every integer had infinitely many bits: non-negative numbers have infinitely many leading 0s, negative numbers have infinitely many leading 1s (recalled: this is how Python defines bitwise operations on its unbounded ints).

Mechanics

One worked example for the whole module: a = 12 (1100) and b = 10 (1010).

The operators, one position at a time.

The symbols are & (AND), | (OR), ^ (XOR), ~ (NOT), << and >> (shifts).

Operator	Rule per position	Applied to 12 and 10
AND	1 only if both are 1	`1000` = 8
OR	1 if either is 1	`1110` = 14
XOR	1 if exactly one is 1, meaning “the bits differ”	`0110` = 6
NOT (of 12)	flip every bit	−13 in Python
Left shift by k	move every bit up k positions, fill with 0; same as times 2^k	`12 << 1` = 24
Right shift by k	move every bit down k positions, the low k bits fall off; same as floor division by 2^k	`12 >> 2` = 3

Masks. A mask is an integer built so its 1s mark the positions you care about. 1 << i has a single 1 at position i. (1 << k) - 1 has 1s at positions 0 to k−1 inclusive, so (1 << 4) - 1 is 1111. The single-bit operations below follow from what AND, OR and XOR do to one bit y: y & 1 == y, y & 0 == 0, y | 0 == y, y | 1 == 1, y ^ 0 == y, y ^ 1 == not y.

Test bit i: (x >> i) & 1. For 12 and i = 2: 12 >> 2 is 11, and 11 & 1 is 1, so bit 2 is set. Bit 0 gives 0.
Set bit i: x | (1 << i). The mask is 0 everywhere else, and OR with 0 keeps a bit, so only position i can change. Set bit 0 of 12: 1101 = 13.
Clear bit i: x & ~(1 << i). The inverted mask is 1 everywhere except position i, and AND with 1 keeps a bit. Clear bit 3 of 12: 0100 = 4.
Toggle bit i: x ^ (1 << i). XOR with 0 keeps, XOR with 1 flips. Toggle bit 1 of 12: 1110 = 14.
Flip the low k bits: x ^ ((1 << k) - 1). 12 XOR 1111 is 0011 = 3.

n & (n - 1) clears the lowest set bit. Look at what subtracting 1 does to 12 = 1100. The lowest 1 is at position 2. Subtracting 1 has to borrow from it, so position 2 becomes 0 and the 0s below it (positions 0 and 1) become 1s: 11 = 1011. Everything above position 2 is untouched. So n and n - 1 agree above the lowest 1 and disagree from it downward. AND keeps the agreement and zeroes the rest: 1100 & 1011 = 1000 = 8. That’s safe for every n > 0, because every n > 0 has a lowest 1 to borrow from.

Two consequences:

n > 0 and n & (n - 1) == 0 means n had exactly one 1, so n is a power of two. 12 gives 8 (not a power), 8 gives 1000 & 0111 = 0 (a power).
The lowest set bit on its own is n & -n. -n is ~n + 1. Flipping turns the trailing 0s of n into 1s, and the +1 carries through them and stops at the lowest 1 of n. So n and −n share exactly one bit. 12 & -12 = 0100 = 4. And n & (n - 1) plus n & -n add up to n: 8 + 4 = 12.

XOR cancellation. Three properties make XOR special:

x ^ x == 0. Every position matches itself.
x ^ 0 == x.
XOR is commutative and associative, so the order and grouping of a chain don’t matter.

So in any chain of XORs, equal values can be moved next to each other and wiped out in pairs. 12 ^ 10 ^ 12 regroups as (12 ^ 12) ^ 10 = 0 ^ 10 = 10. What XOR really tracks is parity per position: after a chain, bit i is 1 exactly when an odd number of the inputs had bit i set. A value that appears an even number of times contributes nothing. This is also why XOR is its own inverse: m ^ k ^ k == m, the basis of every “encrypt and decrypt with the same key” toy.

Diagram

The operators on the worked example, one column per position. Set bits of the inputs are tinted blue, set bits of each result green:

AND, OR and XOR of a = 12 and b = 10, column by column: 8, 14 and 6.

Shifts of a = 12: a << 1 = 24 moves every bit up one; a >> 2 = 3 drops positions 1..0.

The lowest-set-bit tricks. In the first figure the dashed amber frame marks the positions that flip when you subtract 1. In the second, −12 is shown as its low 8 bits, and the grey left-hand cell stands for the pattern that continues forever to the left (infinite 0s for 12, infinite 1s for −12):

a & (a − 1): subtracting 1 flips the lowest 1 of 12 (position 2) and everything below it, so AND clears that bit and keeps positions 7..3. Result 8.

a & −a: −12 is ~a + 1, and it shares exactly one set bit with 12, the lowest one. Result 4.

Implementation

def get_bit(x: int, i: int) -> int:
    # Shift bit i down to position 0, then keep only position 0.
    # 12 = 0b1100, i = 2: 12 >> 2 = 0b11, 0b11 & 1 = 1.
    return (x >> i) & 1

def set_bit(x: int, i: int) -> int:
    # 1 << i has a single 1 at position i; OR forces position i to 1
    # and leaves every other position of x unchanged (y | 0 == y).
    return x | (1 << i)

def clear_bit(x: int, i: int) -> int:
    # ~(1 << i) is all 1s except a 0 at position i; AND with it forces
    # position i to 0 and keeps every other position (y & 1 == y).
    return x & ~(1 << i)

def toggle_bit(x: int, i: int) -> int:
    # XOR with 1 flips a bit, XOR with 0 keeps it, so only position i flips.
    return x ^ (1 << i)

def low_mask(k: int) -> int:
    # (1 << k) - 1 has 1s at positions 0..k-1 inclusive: k = 4 gives 0b1111.
    return (1 << k) - 1

def clear_lowest_set_bit(x: int) -> int:
    # x - 1 turns the lowest 1 of x into 0 and the 0s below it into 1s;
    # positions above the lowest 1 are identical in x and x - 1,
    # so AND keeps them and zeroes the lowest 1: 12 & 11 = 0b1100 & 0b1011 = 0b1000.
    return x & (x - 1)

def lowest_set_bit(x: int) -> int:
    # -x == ~x + 1 (recalled: two's complement negation). ~x flips everything,
    # + 1 carries through the flipped trailing 0s (now 1s) and stops at the
    # lowest 1 of x, so x and -x share exactly that one bit: 12 & -12 = 4.
    return x & -x

def is_power_of_two(x: int) -> bool:
    # A power of two has exactly one 1, so clearing it leaves 0.
    # x > 0 is required: 0 & -1 == 0 would otherwise pass for x = 0.
    return x > 0 and x & (x - 1) == 0

a, b = 12, 10
print(a & b, a | b, a ^ b, a << 1, a >> 2)               # 8 14 6 24 3
print(get_bit(a, 2), get_bit(a, 0))                      # 1 0
print(set_bit(a, 0), clear_bit(a, 3), toggle_bit(a, 1))  # 13 4 14
print(a ^ low_mask(4))                                   # 3  (flip positions 0..3 of 12)
print(clear_lowest_set_bit(a), lowest_set_bit(a))        # 8 4
print(a ^ b ^ a)                                         # 10 (the two 12s cancel)
print(is_power_of_two(12), is_power_of_two(8), is_power_of_two(0), is_power_of_two(1))
# False True False True

I ran this, plus edge cases: get_bit(0, 5) is 0, clear_lowest_set_bit(0) and lowest_set_bit(0) are both 0 (0 has no lowest bit, and both expressions return 0 rather than failing), toggle_bit(0, 31) is 2147483648, and is_power_of_two(-8) is False while is_power_of_two(1 << 63) is True.

Complexity: each operation is O(1) on fixed-width integers. On Python’s unbounded ints it’s O(w / 30), where w is the bit length, since CPython stores ints in 30-bit digits (recalled). For interview-sized numbers, treat it as O(1). Space O(1).

Python has two built-ins worth knowing: x.bit_length() (12 gives 4) and x.bit_count(), the number of 1s (12 gives 2, available since Python 3.10, recalled). bin(x) and format(x, "08b") show the pattern. For negatives they show a minus sign and the magnitude, as the next module covers.

Recognition

Signals:

Pairs cancel, or something appears an odd number of times. “Every element appears twice except…”, “the one that’s unmatched”. XOR parity. Single Number shows this signal.
A known range with one value absent or extra. When you know in advance which values should be there, you may be able to compare expected against actual without storing either. Missing Number shows this signal.
“Count the 1 bits”, “reverse the bits”, “the i-th bit”. The problem is literally about positions: Number of 1 Bits, Counting Bits, Reverse Bits.
“Without using + or −”, “without multiplication”. Arithmetic has to be rebuilt from bitwise operators: Sum of Two Integers.
O(1) extra space where a hash set would be the obvious answer. Often a hint that XOR or a bitmask replaces the set.
Small n, n ≤ 20 or so, with subsets. An integer from 0 to 2^n − 1 can encode a subset. That’s bitmask DP or enumeration, the same mask mechanics.
Powers of two, flags, permissions. Single-bit tests and n & (n - 1).

When not to use it: when a set or counter says the same thing more clearly and the constraints allow the memory. Bit tricks are also narrower than they look. XOR recovers a value that appears an odd number of times, but it can’t tell one occurrence from three, and it can’t find two different unmatched values in one pass without extra work.

Nearest look-alikes: hashing (Arrays & Hashing) solves most “find the unmatched element” questions in O(n) space. XOR is the O(1)-space version, and it only works because of the parity structure. Arithmetic identities (sum of 0..n) compete with XOR on “recover the missing value” questions. They work fine in Python, but in fixed-width languages the sum can overflow and XOR can’t.

Pitfalls

Precedence. Arithmetic binds tighter than shifts, and shifts bind tighter than &, ^, |. So 1 << i + 1 is 1 << (i + 1): 1 << 2 + 1 is 8. In Python, comparisons bind looser than bitwise operators, so x & 1 == 0 means (x & 1) == 0. In C, Java and JavaScript == binds tighter than & (recalled), so parenthesise anyway. The code then ports and reads unambiguously.
~ is not not. ~12 is −13, and ~True is −2. Use not for booleans.
n & (n - 1) and n & -n at n = 0. Both return 0, so a power-of-two test without n > 0 wrongly accepts 0.
Right shift of negatives floors. -5 >> 1 is −3, the same as -5 // 2, while C-style truncation int(-5 / 2) gives −2. Don’t mix the two views.
Negative shift counts raise. 1 >> -1 is a ValueError, so guard computed shift amounts.
Bit positions are 0-indexed from the right. “The 3rd bit” in a problem statement might mean position 2 or position 3. Pin it down with a tiny example before coding.
bin(x) has a 0b prefix, and for negative x a -0b prefix and the magnitude. Counting characters in it for negative numbers counts the wrong thing.

Active Recall

For a = 40 (101000), what are a & -a and a & (a - 1)? What relation between the two results holds for every a > 0?
Why does is_power_of_two need x > 0? What would x & (x - 1) alone say about −8?
Starting from x = 11 (1011), write one expression that clears bit 1 and sets bit 2. What’s the result, and does the order of the two steps matter?
What is 12 ^ 10 ^ 12 ^ 10 ^ 10, and why can you get it without evaluating left to right? What would a value that appears three times contribute?
In Python, what do 1 << 2 + 1 and 12 & 10 == 8 evaluate to?

Answer out loud or on paper first.

Answer these yourself, then get them checked byChatGPT ↗Claude ↗

Mini-task

Skipped. Single Number and Missing Number each make you find a use for XOR cancellation from scratch, and Reverse Bits makes you drive single-bit tests and sets by position yourself, so the list already exercises this module’s core. That reasoning happens when you solve them.

Transfer test

A deduplication service stores a 64-bit “fingerprint” per document, built so that similar documents get fingerprints that differ in only a few bit positions. Two documents count as near-duplicates if their fingerprints differ in at most 3 positions. Given two fingerprints, would you use bit operations to decide? Why?

Decide, then get a second opinion fromChatGPT ↗Claude ↗

Fixed-width integers in Python

Why the list needs it: Reverse Bits works on a 32-bit unsigned value, Sum of Two Integers is specified on 32-bit signed integers, and Reverse Integer must detect 32-bit overflow. Python has no 32-bit integers, so you have to build that behaviour yourself.

Foundation

Imagine every Python integer as a tape of bits that goes on forever to the left: 0s forever for non-negative numbers, 1s forever for negative ones. A 32-bit machine keeps only the rightmost 32 squares of that tape and throws the rest away. Whether those 32 squares are read as unsigned (0 to 2^32 − 1) or signed (−2^31 to 2^31 − 1) is a matter of interpretation. The pattern itself is the same.

So imitating fixed width in Python comes down to two moves: cut the tape to 32 squares (a mask), and choose a reading (unsigned or signed). Knowing when you must cut is the rest.

Mechanics

The worked example for this module is x = −12, the negative of the previous module’s a.

1. Cut: x & 0xFFFFFFFF. 0xFFFFFFFF has 1s at positions 0 to 31 inclusive. ANDing keeps those and zeroes everything above, so the result is always between 0 and 2^32 − 1 inclusive. For −12 the tape is ...1111 0100, and the cut gives 0xFFFFFFF4 = 4294967284, the 32-bit pattern 11111111111111111111111111110100, which has 29 ones.

2. Read as signed. In a 32-bit pattern, position 31 is worth −2^31 instead of +2^31, so a pattern with bit 31 set reads as its unsigned value minus 2^32. 4294967284 − 4294967296 = −12. If bit 31 is 0 (unsigned value 0 to 2^31 − 1 inclusive), the signed and unsigned readings agree. An equivalent one-liner is (u ^ 0x80000000) - 0x80000000.

3. When the cut can wait, and when it can’t. This is the invariant that matters: for +, -, *, &, |, ^, ~ and <<, the low 32 bits of the result depend only on the low 32 bits of the inputs. Carries and shifts only move information upward, never down. So for a chain of those operations, cutting once at the end gives the same bits as cutting after every step (I checked this on 20,000 random pairs per operator). The other side:

>> pulls high bits down, so cutting after is wrong. (-12 >> 1) & 0xFFFFFFFF is 0xFFFFFFFA (arithmetic shift, sign bits come in), while (-12 & 0xFFFFFFFF) >> 1 is 0x7FFFFFFA (logical shift, 0s come in). They differ. Cut before a right shift whenever you want the unsigned, logical behaviour.
Comparisons, division, % and loop conditions look at the whole number, so cut (and reinterpret) before them.
Growth. Even where cutting late is correct, the intermediate numbers keep growing. That costs time and memory, so in loops you usually cut every iteration anyway.

4. Overflow. A signed 32-bit result is valid only if it lies between −2^31 and 2^31 − 1 inclusive. Python computes the true result, so you can check after the fact: INT32_MIN <= r <= INT32_MAX. In a language where the result itself would already have wrapped, you check before computing, rearranged so the check can’t overflow. For a + b with b > 0, a + b > INT32_MAX is the same as a > INT32_MAX - b, and INT32_MAX - b is in range. What wrapping looks like: 2,000,000,000 + 2,000,000,000 is 4,000,000,000 in Python, but read as 32-bit signed it’s −294967296.

5. Loops that never end. while n: n >>= 1 terminates for n ≥ 0, but for n = −12 the values are −12, −6, −3, −2, −1, −1, −1, and so on. An arithmetic shift of −1 is −1 forever. Either cut first (then n reaches 0 within 32 shifts) or loop a fixed 32 times.

Diagram

The two readings of the same 32-bit pattern. Amber rows have bit 31 set, which is exactly where the two readings part ways:

One pattern, two readings. Below 0x80000000 unsigned and signed agree; from there on the signed value is the unsigned one minus 2^32.

And the cut on the worked example. Python’s −12 is the infinite tape, and the mask keeps positions 0..31. Set bits are tinted blue in −12, violet in the mask and green in the result; ⋯ stands for positions 28..4, all 1s in every row:

Masking −12 with 0xFFFFFFFF: everything above position 31 is cut away, leaving 0xFFFFFFF4 = 4294967284.

Implementation

MASK32 = 0xFFFFFFFF          # 1s at positions 0..31 inclusive, i.e. 2**32 - 1
SIGN32 = 0x80000000          # the single bit at position 31, i.e. 2**31
INT32_MAX = 2**31 - 1        # 2147483647
INT32_MIN = -(2**31)         # -2147483648

def to_u32(x: int) -> int:
    # Keep positions 0..31 of x. For x = -12, Python treats x as having
    # infinitely many leading 1s (recalled: Python's bitwise ops act on an
    # infinite two's complement), so the result is 0xFFFFFFF4 = 4294967284.
    return x & MASK32

def to_i32(u: int) -> int:
    # Read a 32-bit pattern as signed. If position 31 is 1, the pattern stands
    # for u - 2**32: 0xFFFFFFF4 -> 4294967284 - 4294967296 = -12.
    # If position 31 is 0 (u in 0..2**31 - 1 inclusive), u already equals its
    # signed value: 0x0000000C -> 12.
    u &= MASK32
    return u - (1 << 32) if u & SIGN32 else u

def lsr32(x: int, k: int) -> int:
    # Logical shift right on 32 bits: mask first so the leading 1s of a negative
    # x become a finite 32-bit pattern, then shift zeros in from the left.
    # -12 -> 0xFFFFFFF4 >> 1 = 0x7FFFFFFA. Plain -12 >> 1 would give -6.
    return to_u32(x) >> k

def bits32(x: int) -> str:
    # format(-12, '032b') prints '-000...1100' (a sign plus the magnitude),
    # so mask first to see the real 32-bit pattern.
    return format(to_u32(x), "032b")

def fits_i32(r: int) -> bool:
    # Python never overflows, so the range check can be done after computing r.
    return INT32_MIN <= r <= INT32_MAX

def add_overflows_i32(a: int, b: int) -> bool:
    # For languages that CAN'T hold a + b: check before adding, using a
    # subtraction that stays in range. With b > 0, a + b > INT32_MAX exactly when
    # a > INT32_MAX - b (and INT32_MAX - b is in range because 1 <= b <= INT32_MAX).
    # With b < 0, a + b < INT32_MIN exactly when a < INT32_MIN - b
    # (INT32_MIN - b is in range because INT32_MIN <= b <= -1).
    # With b == 0, a + b == a, which is already in range.
    if b > 0:
        return a > INT32_MAX - b
    if b < 0:
        return a < INT32_MIN - b
    return False

x = -12
print(to_u32(x), hex(to_u32(x)))                # 4294967284 0xfffffff4
print(bits32(x))                                 # 11111111111111111111111111110100
print(to_i32(to_u32(x)), to_i32(12))             # -12 12
print(x >> 1, lsr32(x, 1), hex(lsr32(x, 1)))     # -6 2147483642 0x7ffffffa
print(hex(to_u32(~12)))                          # 0xfffffff3
print(12 << 29, to_i32(12 << 29))                # 6442450944 -2147483648
print(fits_i32(12 << 29), fits_i32(-12))         # False True
print(add_overflows_i32(INT32_MAX, 1), add_overflows_i32(INT32_MIN, -1))   # True True
print(add_overflows_i32(INT32_MAX, -1), add_overflows_i32(-12, 0))         # False False

Checked beyond the example: to_i32(0) is 0, to_i32(0xFFFFFFFF) is −1, to_i32(0x80000000) is −2147483648, lsr32(-1, 31) is 1. On 100,000 random pairs of 32-bit signed values, add_overflows_i32(a, b) agreed with not fits_i32(a + b) every time, and to_i32(to_u32(a)) == a always held.

The 12 << 29 line is worth a second look. 12 is 1100, so shifting by 29 puts its two 1s at positions 31 and 32. The cut drops position 32 and keeps position 31, the sign bit, so a positive 12 shifted left becomes INT32_MIN. That’s exactly what a 32-bit machine would do.

Complexity: every helper is O(1) time and O(1) space for inputs that fit in a few machine words.

Recognition

Signals:

The statement says “32-bit signed integer”, “unsigned integer” or “assume the environment cannot store 64-bit integers”, or gives a range like −2^31 ≤ x ≤ 2^31 − 1. In this list: Reverse Bits, Sum of Two Integers, Reverse Integer.
The expected output for a negative input is a large positive number, or vice versa. The problem is reading a pattern under the other interpretation.
You’re porting code from C, Java or Go that relies on wraparound: hashes, random number generators, checksums.
An operation lets a carry or a set bit travel upward forever. With a negative operand in Python, “forever” is literal, so a loop that expects the value to hit 0 may never stop.

When not to use it: if the problem only involves non-negative values that stay far below 2^31 and no right shifts or wraparound are needed, masking is noise. Python’s unbounded ints are then an advantage, not a problem.

Nearest look-alike: modular arithmetic (% MOD in DP counting problems). Masking with 2^32 − 1 is exactly % 2**32 for non-negative results, and Python’s % also returns a non-negative result for negative inputs (recalled). But MOD = 10**9 + 7 problems never need the signed reading, and bit problems usually do.

Pitfalls

bin(-12) is '-0b1100', and format(-12, '032b') is a minus sign followed by the zero-padded magnitude. Neither shows two’s complement. Mask first.
Counting 1s of a negative number counts the magnitude. bin(-12).count('1') is 2, while the 32-bit pattern has 29 ones.
Forgetting to convert back. A function that should return a signed 32-bit value but returns to_u32(...) hands back 4294967284 instead of −12.
Cutting after a right shift. (x >> k) & MASK32 is not a logical shift for negative x. Use (x & MASK32) >> k.
Infinite loops on negatives. while n: with n >>= 1 never reaches 0 for n < 0. Anything that loops until a carry dies out has the same risk.
Off-by-one on the range. The signed range is −2^31 to 2^31 − 1 inclusive, which isn’t symmetric. The magnitude 2^31 exists only as a negative.

Active Recall

What do to_i32(0x80000000) and to_i32(12 << 29) return, and why are they the same?
Trace while n: n >>= 1 for n = −12. What goes wrong, and give two fixes.
bin(-12).count('1') gives 2. How many 1s does −12 have as a 32-bit pattern, and how would you compute it in Python?
You want the upper 16 bits of the 32-bit wrapped product of a = 0x10000 and b = 0x10001. Should you mask before or after the >> 16? What does each order give?
Is a + b > INT32_MAX a valid overflow check in Python? Would it be in Java?

Answer out loud or on paper first.

Answer these yourself, then get them checked byChatGPT ↗Claude ↗

Mini-task

Skipped. Sum of Two Integers makes you work out, in Python, when and where the 32-bit cut and the signed reading have to happen for your own loop, which is this module’s core applied from scratch. That reasoning belongs in its own solve.

Transfer test

You’re porting a 32-bit FNV-1a hash from C to Python. Per input byte it does h ^= byte, then h *= 16777619, and C’s uint32_t wraps silently. Your Python port does a single & 0xFFFFFFFF on the return value. It matches the C output on every test string, but it gets slower and slower on long inputs. Is the end-only mask a bug, a performance problem, or both? Where would you put the cut, and why?

Decide, then get a second opinion fromChatGPT ↗Claude ↗

Integration

Bit Operations gives you the vocabulary: per-position rules, masks, n & (n - 1), n & -n, XOR parity. The fixed-width module gives you the ground those operations run on in the problems as written. A statement that says “32-bit” is describing a machine that cuts the tape at position 31, and in Python you have to do that cut yourself, in the right place. Almost every problem in this topic is one identity from the first module, plus possibly one decision from the second.

Distinguishing competing approaches:

XOR vs hash set vs arithmetic total, for “find the unmatched or missing value”. A hash set is O(n) space and handles any multiplicity. An arithmetic total (sum and subtract) is O(1) space but can overflow in fixed-width languages. XOR is O(1) space, can’t overflow, and needs a parity structure: whatever you want cancelled has to appear an even number of times.
Walk all w positions vs jump from 1 to 1. A for i in range(32) loop with (x >> i) & 1 is O(w), sees every position including the 0s, and runs a predictable number of times. Repeatedly taking x & -x and then x &= x - 1 jumps straight from one set bit to the next, so it’s O(number of set bits) but never looks at a 0. Choose based on whether the 0 positions matter to you.
Bit reasoning vs arithmetic reasoning. Reverse Integer is about decimal digits and 32-bit range, not bit positions. It lives here because of the fixed-width module, not the first one. If the statement talks about digits, think % 10 and // 10. If it talks about bits, think masks and shifts.
Bit tricks vs DP. When a question asks for some bit property of every number in 0..n, per-number work is the fallback. That 1-D DP comes right before this topic in the topic map is a reminder to ask whether one number’s answer can be reused for another.

Recognition checklist for an unfamiliar problem:

Does the statement say “without +/−”, “O(1) extra space”, “every element appears twice / k times except”? Think XOR, or per-bit counting.
Is it about positions: the i-th bit, counting 1s, reversing, powers of two? Write the numbers in binary for n = 0..8 and look at which positions change.
Is there a set of at most about 20 items? A mask from 0 to 2^n − 1 can stand for a subset.
Does it name a width (32-bit, unsigned, “cannot store 64-bit”)? Decide up front where you’ll cut with & 0xFFFFFFFF, where you’ll read as signed, and whether any right shift or loop condition sees a negative number.
Can the answer go out of range? Know the inclusive range −2^31 to 2^31 − 1, and whether you’re allowed to compute first and check after.

The problems

Run each through the solving cycle from Part 1: a 15-minute struggle, a key sentence, spaced repetition. For bit manipulation the struggle is concrete. Write small inputs in binary on paper, ask which identity (XOR cancel, n & (n - 1), single-bit mask) matches what changes, and ask whether the problem assumes 32 bits before you write a loop.

7 problems · 5 easy · 2 medium · 0 hard · tracker spreadsheet (.xlsx)

#	Problem	Difficulty	Coach
1	Single Number	Easy	ChatGPT · Claude
2	Number of 1 Bits	Easy	ChatGPT · Claude
3	Counting Bits	Easy	ChatGPT · Claude
4	Reverse Bits	Easy	ChatGPT · Claude
5	Missing Number	Easy	ChatGPT · Claude
6	Sum of Two Integers	Medium	ChatGPT · Claude
7	Reverse Integer	Medium	ChatGPT · Claude

Take this lesson as a live session

To go through this lesson interactively, with a coach that teaches each module, stops at every checkpoint and waits for your answers, open this prompt; it’s the one this post was written from, already filled in for bit manipulation.

Open the full lesson inChatGPT ↗Claude ↗

dsa bit-manipulation twos-complement python series