sure, lookup table would work just fine.
but im telling you, it's a one liner. and its much more elegant than some of the other suggestions.
im making a vow to find it!
then ill post.
finding the number of SET bits in one line of code
Author
hmmm...never mind.
i think im wrong here.
i think it might've been a lookup table.
the one liner that i was probably thinking about was the way to determine if a number is a power of 2.
so now then...this lookup table, what do the values of this table mean?
i think im wrong here.
i think it might've been a lookup table.
the one liner that i was probably thinking about was the way to determine if a number is a power of 2.
so now then...this lookup table, what do the values of this table mean?
int countBits(int num) { return num ? countBits(num>>1) + (num&1) : 0; }
Does that count? ;)
Does that count? ;)
Quote:Original post by Premandrake
int countBits(int num) { return num ? countBits(num>>1) + (num&1) : 0; }
Does that count? ;)
Turn that into a template metaprogram, and I think we'll have a winner [grin]. Although Washu definately gets honorable mention.
CM
template<unsigned long num> \ struct count_set_bits \ { \ enum { value = (num & 1) + count_set_bits<(num >> 1)>::value }; \ }; \ \ template<> \ struct count_set_bits<0L> \ { \ enum { value = 0 }; \ };The backlashes make it so it's only one line of code, as per GekkoCube's requirements.
Quote:Original post by Frunytemplate<unsigned long num> \ struct count_set_bits \ { \ enum { value = (num & 1) + count_set_bits<(num >> 1)>::value }; \ }; \ \ template<> \ struct count_set_bits<0L> \ { \ enum { value = 0 }; \ };
The backlashes make it so it's only one line of code, as per GekkoCube's requirements.
Yay!
CM
Or this one:
int countBits(int num) { return num ? countBits(num & (num - 1)) + 1 : 0; }
Which if optimized for character count is pretty darn short:
int c(int x){return x?c(x&x-1)+1:0;}
So, here is a new challenge, can anyone come up with a method that uses less characters?
int countBits(int num) { return num ? countBits(num & (num - 1)) + 1 : 0; }
Which if optimized for character count is pretty darn short:
int c(int x){return x?c(x&x-1)+1:0;}
So, here is a new challenge, can anyone come up with a method that uses less characters?
Here's the 32-bit version:
At least I think that should work.
MSN
x= (x & 0x55555555) + ((x & 0xAAAAAAAA) >> 1);x= (x & 0x33333333) + ((x & 0xCCCCCCCC) >> 2);x= (x & 0x0F0F0F0F) + ((x & 0xF0F0F0F0) >> 4);x= (x & 0x00FF00FF) + ((x & 0xFF00FF00) >> 8);x= (x & 0x0000FFFF) + ((x & 0xFFFF0000) >> 16);At least I think that should work.
MSN
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
