Counting Bits

[SSJ2Joseph]

Now I'm faced with the challenge of couting the number of 1's in a 32-bit word. I can only use the ! ~ & ^ | + << >> operators. I can't use any control statements. This one is really tough. Anyone got any ideas?

 

[xwb]

Is recursion allowed?

 

[jamisar]

xwb: SSJ2Joseph implicit said NO.
SSJ2Joseph: is this a test||joke ?? ------------ jamisar
Einfachheit ist das Resultat der Reife. (Friedrich Schiller)
Simplicity is the fruit of maturity.

 

[SSJ2Joseph]

Recursion is not allowed.

 

[rotovegasBoy]

no control? my solution would be something like
[tt]
unsigned int foo = ???;
int bits = 0;

bits = (foo & 0x00000001) + ((foo & 0x00000002) >> 1) +
((foo & 0x00000004) >> 2) + ((foo & 0x00000008) >> 3) +
((foo & 0x00000010) >> 4) + ((foo & 0x00000020) >> 5) +
...

printf(&quot;There are %d 1's in %d&quot;, bits, foo);
[/tt]
The lack of control makes things ugly anybody got anything better?



&quot;There are no stupid questions, just lots of inquisitive idiots&quot; - anon

 

[Zyrenthian]

int count = 0;
for(int i = 0;i<sizeof(value)*8;i++)
{
if(value & 1<<i)
{
count++;
}
}

Matt

 

[jamisar]

Zyrenthian: did you already considere to buy optical equipment ??

rotovegasBoy: can you spend few words about you are doing ?

thanks

------------ jamisar
Einfachheit ist das Resultat der Reife. (Friedrich Schiller)
Simplicity is the fruit of maturity.

 

[Zyrenthian]

Basically, that is the gist of figuring out how many bits that are set to one. The other approach, if you cant loop would be to make a struct using bit fields or write the loop out line by line.

Example of bit fields. Please note that this MAY be in reverse order depending on Endianism.

struct binStruct
{
unsigned bit0: 1;
unsigned bit1: 1;
....
unsigned bit31: 1;
}

binStruct s;

(int)s = value;

add up all the bits i.e.

int totalOnes = s.bit0+s.bit1+...+s.bit31;

The last approach i can think of would use the modulus operator and right shifting.

count += value%2 + (value>>1)%2... + (value>>31)%2

but I did not see that as an option above.

Matt

 

[rotovegasBoy]

My code works by masking a particular bit and then shifting it so it has a value of 1 or 0. for example 16 is 10000 in binary so we mask this with 0x10(16) then shift this to the left 4 bits so 16 becomes 1. this works for any number with that bit set. with control statements my code becomes
[tt]
unsigned int foo;
int mask = 0x00000001;
int bit;
int bitcount = 0;
for(bit = 0; bit < 32; bit++)
{
bitcount += foo & mask >> bit;
mask = mask * 2;
}
[/tt] &quot;There are no stupid questions, just lots of inquisitive idiots&quot; - anon

 

[vgersh99]

FYI - something to 'chew' on

http://www-db.stanford.edu/~manku/bitcount.html

vlad
+---------------------------+
|#include<disclaimer.h> |
+---------------------------+