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.


Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.