Posts
Sol 1:
Simple Iterative solution.(Very slow)
int countbits (unsigned int number) {
int count = 0;
while (number) {
count += number & 0x1u;
number >>= 1;
}
return count;
}
Sol 2:
Faster Solution for 32 bit machines.
compute 16bits then add then to return full number of ones in 32 bit number.
static char ones_in_16bit_num [0x1u << 16] ;
int countbits (unsigned int number)
{
return ones_in_16bit_num [number & 0xffffu] + ones_in_16bit_num [(number >> 16) & 0xffffu] ;
}
Categories
FollowersBlog Archive
Jobs
Find more freelance jobs
|
Sunday, March 28, 2010
Subscribe to:
Post Comments (Atom)
|
Popular Posts
|
... however both solutions have drawbacks (speed and memory). interesting thing is, that people asking this question are never prepared to hear the correct answer and often don't even understand it (what a shame :( ), that is:
ReplyDeleteval = ((val & 0xaaaaaaaa) >> 1) + (val & 0x55555555);
val = ((val & 0xcccccccc) >> 2) + (val & 0x33333333);
val = ((val & 0xf0f0f0f0) >> 4) + (val & 0xf0f0f0f);
val = ((val & 0xff00ff00) >> 8) + (val & 0xff00ff);
val = ((val & 0xffff0000) >> 16) + (val & 0xffff);
// and to extend it to 64 bits (apart from expanding above masks):
val = ((val & 0xffffffff00000000ull) >> 32) + (val & 0xffffffffull);