#include <stdio.h>

/**
 * Exercise 2-9.  In a two's complement number system, x &= (x-1) 
 * deletes the rightmost 1-bit in x.  Explain why.  Use this 
 * observation to write a faster version of bitcount.
 */

void displaybits(unsigned,int);
int bitcount(unsigned);
int bitcount_fast(unsigned);

void displaybits(unsigned x, int numbits)
{
   int i;
   for(i=numbits-1; i>=0; i--)
      printf("%d",(x&(1<<i))>0 ? 1 : 0);
   printf("\n");
}

int bitcount(unsigned x)
{
   int b;

   for(b=0; x!=0; x >>= 1)
      if(x & 01) 
         b++;

   return b;
}

int bitcount_fast(unsigned x)
{
   int b = 0;
   for(;x!=0;x&=(x-1)) b++;
   return b;
}

int main(void)
{
   unsigned x = 128482;
   displaybits(x,32);

   int bcnum = bitcount(x);
   int fastbcnum = bitcount_fast(x);

   if(bcnum != fastbcnum)
   {
      printf("Calculation Error!\n");
      exit(-1);
   }

   printf("Number of 1-bits: %d\n", fastbcnum);
   return 0;
}