Jump to content
  • Advertisement
Sign in to follow this  
GekkoCube

finding the number of SET bits in one line of code

This topic is 4477 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement
Well a bloated solution would be to have a sequence of if statements that test each bit. Would that suffice?

Dave

Share this post


Link to post
Share on other sites
This page lists some ways to do it. I don't believe you can do it in a single line (well, single statement at least; obviously you can always put a bunch of them on a single line...).

Share this post


Link to post
Share on other sites
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
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
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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!