# finding the number of SET bits in one line of code

## 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 ^_^)

##### Share on other sites
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 on other sites
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 on other sites
std::bitset<32>(val).count();

Because reinventing the wheel is bad.

##### Share on other sites
oh. geez. never mind i get it.

##### Share on other sites
int countBits(int num) { return num ? countBits(num>>1) + (num&1) : 0; }

Does that count? ;)

##### Share on other sites
Quote:
 Original post by Premandrakeint 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 on other sites
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 on other sites
Quote:
 Original post by Frunytemplate \ 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 on other sites
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 on other sites
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 on other sites
Quote:
 Original post by Anonymous PosterIndeed, 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 on other sites
Quote:
 Original post by Evil SteveThe 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 on other sites
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

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628349
• Total Posts
2982210

• 10
• 9
• 24
• 11
• 9