Bit ManipulationMath
Count the total number of 1 bits in the binary representations of all the numbers from 1 to n. For large n you cannot count them one by one, so look for a pattern.
Input
A single integer n.
Output
Print the total number of set bits across 1, 2, ..., n.
Constraints
1 <= n <= 10^9
Example 1
Input
3
Output
4
1, 10, 11 contain 1 + 1 + 2 = 4 set bits.
Example 2
Input
6
Output
9
The counts for 1..6 are 1 1 2 1 2 2, which add to 9.