1303. Counting Every Set Bit From Zero to n
Given n, print the total number of 1 bits in the binary forms of all the
values 0, 1, 2, ..., n added together.
n=0 -> 0
n=1 -> 1 0, 1
n=3 -> 4 0, 1, 10, 11 gives 0 + 1 + 1 + 2
n=7 -> 12
## What most people try first
A loop over 0..n with a popcount each time. Correct, O(n log n), and at
n = 10^15 it is a thousand million million popcounts. Nothing can be pruned,
because every value contributes a different amount.
The recurrence dp[i] = dp[i >> 1] + (i & 1) from #1305 makes each popcount
O(1), which reduces the cost to O(n) and still cannot finish, and it needs
O(n) memory on top. A faster popcount is not the answer; not visiting the
values is.
## Count by POSITION, not by value
Swap the order of summation. Instead of "for each value, how many bits", ask "for each bit position, how many values have it set":
total = sum over positions b of (how many v in [0, n] have bit b set)
This is legitimate because both orders count exactly the same set of
(value, position) pairs where the bit is 1, and there are only about 50
positions below 10^15.
## Counting one position exactly
Look at bit b as v runs upward from 0. It follows a strict cycle: 2^b
zeros, then 2^b ones, repeating with period 2^(b+1).
b = 0: 0 1 0 1 0 1 ... period 2, one zero then one one
b = 1: 0 0 1 1 0 0 1 1 ... period 4, two zeros then two ones
b = 2: 0 0 0 0 1 1 1 1 ... period 8
So over the n + 1 values from 0 to n, count the complete periods and then
the leftover:
block = 2^(b+1)
half = 2^b
full = (n + 1) / block complete periods, integer division
rem = (n + 1) % block the leftover prefix of a period
count = full * half + max(0, rem - half)
The max(0, rem - half) is the part to get right. The leftover is a prefix of
one period, which begins with half zeros and then has ones. If the leftover is
no longer than half it contains no ones at all, hence the max with 0;
otherwise it contains rem - half of them.
## Checking it on n = 7
b = 0: block = 2, half = 1, full = 8/2 = 4, rem = 0, count 4.
b = 1: block = 4, half = 2, full = 2, rem = 0, count 4.
b = 2: block = 8, half = 4, full = 1, rem = 0, count 4.
Higher positions contribute 0. Total 12, matching the statement.
## Cost
O(log n): about 50 iterations of a handful of integer operations, with
constant space, against O(n) at best for any method that visits the values.
#1304 prints the per-position counts rather than their total, which makes this
decomposition visible, and #1257 applies the same reorganisation to a different
per-value quantity.
## Width
At n = 10^15 the total is 24784747400675348, about 2.5 * 10^16. That is
past the 2147483647 a signed 32-bit integer holds by seven orders of
magnitude, and also past 2^53 = 9007199254740992, the largest integer a double
represents exactly, by a factor of nearly three. So the accumulator must be a
64-bit integer, whose limit is 9223372036854775807, and in JavaScript it must
be BigInt rather than Number.
The intermediate n + 1 is at most 10^15 + 1 and block at most 2^50, both
comfortably inside 64 bits.
Constraints - `0 ≤ n ≤ 1000000000000000`
Input
A single line containing the integer n.
Output
Print one integer on its own line: the total number of 1 bits across the binary forms of every value from 0 to n inclusive.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.