Number of 1 Bits — The Punch Card Count

Boss 2: The Punch Card Count

Boss 1 handed you the XOR wand: pair things up and watch them cancel. This boss hands you the other half of the starter kit. AND, used not as a blunt filter but as a scalpel, one that removes exactly one bit per cut. Between "XOR cancels" and "AND clears", most of this dungeon's remaining bosses are already half-dead.

The problem itself looks almost insultingly small. Count the 1s in a number. That's it. Which is exactly why interviewers love it: the naive answer takes ten seconds, and the good answer reveals whether you actually understand what subtraction does to bits.

The story

The city archive keeps a basement of machine punch cards, thousands of them, each one a strip of 32 columns. A punched hole means 1. An untouched blank means 0.

The archivist bills clients per hole. Every card that comes off the shelf needs its holes counted before it ships, and the queue behind you is long.

card #180:   0 0 0 ... 1 0 1 1 0 1 0 0
                       ↑   ↑ ↑   ↑
                     four holes punched

Your first shift, you do it the obvious way: slide a finger across all 32 columns, hole, blank, blank, hole. It works. It's also mostly a tour of blank paper, because a typical card has a handful of holes and a wasteland of zeros.

The retired archivist watches you for a minute, then shows you the house trick: a way to jump finger-to-hole directly, skipping every blank column in between. Four holes, four moves, done.

The problem, dressed up properly

Given a 32-bit unsigned integer, return the number of 1 bits it has (also known as the Hamming weight).

LeetCode 191, "Number of 1 Bits". The gentlest-rated boss in the dungeon, and the one whose trick you'll reuse the most.

The naive attempt

Two honest baselines. The lazy one turns the card into text:

def hamming_weight(n: int) -> int:
    return bin(n).count("1")

Correct, short, and it teaches you nothing. It also allocates a brand-new string just to count characters in it, which is a silly thing to do in a hot loop. Python even has int.bit_count() since 3.10, which is the real production answer. But an interview isn't asking "can you find the stdlib", it's asking "do you know what the bits are doing".

The honest baseline checks every column yourself:

def hamming_weight(n: int) -> int:
    count = 0
    for _ in range(32):
        count += n & 1     # is the lowest column a hole?
        n >>= 1            # slide to the next column
    return count

n & 1 peeks at the lowest bit, n >> 1 shifts the card over by one column. Thirty-two peeks, always, even when the card has one lonely hole at the top. This is your finger touring the blank paper.

The weapon: erase the lowest hole

Here's the archivist's trick, and it starts from a question that sounds unrelated: what does subtracting 1 actually do to a binary number?

Subtraction borrows. Take n = 180, binary 10110100. To subtract 1, you need a 1 in the lowest column, but there's a 0 there. So you borrow from the next column. Also 0. Borrow again. The borrow ripples left until it finds the lowest 1, consumes it, and turns every 0 it passed into a 1:

n     = 10110100
n - 1 = 10110011
           ↑ ↑↑
   lowest 1 became 0, trailing 0s became 1s

Everything above the lowest set bit is untouched. Everything at-or-below it is flipped. Now AND the two together:

• Above the lowest 1: both numbers agree, so those bits survive.
• At the lowest 1: n has 1, n - 1 has 0. Cleared.
• Below it: n has 0s, n - 1 has 1s. Still 0.

So n & (n - 1) is n with its lowest set bit surgically removed, and nothing else changed. One expression, one hole erased. That's Brian Kernighan's trick, and it turns hole-counting into a loop that runs once per hole instead of once per column.

def hamming_weight(n: int) -> int:
    count = 0
    while n:
        n &= n - 1     # erase the lowest hole
        count += 1     # bill it
    return count

Five lines. The loop body never inspects a blank column, because n & (n - 1) teleports straight to the next hole.

Watching it work

Card #180, binary 10110100, four holes. Watch each AND erase exactly one:

step  n          n - 1       n AND (n - 1)   count
1     10110100   10110011    10110000        1
2     10110000   10101111    10100000        2
3     10100000   10011111    10000000        3
4     10000000   01111111    00000000        4
n is zero → return 4 ✓

Four holes, four iterations. The naive loop would have taken 32. And notice step 4: 128 & 127 wipes the whole card in one move, because 127 is all-ones below that final hole. The borrow rippled through seven columns to find it, and the AND cashed that in.

Gotchas

1. Negative numbers can loop forever in the shift version. In Java, n >> 1 is an arithmetic shift: it drags the sign bit along, so a negative n never reaches zero and while (n != 0) with >> spins forever. Java wants >>>, the unsigned shift. Kernighan's loop dodges this entirely on fixed-width ints, since each step strictly removes a bit.

2. Python integers have no 32-bit edge. Python ints are arbitrary-width, so a negative number has infinitely many conceptual sign bits, and both -1 >> 1 and Kernighan on -1 never terminate. LeetCode feeds you non-negative input so you're safe there, but when porting bit code to Python, mask first: n &= 0xFFFFFFFF gives you the 32-bit view the other languages had for free.

3. Clearing the lowest bit is not the same as keeping it. n & (n - 1) removes the lowest set bit. Its sibling n & -n isolates it, throwing away everything else. Both show up in interviews, both look like line noise, and swapping them turns a popcount into an infinite loop. Clear-vs-keep. Say it out loud before you type.

4. String conversion in a hot path. bin(n).count("1") builds a fresh string per call. Fine for one card, ugly for a million. If you genuinely need bulk popcounts in Python, int.bit_count() is a C-speed primitive. Everywhere else, Kernighan.

Complexity

The naive loop pays for every column. Kernighan pays only for holes: with k set bits, the loop runs exactly k times.

Time: O(k) with k = number of set bits, versus O(32) for the column walk. Space: O(1).

Worst case (all 32 holes punched) they tie. On real, mostly-blank cards, Kernighan wins by miles.

Boss down

The archivist stamps your card and slides the bill across the counter. Two bosses in, and the dungeon's grammar is taking shape: Boss 1 taught XOR as a cancel, this one taught AND as a surgical clear. Nearly every trap ahead is some combination of those two moves.

Next up, Boss 3: Counting Bits — The Locker Stencils. Same archive, nastier order: the hole count for every card number from 0 to n, all at once. Running this boss's loop n times works, but there's a way to make each answer steal from an earlier one, and suddenly a weapon from Dungeon 12's DP halls is back in your hand. Bring it.