Number of 1 Bits

Counting the 1 bits of a number — its population count or Hamming weight — is the shortest bit question there is. It shows up as a warm-up, and as a building block inside other problems: Hamming distance, power-of-two checks, and bitmask problems that ask "how many items are in this set?". The interviewer wants to see the n & (n - 1) trick and hear you explain why it works.

The problem

You get an unsigned 32-bit integer. Return how many of its bits are 1.

Example 1. 11 → 3. In binary, 11 is 1011: three 1s.

Example 2. 128 → 1. 128 is 10000000, a power of two.

Example 3. 4294967293 → 31. That is 11111111111111111111111111111101: every bit except bit 1.

Constraints. The input is between 0 and 2³² − 1.

Clarifying questions

• Is the input really unsigned? Yes. In Java it would arrive as a signed int, and you would use >>>; in Python it is a plain non-negative integer.
• May I use a built-in? Ask. Python 3.10+ has n.bit_count(), and bin(n).count("1") works everywhere. Say you know them, then write the bit version.
• Will this be called many times? It often is, as a follow-up. See below.

Approach 1: the simple way

Look at every one of the 32 positions. Check the lowest bit with n & 1, then shift right.

1def hamming_weight_simple(n: int) -> int:2    """Check all 32 positions, lowest first."""3    count = 04    for _ in range(32):5        count += n & 1          # 1 if the lowest bit is set6        n >>= 17    return count

This is O(32) time and O(1) space, and it is correct. Nothing about it is too slow for one call. The weakness is that it always does 32 steps, even for 128, which has a single 1 bit. When this function sits in the inner loop of something bigger — counting bits for every subset, every pair of numbers — the wasted steps add up. The interviewer's follow-up is: "can you make the work depend on the number of 1 bits instead?"

The key insight

We want a step that removes one 1 bit each time, no matter where it is. Then the loop runs exactly as many times as there are 1s.

Subtracting 1 does something special in binary. Take 44 = 101100. To subtract 1, you borrow from the lowest 1 bit: it becomes 0, and every 0 below it becomes 1. Everything above it stays the same. So 43 = 101011.

Now AND the two:

n       = 1 0 1 1 0 0     (44)n - 1   = 1 0 1 0 1 1     (43)n & n-1 = 1 0 1 0 0 0     (40)

Above the lowest 1, both numbers agree, so those bits survive. At the lowest 1 and below it, one of the two always has a 0, so everything there becomes 0. The result is n with its lowest 1 bit erased. This was discovered by several people; it is often called Kernighan's trick.

Approach 2: clear one set bit per step

1def hamming_weight(n: int) -> int:2    """Clear the lowest set bit until nothing is left."""3    count = 04    while n:5        n &= n - 1              # erase exactly one 1 bit6        count += 17    return count

Step by step:

1. While any bit is still set, erase the lowest one.
2. Count each erase.
3. When n reaches 0, the count is the number of 1s that were there.

Dry run on 44:

Three steps for three 1 bits. For 128 it is one step; the simple version would take 32.

Complexity. O(k) time, where k is the number of 1 bits — at most 32, often much fewer. O(1) space.

One honest note about Python: the built-ins run in C, so n.bit_count() is faster than either loop. In an interview, write the loop to show the idea, then mention the built-in as what you would use in production.

Edge cases

• Zero. The loop never runs; the answer is 0. The simple version also returns 0.
• All 32 bits set (4294967295). 32 iterations; the worst case.
• A negative number in Python. If a problem hands you a signed 32-bit value like -3, while n: never ends: -3 & -4 is -4, then -8, and so on, forever moving left. Mask first: hamming_weight(-3 & 0xFFFFFFFF) gives 31. Beware the built-in too: (-3).bit_count() returns 2, because it counts the bits of the absolute value.

Follow-ups

• "Is n a power of two?" A power of two has exactly one 1 bit, so one step of the trick leaves zero: n > 0 and (n & (n - 1)) == 0. The n > 0 guard is essential, because 0 also passes the second test.
• "How many bits differ between x and y?" (Hamming distance.) XOR marks exactly the positions that differ, so count the 1s of x ^ y. For 1 (001) and 4 (100), 1 ^ 4 = 101, two bits.
• "This is called millions of times. Make it faster." Precompute a table of the counts for all 256 byte values, then answer with four lookups: table[n & 0xFF] + table[(n >> 8) & 0xFF] + table[(n >> 16) & 0xFF] + table[n >> 24]. The table costs 256 entries once. Modern CPUs also have a single popcount instruction, which is what bit_count uses.