?
Solved

bitCount

Posted on 2003-02-19
4
Medium Priority
?
694 Views
Last Modified: 2008-03-04
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.

Here's one I already did....
**** 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
Comment
Question by:Discomonkey
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
4 Comments
 
LVL 1

Expert Comment

by:TheBeaver
ID: 7984375
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
 
LVL 84

Accepted Solution

by:
ozo earned 200 total points
ID: 7987911
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
 

Expert Comment

by:nagubala
ID: 7988701
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
 
LVL 1

Author Comment

by:Discomonkey
ID: 7990384
Thanks ozo and thebeaver for replying :)
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
Suggested Courses
Course of the Month14 days, 18 hours left to enroll

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question