Fastest algorithm to find the number of bits set in a number?
Hi, what is the fastest algorithm to find the number of bits set in a number?
Re: Fastest algorithm to find the number of bits set in a number?
for(count=0;number;count++)
number&=(number-1);
can anyone write a better logic for this?
Re: Fastest algorithm to find the number of bits set in a number?
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).
Re: Fastest algorithm to find the number of bits set in a number?
Create a lookup table - O(1).
Re: Fastest algorithm to find the number of bits set in a number?
hi friend..
just refer the link
[url=http://tekpool.wordpress.com/category/bit-count/]Bit Count « Technical Interview Questions[/url]
Thanks
Deepasree