finding the number of SET bits in one line of code
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?
Well a bloated solution would be to have a sequence of if statements that test each bit. Would that suffice?
Dave
Dave
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...).
Hmmm
int count = (int)( (byte&1)+(byte&2)+(byte&4)+(byte&8)+(byte&16)+(byte&32)+(byte&64)+(byte&128) )
int count = (int)( (byte&1)+(byte&2)+(byte&4)+(byte&8)+(byte&16)+(byte&32)+(byte&64)+(byte&128) )
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 ....
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...
Quote:Original post by Anonymous PosterQuote: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 ^_^)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement