# 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.

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

Dave

##### Share on other sites
sorry, it's a one line solution.

##### 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 on other sites
One possible solution is a map.

Kuphryn

##### Share on other sites
Indeed, the fastest method is via a look-up table.

##### Share on other sites
Hmmm

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

##### Share on other sites
Quote:
 Original post by discman1028Hmmmint 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 on other sites
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 on other sites
Quote:
Original post by Anonymous Poster
Quote:
 Original post by discman1028Hmmmint 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 ^_^)

• 40
• 12
• 10
• 10
• 9
• ### Forum Statistics

• Total Topics
631371
• Total Posts
2999606
×