4.30.2 — Number of 1 Bits

LeetCode 191 · Easy · ★ Blind 75

The problem

Count the set bits in a 32-bit unsigned integer. This count is called the Hamming weight, or the population count.

n = 11    (binary 1011)         →  3
n = 128   (binary 10000000)     →  1

The obvious solution

Check each of the 32 bits:

count = 0
for i in range(32):
    if n & (1 << i):
        count += 1
return count

O(32), which is constant — and it does the same work whether n has one set bit or thirty-two.

The better idiom

while n:
    n &= n - 1        # clears the LOWEST set bit
    count += 1

This is Brian Kernighan's method, and the loop runs exactly as many times as there are set bits. For n = 128 that is one iteration instead of thirty-two.

Why n & (n - 1) clears the lowest set bit. Subtracting 1 borrows: the lowest 1 becomes 0, and every 0 below it becomes 1. Everything above is untouched. ANDing with the original therefore keeps only the bits above the lowest 1.

n       = 1011 0100
n - 1   = 1011 0011      ← lowest 1 flipped, zeros below became 1
n & (n-1) = 1011 0000    ← that bit gone

Understand this rather than memorising it. It also gives you the power-of-two test — n > 0 and n & (n - 1) == 0, since a power of two has exactly one set bit and clearing it leaves zero.

The solution

Python

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1              # clear the lowest set bit
            count += 1
        return count

TypeScript

function hammingWeight(n: number): number {
  let count = 0;
  while (n !== 0) {
    n &= n - 1;
    count++;
  }
  return count;
}

In JavaScript, n must stay non-negative for the while (n !== 0) test. Bitwise operators coerce to 32-bit signed integers, so a value with the top bit set becomes negative and the loop still terminates correctly — because n &= n - 1 strictly reduces the number of set bits regardless of sign. Worth checking rather than assuming.

In Python, negative inputs would loop forever, since Python integers have infinitely many leading 1s. The problem gives an unsigned value, so it does not arise — but it is the kind of assumption to state.

Complexity

O(\text{number of set bits}), at most 32. O(1) space.

The three faster methods

Worth naming, in increasing order of cleverness.

A lookup table. Precompute the count for all 256 byte values, then sum four lookups per 32-bit integer. O(1) with four memory accesses, and it is what many libraries did before hardware support.

The SWAR trick. A sequence of masked shifts and adds counts bits in parallel within the word — pairs, then nibbles, then bytes — in about twelve operations with no loop and no table. Elegant and unmemorable; know it exists.

The hardware instruction. Modern CPUs have POPCNT, and compilers emit it for __builtin_popcount in C, Integer.bitCount in Java, and int.bit_count() in Python 3.10+. In real code, use the built-in.

bin(n).count('1') in Python is also perfectly acceptable and often the fastest thing you can write — but in an interview, write the loop, since the loop is what is being asked about.

Where this goes next

• Counting Bits — the count for every number from 0 to n, where DP beats calling this function repeatedly. 4.30.3.
• Hamming Distance — the number of differing bits between two numbers, which is popcount(x ^ y). One line, and it is the foundation of error-correcting codes (Chapter 1.8).
• Bitmask DP — the population count of a mask tells you how many items a subset holds, which is often part of the DP state.
• Power of Two — n > 0 and n & (n - 1) == 0.

What the interviewer will push on

"Explain n & (n - 1)." The borrow argument. This is the question.

"How many iterations does your loop run?" Once per set bit, not 32.

"How would you test for a power of two?" The same idiom, and say why.

"What is the fastest way in production?" The built-in, which compiles to a single instruction.

"What about negative numbers?" In Python the loop would never end; in JavaScript the 32-bit coercion keeps it finite. Naming your language's behaviour is the answer.

One thing to volunteer: derive the idiom on a small binary number out loud. It takes fifteen seconds and it converts a memorised trick into something you obviously understand.

Next: 4.30.3 Counting Bits — the same count for every number up to n, in one pass.