Fastest algorithm to find the number of bits set in a number?

chandan1008 · #1 (**permalink**) 02-11-2007

Hi, what is the fastest algorithm to find the number of bits set in a number?

chandan1008 · #2 (**permalink**) 02-15-2007

for(count=0;number;count++)
number&=(number-1);

can anyone write a better logic for this?

sandeep6883 · #3 (**permalink**) 06-29-2007

For a number 'n'

c=0;

while(n)
{
c=c + (n&1);
n=n>>1;
}

This is the best algorithm as for a number 'n' the time taken is O(log n).

jurgenthor · #4 (**permalink**) 08-27-2008

Create a lookup table - O(1).

deepasree · #5 (**permalink**) 08-27-2008

hi friend..

just refer the link

Bit Count « Technical Interview Questions

Thanks
Deepasree

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

The Following User Says Thank You to chandan1008 For This Useful Post:
mounesh4k