Count Set Bits Total
EasyBit ManipulationMathDynamic Programming
Description
Given a non-negative integer n, return the sum of the number of 1-bits in the binary representation of every integer from 1 to n inclusive.
Examples
Input:
n = 4Output:
5Explanation:
popcount(1..4) = 1+1+2+1 = 5.
Input:
n = 1Output:
1Explanation:
Only the integer 1 contributes 1 set bit.
Input:
n = 7Output:
12Explanation:
1+1+2+1+2+2+3 = 12.
Constraints
- •
0 ≤ n ≤ 10⁴ - •
Return a single integer.