Total Set Bits from 1 to N

Problem Given a number N, count the total number of set bits (1s) across the binary representations of every integer from 1 to N inclusive.

Input / Output

• Input: a single integer N.
• Output: the total count of 1-bits appearing in 1, 2, …, N.

Constraints

• N can be large (10^9 or beyond), so looping over every number and counting its bits at O(N log N) is too slow; the target is O(log N).
• The running total exceeds 32 bits for large N — accumulate in 64-bit.
• N may be 0, in which case the answer is 0.

Example

• N=4 → 1, 10, 11, 100 → 1 + 1 + 2 + 1 = 5.
• N=3 → 1, 10, 11 → 1 + 1 + 2 = 4. Going from N=3 to N=4 adds only a single bit, since powers of two are the sparsest numbers — a good spot check for any formula.