Share the joy
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
Example:
For num = 5 you should return [0,1,1,2,1,2].
Solution. A great solution is from here. It uses the formula: f(x) = f(x / 2) + x % 2
0 1 2 3 4 5 6 7 8
0 1 10 11 110 101 110 111 1000
0 1 1 2 2 2 2 3 1
We know 7 move right 1 bit, then it can reach 3. So we can calculate 7 by 3. The only difference is that we need to know the new bit is 0 or 1.
Check my code on github.