Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 723

# bitCount

Hey experts!  I hope you are prepared for an onslaught of questions I have for you.

I'm doing bit level manipulations homework in C.  I am trying to basic manipulations using a limited amount of operations.  There are restrictions are in place to help confuse me.(haha)  I would orginally have loved to sit down and figure these out, but time is thin and I need a little help.(spent last couple of days finishing a huge project, this one is due at midnight)  The system is real simple, I have skeleton code, I just have to fill in the blanks so to speak.  You can consider these are puzzlers, because that is generally what they are really.  These are straight out of my code

in the comments you can see restrictions, overall goal, etc.

in place of return 2, of course something else is to be put there.

Rating is the difficulty of the problem from 1 to 4, 4 being hard.

So any help will be gladly appreciated... I have no partner for this project and my time is low, so I can only rely on the help of you guys. I will be trying my best to figure these out, I'll still give points even If I get the answer.

**** Start Example****
/*
* bitXor - x^y using only ~ and &
*   Example: bitXor(4, 5) = 1
*   Legal ops: ~ &
*   Max ops: 14
*   Rating: 2
*/
int bitXor(int x, int y) {

int z = ~x & y;
int zz = x & ~y;
int zzz = ~z & ~zz;
zzz = ~zzz;

return zzz;
**** End Example****

Problem:

/*
* bitCount - returns count of number of 1's in word
*   Examples: bitCount(5) = 2, bitCount(7) = 3
*   Legal ops: ! ~ & ^ | + << >>
*   Max ops: 40
*   Rating: 4
*/
int bitCount(int x) {
return 2;
0
Discomonkey
1 Solution

Commented:
int bitCount(int x)
{
int count=0;

while( x )
{
count += (x & 1);
x = x>>1;
}
return count;
}

xor works like this... it only returns 0 where the bit is unchanged ie 00=0 and 11=0. so...

int bitXor(int a, int b)
{
int bits11 = a & b;   // finds 11 = 1
int bits00 = ~a & ~b; // finds 00 = 1

return ~bits11 & ~bits00;  // invert the results and compare
}
0

Commented:
int bitCount(int x){
x -= ((unsigned)x>>1)&0x55555555;
x -= ((x>>2)&0x33333333)*3;
x += (x>>4)&0x0f0f0f0f;
x &= 0x0f0f0f0f;
x += (x>>8);
/*  x &= 0x00ff00ff;*/
x += (x>>16);
return x&0xff;
}
0

Commented:
A very optimized way of counting 1 bits in a number by K&R...
int BitCount(int x)
{
int count = 0;

while(x)
{
x &= (x-1);
count ++;
}
return count;
}

This above code uses the following property.
A number & with (number -1) will always reset the right most bit which is 1. In this way, if the number has 3, 1 bits then the number of times this has to be done is also 3. How elegant?
0

Author Commented:
Thanks ozo and thebeaver for replying :)
0

## Featured Post

Tackle projects and never again get stuck behind a technical roadblock.