The problem
Count how many 1 bits are in the binary form of a number.
Input: n = 11 (binary 1011) Output: 3
Picture it
Picture a panel of light switches showing the number in binary. We want the number of lights that are on. Trick: n & (n − 1) switches off the lowest light that is on. Keep doing that until all lights are off, counting the steps.
How to recognise it
- The question is about the binary form of a number: how many of its bits are 1 (the "population count" or Hamming weight).
- Bit operators (
&,>>) answer this without converting to a string. - The input is a positive 32-bit integer (1 ≤ n ≤ 2^31 − 1 on LeetCode), so any approach is fast; the interest is the trick
n & (n - 1).
Start with brute force
Look at each of the 32 bit positions in turn and count the ones that are set.
def hw_brute(n):
count = 0
for i in range(32):
if (n >> i) & 1:
count += 1
return count
That is always 32 steps: O(1) for a fixed width, or O(w) for w bits. It is not slow. Its only waste is that it checks every 0 bit too, and it silently ignores bits above position 31.
From brute force to the idea
- Find the waste. For a number like 128 (binary 1000 0000) the loop checks 32 positions to find one 1.
- See what
n - 1does. Subtracting 1 turns the lowest 1 bit into 0 and every 0 below it into 1. For 12 (1100),n - 1is 11 (1011). - AND them.
n & (n - 1)keeps every bit above the lowest 1 and clears that bit and everything below: 1100 & 1011 = 1000. So each step switches off exactly one 1 bit. - Count the steps. Repeat until
nis 0. The number of steps is the number of 1 bits.
This is the key idea: n &= n - 1 clears the lowest set bit, so the loop runs once per 1 bit, not once per bit position.
Python also has bin(n).count("1") and, from Python 3.10, n.bit_count().
The key idea
Repeat n &= n − 1, counting iterations: one step per 1 bit.
Python solution
def hamming_weight(n):
count = 0
while n:
n &= n - 1 # switches off the lowest light
count += 1
return countIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (check all 32 bits) | O(32): every position checked | O(1) |
| Clear the lowest bit (shown code) | O(k): one step per 1 bit, at most 31 for LeetCode's inputs | O(1) |
Both are constant for 32-bit numbers; the shown loop does fewer steps when few bits are set.
Edge cases
- n = 0: the loop never runs; returns 0.
- n = 2^31 − 1 (31 ones): returns 31.
- A power of two (128): one step, returns 1.
- More than 32 bits: Python integers have no fixed width, so
hamming_weight(2**40)returns 1, while the 32-position brute force returns 0. - Negative numbers: the shown code never stops. In Python,
-1 & -2is-2, then-4,-8, and so on:nnever reaches 0. LeetCode's inputs are positive, so this does not arise there; for a 32-bit two's complement view, call it onn & 0xFFFFFFFF(−1 then gives 32).
Common mistakes
- Getting precedence wrong when porting: in Python
n & n - 1isn & (n - 1)andn & 1 == 1is(n & 1) == 1, but in C and Javan & 1 == 1meansn & (1 == 1). Brackets make the intent clear in every language. - Using
n >>= 1on a negative number in a loopwhile n:, which also never ends (−1 >> 1 is −1). - Counting characters of
bin(n)withoutcount("1"), which includes the0bprefix.
Return the number of bit positions where two non-negative integers x and y differ (LeetCode 461). For x = 1 (001) and y = 4 (100) the answer is 2. Describe your approach, then write it if you like.
Compare with our answer
XOR marks exactly the positions where the two bits differ: x ^ y has a 1 there and a 0 elsewhere. Then count the 1 bits with the same trick.
def hamming_distance(x, y):
n, count = x ^ y, 0
while n:
n &= n - 1
count += 1
return count
Time O(k) for k differing bits, space O(1).
A strong answer mentions: that XOR gives 1 exactly where the bits differ, reusing the lowest-bit trick, and that the inputs are non-negative so the loop ends.
1. You must check whether a positive integer is a power of two in O(1). Which test fits best?
Clearing the lowest 1 bit of a power of two leaves 0. Evenness and "ends in 0" also hold for 6 or 12, and n >> 1 == n // 2 is true for every non-negative n. (In Python, n & (n - 1) == 0 already groups correctly, because == binds looser than &.)
2. How many times does the shown loop run for n = 11 (binary 1011)?
Each n &= n - 1 clears one 1 bit: 1011 → 1010 → 1000 → 0. So the loop runs once per 1 bit, here 3 times.
3. What does the shown code do when called with n = −1 in Python?
Python integers are unbounded, so −1 has infinitely many 1 bits: n & (n - 1) goes −2, −4, −8, ... and never reaches 0. Masking with 0xFFFFFFFF first gives 32.
Score 60% or more and the lesson is marked complete.