# Thread: bitwise operations in C

1. ## bitwise operations in C

I'm trying to write a program called bitCount -
It returns the of number of 1's in word (32 bit word size)
Examples: bitCount(5) = 2, bitCount(7) = 3
Legal ops: ! ~ & ^ | + << >>
Max ops: 40

does anyone have any hints on this, it doesn't really make sense to me.

2. Here's one way that tests the low order bit and then shifts all bits right until the value is 0:
Code:
```int bit_count1 ( unsigned int val )
{
int count = 0;

while ( val != 0 ) {
if ( val & 1 )
count++;

val >>= 1;
}

return count;
}```
And another method that loops until the value is 0, but instead of shifting it clears the lowest order bit set to 1:
Code:
```int bit_count2 ( unsigned int val )
{
int count = 0;

while ( val != 0 ) {
count++;

val &= val - 1;
}

return count;
}```
-Prelude

3. what's really tough is that I need to do this without using any operations like "if" or "while" or "for"

just bitwise operators

4. No problem, but it's not nearly as clear as the previous functions and it assumes a 32 bit value:
Code:
```int bit_count3 ( unsigned int val )
{
val = ( val & 0x55555555 ) + ( ( val >> 1 ) & 0x55555555 );
val = ( val & 0x33333333 ) + ( ( val >> 2 ) & 0x33333333 );
val = ( val & 0x0F0F0F0F ) + ( ( val >> 4 ) & 0x0F0F0F0F );
val = ( val & 0x00FF00FF ) + ( ( val >> 8 ) & 0x00FF00FF );
val = ( val & 0x0000FFFF ) + ( ( val >> 16 ) & 0x0000FFFF );

return (int)val;
}```
-Prelude

5. Code:
```int BitCount(unsigned int x)
{
x = (x >> 1 & 0x55555555) + (x & 0x55555555);
x = (x >> 2 & 0x33333333) + (x & 0x33333333);
x = (x >> 4 & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
x = (x >> 8 & 0x00ff00ff) + (x & 0x00ff00ff);
return(x >> 16) + (x & 0x0000ffff);
}```
EDIT - dammit, you beat me this time

6. thanks, I wasn't really expected some one to just give me the code. I don't completly understand how the masking is working, but I'll have to break it down at it and figure it out.

Popular pages Recent additions