Quick Tip: Count The Number of 1 Bits In an Integer Using C

I recently had an intervew where I was asked to write a program to count the number of 1 bits in an integer. The solution I presented is the following:

unsigned int bit_count ( unsigned int i ) {
  unsigned int n = 0;
  while ( i != 0 ) {
    n += i & 1;
    i = i >> 1;
  }
  return n;
}

Download Source: bit_count.c

The solution above is O(n) where n is the number of bits. It is not a very efficient solution since it must do around 64 computations for each 32-bit number but it did the job of demonstrating my skills. When I was walking home from the interview I thought of a better solution using a lookup table:

unsigned int lookup_table[] = { 0, 1, 1, 2 };
unsigned int bit_count_lookup ( unsigned int i ) {
  unsigned int n = 0;
  while ( i != 0 ) {
    n += lookup_table[i & 3];
    i = i >> 2;
  }
  return n;
}

Download Source: bit_count_lookup.c

Although this solution will also be O(n) where n is the number of bits, it will require half of the computations as the first solution. By making the lookup table even bigger, you could reduce the computations further.

Tags: C/C++, Interview Questions, Quick Tip