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.
Input format
A single line containing one integer n.
Output format
A single integer: the total number of set bits across all integers in the range 0..n.
Constraints
- 0 ≤ n ≤ 1000000000