Number of 1 Bits
Count the set bits in a number, and learn the n & (n-1) trick that skips every zero
Problem Statement
Given an unsigned integer, return the number of 1 bits it contains. This count is also called the Hamming weight.
Input: n = 11 binary 1 0 1 1
Output: 3
Input: n = 128 binary 1 0 0 0 0 0 0 0
Output: 1
Input: n = 0
Output: 0Intuition
The direct approach: look at every bit position, check whether it is a 1, move on.
n = 11 1 0 1 1
↑ ↑ ↑ ↑
check each: 1+0+1+1 = 3You check the last bit with n & 1, then shift the number right to bring the next one into position. Repeat until nothing is left. That works and it is O(32) — 32 iterations for a 32-bit number, whatever the input.
But look at n = 128. That is 1 followed by seven zeros. The loop above checks all eight positions to find one bit, and seven of those checks learn nothing.
The insight
n & (n - 1) removes the lowest set bit and leaves everything else alone.
So instead of walking past the zeros, jump straight from one 1 to the next. Count how many jumps it takes to reach zero — that is the answer.
The loop now runs once per set bit, not once per position.
Why n & (n - 1) Works
Subtracting 1 from a binary number does two things: it flips the lowest 1 to 0, and it turns every 0 below that into 1.
n = 1 0 1 1 0 0 (44)
↑ lowest set bit
n - 1 = 1 0 1 0 1 1 (43)
↑ flipped to 0, the zeros below became ones
n&(n-1) = 1 0 1 0 0 0 (40)Compare n and n - 1 column by column. Above the lowest set bit they are identical, so AND keeps those unchanged. At the lowest set bit and below they are exactly opposite, so AND turns all of them to 0.
Net effect: one bit removed, nothing else disturbed.
Approach
While n is not zero, clear its lowest set bit
n = n & (n - 1). Each clearing removes exactly one 1.
Count the clearings
When n reaches 0, every set bit has been removed, and the counter holds how many there were.
Solution
def hamming_weight(n: int) -> int:
"""Count the set bits in n.
Each `n &= n - 1` clears exactly one set bit, so the loop runs
once per 1 rather than once per bit position.
"""
count = 0
while n:
n &= n - 1
count += 1
return countPython also offers bin(n).count("1") and, from 3.10, n.bit_count(). Both are fine in real code — the loop is what the problem is asking you to understand.
Complexity Analysis
Time Complexity
O(k)
Space Complexity
O(1)
Time — k is the number of set bits, at most 32 for a 32-bit integer. So it is O(1) in the strict sense, but the useful statement is that it is proportional to the number of ones, not the width of the number.
Space — a single counter.
Comparing the two loops
| Shift-and-check | n & (n - 1) | |
|---|---|---|
| Iterations | Always 32 | Once per set bit |
n = 128 | 8 | 1 |
n = 0 | 32 (or 0, if you exit early) | 0 |
n = all ones | 32 | 32 |
They match in the worst case. The trick wins on sparse numbers, which is most real input.
Edge Cases
Related Problems
- Counting Bits — this same count, for every number from 0 to n, done faster
- Single Number — the other essential bit operation