Sign in to follow this  
GekkoCube

finding the number of SET bits in one line of code

Recommended Posts

GekkoCube    116
here's the deal: without using any loops, determine how many bits in a byte are set. I remember seeing the answer to this a few months ago. Im trying to figure this out again, but i misplaced the reference as well as the solution. i do remember it was pretty darn elegant, and i believe it used some clever bitwise operations. cant remember if it invovled its 2's complement. anyhow, it was pretty neat. anybody like to take a stab at it?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Indeed, the fastest method is via a look-up table.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Quote:
Original post by discman1028
Hmmm

int count = (int)( (byte&1)+(byte&2)+(byte&4)+(byte&8)+(byte&16)+(byte&32)+(byte&64)+(byte&128) )


shouldnt you shift ( >> ) each of those down (except first) so that they would equal 0x01 ????

Hmm I wonder if the resulting code is actually larger (in mem) than a lookup table of bytes (byte used as index and array element containing the count).
The array thingee would certainly be faster ....

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Well, if we're talking about 32-bit integers, this specific look-up table should take up 1024 bytes / 1 kilobyte if it contains 256 elements...

Share this post


Link to post
Share on other sites
discman1028    212
Quote:
Original post by Anonymous Poster
Quote:
Original post by discman1028
Hmmm

int count = (int)( (byte&1)+(byte&2)+(byte&4)+(byte&8)+(byte&16)+(byte&32)+(byte&64)+(byte&128) )


shouldnt you shift ( >> ) each of those down (except first) so that they would equal 0x01 ????


Knew I was missing something! :-0

int count = (int)( (byte&1)+((byte&2)>>1)+((byte&4)>>2)+((byte&8)>>3)+((byte&16)>>4)+((byte&32)>>5)+((byte&64)>>6)+((byte&128)>>7) )

Shifts in hardware are inexpensive, if not free. (The shifts were, ahem, errm, assumed ^_^)

Share this post


Link to post
Share on other sites
GekkoCube    116
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.

Share this post


Link to post
Share on other sites
GekkoCube    116
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?

Share this post


Link to post
Share on other sites
Conner McCloud    1135
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

Share this post


Link to post
Share on other sites
Fruny    1658
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.

Share this post


Link to post
Share on other sites
Conner McCloud    1135
Quote:
Original post by Fruny
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.

Yay!

CM

Share this post


Link to post
Share on other sites
Premandrake    175
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?

Share this post


Link to post
Share on other sites
msn12b    390
Here's the 32-bit version:



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

Share this post


Link to post
Share on other sites
Evil Steve    2017
Quote:
Original post by Anonymous Poster
Indeed, the fastest method is via a look-up table.
The fastest method is that assembly instruction that counts the number of set bits in a 32-bit value. No idea what it's called though...

Share this post


Link to post
Share on other sites
Fruny    1658
Quote:
Original post by Evil Steve
The fastest method is that assembly instruction that counts the number of set bits in a 32-bit value. No idea what it's called though...


You are thinking of BSR which computes the integer log base 2. I don't know of an instruction which counts the number of set bits.

Share this post


Link to post
Share on other sites
Enigma    1410
Based on the 64-bit versions on the page linked to by jpetrie and assuming an 8-bit byte and 32-bit unsigned int:
int countbits(unsigned int v)
{
return (((v * 0x01008040U) | (v >> 3)) & 0x11111111U) % 15;
}

Σnigma

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this