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.
Anonymoussetbits(n) = setbits(n/2) + (n & 0x1);

setbits(0) = 0

setbits(1) = 1;

Yogeshit can be done more straightforwardly as -

n & n-1 clear the least significant bit in n.

s(n) = s(n & n-1) + 1 , n > 0

we can use dynamic programming to do the memorization.

Akash@Yogesh: We can do that for a number but as I have written in the very beginning of the answer "what if I need to count number of set bits in every number from 0 to N? Imagine the time taken when N is large."

Think in terms of complexity and time taken.

UnknownYogeshHi Akash,

thanks for replying. But I still see with soln i posted above, complexity is O(n) and not exponential.

S[0....N] can be populated. For getting the final solution which is Sigma(S(i)), 0<=i<=N, we keep track of a SUM variable while populating the table. Correct me If I am wrong, and you see prob in this.

your solution is doing same thing more or less, but lil complicated plus you are using a sub function call to get power_of_two.

Venkata Ramana SanakaI have provided meta program to generate the table in the following post,

http://www.geeksforgeeks.org/archives/11263

Instead of random numbers, we can make use of numbers from 0 to N. Isn't it?

Sumitfor (int n = 0; n < 16; n++) {

int base = 2;

int count = 0;

while (n >= (base >> 1)) {

int cycles = (n + 1) / base;

int rest = (n + 1) % base;

rest = Math.max(0, rest - (base >> 1));

count += (cycles * (base >> 1)) + rest;

base = base << 1;

}

System.out.println(n + " " + count);

}

Enjoy!

(Basically calculating how many times a complete loop is made for a bit location and the residual number of set bit if a partial cycle)