Number of 1 Bits

Number of 1 Bits (also called the Hamming weight) asks how many 1s are in the binary form of a number. The naive answer loops over all 32 bits; the slick answer touches each 1 exactly once using a single bitwise trick.

The slow way first

The obvious idea: check every bit position. Loop 32 times, and each time test whether the lowest bit is set with n & 1, add it to the count, then shift n right by one. That works and is O(number of bits) — always 32 iterations, even for a number with a single 1.

The question to ask: can I skip straight from one 1 to the next, instead of walking past all the 0s? There is a classic bit trick that does exactly that.

The idea: drop the lowest 1-bit each step

Look at n - 1. Subtracting one flips the lowest 1 bit to 0 and turns every 0 below it into a 1. So n & (n - 1) keeps all the higher bits unchanged but clears the lowest set bit. Repeat that, counting once per clear, until n becomes 0. The loop runs exactly once per 1-bit — nothing wasted on the zeros.

The key insight: n & (n - 1) removes one 1 per step, so the number of steps equals the number of set bits — not the number of bit positions.

Walk through it

Step through the animation. n = 11 shows as 00001011. Each iteration highlights the lowest 1 bit (the one n - 1 is about to flip), then clears it and bumps count. After three clears the strip is all zeros, n is 0, and we return count = 3.

Pseudocode

count = 0
while n is not zero:
    n = n AND (n - 1)     # clears the lowest 1-bit
    count = count + 1     # we removed exactly one 1
return count

The Python solution

def hamming_weight(n):
    count = 0
    while n:
        # n & (n - 1) clears the lowest set bit
        n &= n - 1
        count += 1
    return count

• count tracks how many 1 bits we have removed so far.
• while n: keeps looping as long as n still has any 1 bit (n is non-zero).
• Line 5 is the trick: n &= n - 1 clears the lowest set bit and leaves the rest alone.
• We add one to count for every bit we clear, so the total equals the number of set bits.
• When n reaches 0 there are no more 1s, and we return the count.

Complexity

We loop once per 1 bit instead of once per bit position, so a number with few 1s finishes fast. The trick uses no extra storage — just the integer itself — so space is O(1).

When this pattern shows up

Practice