Number of 1 Bits (LeetCode 191)

The problem

Given a non-negative integer n (treated as an unsigned 32-bit value), return how many bits in its binary form are 1. This count is also called the Hamming weight or popcount.

Input:  11
Output: 3

11 is 1011 in binary, which has three 1s.

How to think about it

Start with brute force. Check each of the 32 bits: if n & 1: count += 1, then n >>= 1. That is 32 steps every time, which is already O(1), but it spends steps on zeros.

The key insight: n & (n - 1) clears the lowest set bit. Subtracting 1 flips the lowest 1 to 0 and turns every 0 below it into 1. Everything above stays the same. So n & (n - 1) keeps the higher bits and wipes out that lowest 1 and the bits below it.

n       = 10100   (20)
n - 1   = 10011   (19)
n & n-1 = 10000   (16: the lowest 1 is gone)

So count the steps until zero. Each n &= n - 1 removes exactly one set bit. The loop runs once per 1 bit, not once per bit position. For sparse numbers that is much faster.

Which pattern is this? Bit manipulation, the “clear lowest set bit” trick (often credited to Brian Kernighan). The tell is “count set bits” or “is it a power of two” (a power of two has exactly one set bit, so n & (n - 1) == 0).

Approach

1. Set c = 0.
2. While n is not zero, replace n with n & (n - 1) and add one to c.
3. Return c.

Solution

def hamming_weight(n):
    c = 0
    while n:
        n &= n - 1      # drop the lowest set bit
        c += 1
    return c
# hamming_weight(11) -> 3   (1011 has three 1s)

Dry run

On n = 11:

n is now 0, so the loop stops with 3.

Complexity

• Time: O(k), where k is the number of set bits, at most 32.
• Space: O(1).

Edge cases and pitfalls

• n = 0 returns 0; the loop never runs.
• All 32 bits set (2**32 - 1) returns 32.
• Negative input in Python. Python ints are unbounded, so a negative n has infinitely many 1 bits and this loop never ends. If the input can be negative, first do n &= 0xFFFFFFFF. LeetCode’s Python version passes a non-negative value.
• bin(n).count("1") is a fine one-liner in real code, but interviewers usually want the bit trick.

Related problems

• Counting Bits (LeetCode 338): popcount for every number from 0 to n, with DP.
• Reverse Bits (LeetCode 190): another bit-by-bit walk over a 32-bit value.
• Single Number (LeetCode 136): the other basic bit trick, XOR cancellation.