Count the 1 bits in a number

Bits and maths Junior Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
x = 12
steps = []
while x:
    x &= x - 1
    steps.append(bin(x))
print(steps, (12).bit_count())

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A ['0b1000', '0b0'] 2

Right: 1100 loses its lowest 1 bit twice, so it has two 1 bits.

The loop runs once per 1 bit rather than once per bit position, which matters for sparse numbers.

Why not the others?
  • B ['0b1011', '0b1010'] 2. Those are x - 1 values; the & keeps only bits set in both.
  • C ['0b110', '0b11', '0b1', '0b0'] 2. That is shifting right, not clearing bits.

30-second answer

x & (x - 1) clears the lowest 1 bit, because subtracting 1 flips that bit and every 0 below it. Repeat until x is 0, counting the steps. The loop runs once per 1 bit, at most O(log x) times, with O(1) space. In real code, x.bit_count() does this directly.

Practise saying it · 30 s. No recording, just a timer

Explain counting 1 bits.

Say your answer out loud, then check which of these points you covered:

  • x & (x - 1)
  • One step per 1 bit
  • bit_count() in practice

Deep dive

The 'clear the lowest bit' step is the template for many bit questions.

Checking x & 1 and shifting also works but always runs bit_length times.

For 32-bit negative numbers in Python, mask first: x & 0xFFFFFFFF.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def ones(x: int) -> int:
    count = 0
    while x:
        x &= x - 1  # clears the lowest 1 bit
        count += 1
    return count

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun ones(x: Int): Int {
    var rest = x
    var count = 0
    while (rest != 0) {
        rest = rest and (rest - 1) // clears the lowest 1 bit
        count++
    }
    return count
}

Common mistakes

  • Looping forever on negative Python ints, which have infinitely many 1 bits in two's complement.
  • Using bin(x).count('1') and not mentioning bit_count() exists.

Senior take & follow-ups

Explain why x - 1 flips the lowest 1 bit; one example like 12 is enough.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you check if x is a power of two?

    Show hint

    x > 0 and x & (x - 1) == 0.

  2. How do you count bits for every number up to n?

    Show hint

    Reuse smaller answers: bits[i] = bits[i >> 1] + (i & 1).

What each operation costs: Hash Functions

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.