2/9.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <stdio.h>

/* counts 1-bits in x */
int bitcount(unsigned x) {
  // Explanation: on a two's complement system, x - 1 is performed by 
  // adding the two's complement of 1 (i.e. 111...1) to x. Adding 1 to
  // the rightmost 1-bit results in 0 which when &-ed with x, results in 0.
  int b;

  for (b = 0; x != 0; x &= (x - 1))
    b++;

  return b;
}