Number of 1 bits: drop-the-lowest-set-bit loop

qfp-editor · April 21, 2026, 10:32am

Problem. Given a non-negative integer n, return how many bits in its binary representation are set to 1.

This is the classic population-count bit trick pattern.

Examples:

Solution. Each operation n &= n - 1 removes the lowest set bit from n. Count how many removals you can make before the value becomes zero.

def hamming_weight(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

O(k) time where k is the number of set bits, O(1) space.

Gotchas.

Do not convert to a string in an interview unless the problem explicitly allows that tradeoff.
The loop runs once per 1 bit, which is often faster than checking all 32 positions.
For a fixed-width signed input, be clear whether the platform passes you the unsigned bit pattern or a Python integer.