For a non-negative integer x, let popcount(x) be the number of 1-bits in its binary representation. Given n, compute the sum of popcount(x) over every integer x from 0 to n inclusive.
Because n can be as large as one billion, an approach that inspects every integer one at a time will be too slow; count the contribution of each bit position instead.
A single line containing one integer n.
A single integer: the total number of set bits across all integers in the range 0..n.
Example 1
Input
5
Expected
7
Explanation
popcount of 0..5 is 0,1,1,2,1,2 which sums to 7.
Example 2
Input
0
Expected
0
Explanation
The only integer in range is 0, whose binary form has no set bits, so the total is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →