1-bit counts for every number from 0 to n

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
bits = [0] * 9
for i in range(1, len(bits)):
    bits[i] = bits[i >> 1] + (i & 1)
print(bits)

Options

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

Show answer

Answer: A [0, 1, 1, 2, 1, 2, 2, 3, 1]

Right: for example 7 is 111 (three bits) and 8 is 1000 (one bit).

Each entry costs one shift and one addition, because the count for i >> 1 is always computed first.

Why not the others?
  • B [0, 1, 2, 2, 3, 3, 3, 3, 4]. Those are bit lengths, not counts of 1 bits.
  • C [0, 1, 1, 2, 1, 2, 2, 3, 2]. 8 is a power of two, so it has a single 1 bit.

30-second answer

Dropping the last bit of i (i >> 1) gives a smaller number whose count is already known; add back the dropped bit (i & 1). So bits[i] = bits[i >> 1] + (i & 1). One pass, O(n) time and O(n) space for the table, which beats recounting each number on its own in O(n log n).

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

Explain the 1-bit table for 0 to n.

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

  • bits[i >> 1] + (i & 1)
  • Build on smaller answers
  • O(n)

Deep dive

It is a tiny DP: each answer is built from a smaller one.

bits[i] = bits[i & (i - 1)] + 1 is an equally good recurrence.

The output itself is O(n), so O(n) time is optimal.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def ones_table(n: int) -> list[int]:
    bits = [0] * (n + 1)  # bits[0] stays 0
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)  # drop last bit, add it back
    return bits

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun onesTable(n: Int): List<Int> {
    val bits = IntArray(n + 1)
    for (i in 1..n) bits[i] = bits[i shr 1] + (i and 1)
    return bits.toList()
}

Common mistakes

  • Recounting each number from scratch.
  • Starting the loop at 0 and reading bits[-1].

Senior take & follow-ups

Point out that the answer builds on smaller answers; that is the DP link.

Follow-up questions

Think of your answer first, then open the hint.

  1. Which other recurrence works?

    Show hint

    bits[i] = bits[i & (i - 1)] + 1, using the 'clear the lowest bit' step.

  2. How would you count bits up to 10¹⁸?

    Show hint

    Count per bit position: each bit is 1 for half of every full cycle of length 2ᵏ⁺¹.

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.