Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n.
Example:
Input: n = 3
Output: 4
The way to solve these sorts of problems is to write out the first few values, and look for a pattern
Number binary # bits set F(n) 1 0001 1 1 2 0010 1 2 3 0011 2 4 4 0100 1 5 5 0101 2 7 6 0110 2 9 7 0111 3 12 8 1000 1 13 9 1001 2 15 10 1010 2 17 11 1011 3 20 12 1100 2 22 13 1101 3 25 14 1110 3 28 15 1111 4 32
Binary-representations of the first 8 and the last 8 numbers are exactly the same, except the first 8 have a 0 in the MSB (most significant bit), while the last 8 have a 1. If the input number is of the form 2^b -1 e.g., 1, 3, 7, 15.. etc, the number of set bits is b * 2^(b-1). This is because 2^(b-1) are set and 2^(b-1) are unset for x ∈ (0, b-1 ). In the above example for b =4, 8 bit are set for b =3,2,1. So total set bit is (number of set bit in one column) x (number of column) i.e. b * 2^(b-1). This can also be solved using Permutation.
If n = 2^b, then note in the table above that for n-1, the first bit is set exactly n/2 times, the second bit is set exactly n/2 times, the third bit… all the way to the b’th bit. Thus,
F(n) = b*2^(b-1) + F(n-2^b) + (n-2^b+1)
Thus, for example to calculate F(12), we can just take F(7) and add to it the number of set bits in 8, 9, 10, 11 and 12. But that’s the same as the number of set-bits in 0, 1, 2, 3, and 4 (ie. F(4)), plus one more for each number!