LeetCode 191 · Bit Manipulation

Number of 1 Bits, explained with a picture

Counting the lights that are on.

EasyBit Manipulation
▶ Watch it step by step

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

  1. Find the waste. For a number like 128 (binary 1000 0000) the loop checks 32 positions to find one 1.
  2. See what n - 1 does. Subtracting 1 turns the lowest 1 bit into 0 and every 0 below it into 1. For 12 (1100), n - 1 is 11 (1011).
  3. 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.
  4. Count the steps. Repeat until n is 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 count

In 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

ApproachTimeSpace
Brute force (check all 32 bits)O(32): every position checkedO(1)
Clear the lowest bit (shown code)O(k): one step per 1 bit, at most 31 for LeetCode's inputsO(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 & -2 is -2, then -4, -8, and so on: n never reaches 0. LeetCode's inputs are positive, so this does not arise there; for a 32-bit two's complement view, call it on n & 0xFFFFFFFF (−1 then gives 32).

Common mistakes

  • Getting precedence wrong when porting: in Python n & n - 1 is n & (n - 1) and n & 1 == 1 is (n & 1) == 1, but in C and Java n & 1 == 1 means n & (1 == 1). Brackets make the intent clear in every language.
  • Using n >>= 1 on a negative number in a loop while n:, which also never ends (−1 >> 1 is −1).
  • Counting characters of bin(n) without count("1"), which includes the 0b prefix.
Your turn: Hamming distance

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.

Check what stuck

1. You must check whether a positive integer is a power of two in O(1). Which test fits best?

2. How many times does the shown loop run for n = 11 (binary 1011)?

3. What does the shown code do when called with n = −1 in Python?

Score 60% or more and the lesson is marked complete.