Question: You have given a number N. You need to find out total number of set bits from 0 to N.

Example:
Given number is 5. We can represent number 0 to 5 in binary format as below:
000
001
010
011
100
101
Total set bit are 7 (0+1+1+2+1+2)

Answer: Horrified if I need to count number of set bits in every number from 0 to N? Imagine the time taken when N is large…

I was wondering if I could use some pre-generated values in my solution. I gave a thought to this problem and decided to use a recursive approach. This solution needs the pre-computed answers for numbers with all bits set (i.e. 1,3,7,15...). If we assume 4-byte integer, then we need to have a pre-computed array of 32 numbers. That’s it ☺

For 1 Byte numbers, our pre-computed array will be like:

PRE[8] = {0,1,4,12,32,80,192,448};

It means if N is 0,1,3,7,15,31,63,127 then answer will be 0,1,4,12,32,80,192,448 respectively. Notice that in input N, all possible bits are 1s.

now if N is say 6 (110) then how will I compute my answer?

000, 001, 010, 011, 100, 101, 110

We are seeing that max power of 2 less than 6 is 4. And maximum number with all bits set is 3 (4-1).

Now lets take the HSB(1) out form numbers greater than 3, than it will look like

000, 001, 010, 011, 1#00, 1#01, 1#10

Now we can say that
No_of_bits_till (6) = PRE[2] + (6-3) + No_of_bits_till (6 XOR 4)
No_of_bits_till (6) = PRE[2] + (6-3) + No_of_bits_till (2)

Simply if we see for 53 (110101) then this relationship will be
No_of_bits_till (53) = PRE[5] + (53 - 31) + No_of_bits_till (53 XOR 32)

In this manner we have final recursive relation as
No_of_bits_till (N) = PRE[x] + (N-(2^x -1)) + No_of_bits_till (N XOR 2^x)
Where x is max possible power of 2 such that 2^x < N

Code:

```#include<iostream>using namespace std;int PRE[33] = {0,1,4,12,32,80,192,448,1024,2304,5120,11264};int maxpowof2(int n){    int cnt=0;    while(n)    {        n=n>>1;        cnt++;    }    return 1<<(cnt-1);}int noof1s(int n){    if (n == 0)        return 0;    int mx_pow_2 = maxpowof2(n);    int cnt = 0;    while (1<<cnt != mx_pow_2)        cnt++;    return (PRE[cnt] + (n-mx_pow_2+1) + noof1s(n^mx_pow_2));}
```

PS: The beautiful part is that you can generate PRE using this program only. I started with 4 predefined values and generated that using this program only.