Introduction

If the goal is to count how many 1 bits appear in all numbers across a range, iterating through every integer and counting bits one by one is correct but often too slow. A much better approach is to compute the total number of set bits from 0 to n, then subtract two prefix totals to get any range answer.

The Slow but Obvious Solution

The direct method is:

1. loop from left to right
2. count the 1 bits of each value
3. sum them

That works, but the complexity is roughly O((right - left + 1) * word_size). For small ranges it is fine. For large ranges, it wastes structure that binary numbers naturally provide.

Use a Prefix Function

Define count_ones_upto(n) as the total number of set bits in all integers from 0 through n. Then the answer for any inclusive range is:

count_ones_upto(right) - count_ones_upto(left - 1)

That turns the range problem into a faster prefix problem.

Key Observation About Powers of Two

Consider all numbers from 0 to 2^k - 1. Across that full block, each bit position is 1 exactly half the time. There are 2^k numbers and k bit positions, so the total number of set bits in that block is:

k * 2^(k - 1)

That identity is the basis of the fast recursive or iterative solution.

Derive the Recurrence

Suppose n is positive and the highest power of two not exceeding n is p = 2^k.

Then the range 0..n can be split into:

• '0..p-1'
• 'p..n'

The first block contributes k * 2^(k - 1) set bits.

In the second block:

• the most significant bit is set in every number, contributing n - p + 1
• the remaining lower bits behave exactly like the numbers 0..(n - p)

So:

count_ones_upto(n) = k * 2^(k - 1) + (n - p + 1) + count_ones_upto(n - p)

That reduces the problem quickly because each step removes the top bit.

Python Implementation

1def count_ones_upto(n: int) -> int:
2    if n <= 0:
3        return 0
4
5    total = 0
6
7    while n > 0:
8        k = n.bit_length() - 1
9        p = 1 << k
10
11        bits_in_full_block = k * (p >> 1)
12        msb_contribution = n - p + 1
13
14        total += bits_in_full_block + msb_contribution
15        n -= p
16
17    return total
18
19
20def count_ones_in_range(left: int, right: int) -> int:
21    if left > right:
22        return 0
23    return count_ones_upto(right) - count_ones_upto(left - 1)
24
25
26print(count_ones_in_range(5, 7))   # 7
27print(count_ones_in_range(0, 10))  # 17

This runs in O(log n) time for the prefix function because each loop step removes one highest set bit.

Why It Works on a Sample

Take the range 5..7:

• '5 is 101, so it has 2 ones'
• '6 is 110, so it has 2 ones'
• '7 is 111, so it has 3 ones'

The total is 7.

Using the prefix function:

• 'count_ones_upto(7) is 12'
• 'count_ones_upto(4) is 5'
• '12 - 5 = 7'

The same answer appears without scanning every value in the target range.

When Per-Number Counts Are Needed

Sometimes the problem is not the total across the range, but the popcount of each number from 0 to n. In that case, dynamic programming is often better:

1def popcounts(n: int) -> list[int]:
2    bits = [0] * (n + 1)
3    for i in range(1, n + 1):
4        bits[i] = bits[i >> 1] + (i & 1)
5    return bits

That solves a related problem efficiently, but it is a different output shape from the single total count.

Common Pitfalls

• Mixing up "count the ones in each number" with "count the total ones across the whole range" leads to the wrong algorithm.
• Forgetting that the range is inclusive causes off-by-one errors in the subtraction formula.
• Using the fast prefix recurrence without handling left = 0 carefully can produce negative-index style mistakes in surrounding code.
• Recomputing bit counts for every integer is acceptable for tiny ranges, but it does not scale.
• Confusing the highest power of two with the highest set bit position leads to incorrect recurrence terms.

Summary

• The fastest general approach is to compute total set bits from 0..n, then subtract prefix totals.
• The core recurrence comes from how often each bit is set in a full power-of-two block.
• 'count_ones_upto(n) can be implemented in O(log n) time.'
• For per-number popcounts, use a different dynamic-programming approach instead of the range-total formula.