Module 25 · Bit Manipulation, Mathematics, and Designed Data Structures

244. Counting Bits from 0 to N

Foundation · Download this solution · All solutions and shared helpers

Problem

Return a list of set-bit counts for every integer from zero through n inclusive, where n>=0. Entry i must describe i. Use previously computed smaller answers instead of independently recounting each number.

Examples

Example 1

counting_bits(5)
=> [0, 1, 1, 2, 1, 2]

Each entry reuses the count after removing its low bit.

Example 2

counting_bits(0)
=> [0]

The inclusive range still contains zero.

Example 3

counting_bits(2)
=> [0, 1, 1]

Binary 10 has one set bit, like binary 1.

Reveal the worked solution and reasoning

Why this mechanism works

Right shift removes the least significant bit, leaving a smaller integer whose count is already known. Add back the removed bit, which is either zero or one. Ascending integer order therefore forms a dynamic program over binary representations.

State and boundaries

counts[i] is the number of one bits in i. Every dependency i>>1 is smaller than i for i>=1.

Protocol

Allocate n+1 zero entries.
For i from 1 through n, set counts[i]=counts[i>>1]+(i&1).
Return the full table.

Visualization

i=5 is binary 101
i>>1=2 is binary 10, count 1
i&1=1 -> count[5]=1+1=2

Python implementation

def counting_bits(n):
    counts = [0] * (n + 1)
    for i in range(1, n + 1):
        counts[i] = counts[i >> 1] + (i & 1)
    return counts

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

counting_bits(5)

L2 counting_bits: counts = [0] * (n + 1)
n=5; counts=[0, 0, 0, 0, 0, 0]

L3 counting_bits: for i in range(1, n + 1):
n=5; counts=[0, 0, 0, 0, 0, 0]; i=1

L4 counting_bits: counts[i] = counts[i >> 1] + (i & 1)
n=5; counts=[0, 1, 0, 0, 0, 0]; i=1

L3 counting_bits: for i in range(1, n + 1):
n=5; counts=[0, 1, 0, 0, 0, 0]; i=2

L4 counting_bits: counts[i] = counts[i >> 1] + (i & 1)
n=5; counts=[0, 1, 1, 0, 0, 0]; i=2

L3 counting_bits: for i in range(1, n + 1):
n=5; counts=[0, 1, 1, 0, 0, 0]; i=3

L4 counting_bits: counts[i] = counts[i >> 1] + (i & 1)
n=5; counts=[0, 1, 1, 2, 0, 0]; i=3

L3 counting_bits: for i in range(1, n + 1):
n=5; counts=[0, 1, 1, 2, 0, 0]; i=4

L4 counting_bits: counts[i] = counts[i >> 1] + (i & 1)
n=5; counts=[0, 1, 1, 2, 1, 0]; i=4

L3 counting_bits: for i in range(1, n + 1):
n=5; counts=[0, 1, 1, 2, 1, 0]; i=5

L4 counting_bits: counts[i] = counts[i >> 1] + (i & 1)
n=5; counts=[0, 1, 1, 2, 1, 2]; i=5

Result: [0, 1, 1, 2, 1, 2]. Each entry reuses the count after removing its low bit.

counting_bits(0)

L2 counting_bits: counts = [0] * (n + 1)
n=0; counts=[0]

Result: [0]. The inclusive range still contains zero.

Why the solution is correct

The binary digits of i consist of the digits of i>>1 followed by its low bit. Their set-bit counts add exactly as the recurrence states. The zero base is correct, and ascending order guarantees the smaller count is complete.

Time and space

O(n) word-level operations and O(n) output entries. Integer indices and operations have logarithmic bit width under an arbitrary-precision analysis.

Common mistakes

Allocating only n entries omits the inclusive endpoint. Adding one unconditionally overcounts even integers.

Reasoning card

State: counts[i] is the number of one bits in i. Every dependency i>>1 is smaller than i for i>=1.

Invariant: Each count is derived from a previously computed integer.

Decision to rehearse: Reuse a smaller solved state such as count[i>>1] + (i&1).

Finish: Return the full table

Transfer exercise

Use counts[i]=counts[i&(i-1)]+1 and connect its dependency to the previous kata's bit-clearing loop.