Construction an logical expression which will count bits in a byte.

Question

When interviewing new candidates, we usually ask them to write a piece of C code to count the number of bits with value 1 in a given byte variable (e.g. the byte 3 has two 1-bits). I know all the common answers, such as right shifting eight times, or indexing constant table of 256 precomputed results.

But, is there a smarter way without using the precomputed table? What is the shortest combination of byte operations (AND, OR, XOR, +, -, binary negation, left and right shift) which computes the number of 1-bits?

Answer 1

There are at least two faster solutions, with different performance characteristics:

1. Subtract one and AND the new and old values. Repeat until zero. Count the number of iterations. Complexity: O(B), where B is the number of one-bits.

   int bits(unsigned n)
   {
       for (int i = 0; n; ++i)
       {
           n &= n - 1;
       }
       return i;
   }
   

2. Add pairs of bits then groups of four, then groups of eight, till you reach the word size. There's a trick that lets you add all groups at each level in a single pass. Complexity: O(log(N)), where N is the total number of bits.

   int bits(uint32 n)
   {
       n = (n & 0x55555555) + ((n >>  1) & 0x55555555);
       n = (n & 0x33333333) + ((n >>  2) & 0x33333333);
       n = (n & 0x0f0f0f0f) + ((n >>  4) & 0x0f0f0f0f);
       n = (n & 0x00ff00ff) + ((n >>  8) & 0x00ff00ff);
       n = (n & 0x0000ffff) + (n >> 16);
       return n;
   }
   

   This version is a bit naive. If you think about it a bit, you can avoid some of the operations.

Answer 2

Here is a list of ways Bit twiddling hacks

Answer 3

Java does it this way (using 32-bit integers) (14 calculations)

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

For 16-bit integers (short), the method can be rewritten to :

private static int bitCount(int i) {
   // HD, Figure 5-2
   i = i - ((i >>> 1) & 0x5555);
   i = (i & 0x3333) + ((i >>> 2) & 0x3333);
   i = (i + (i >>> 4)) & 0x0f0f;
   i = i + (i >>> 4);
   i = i + (i >>> 8);
   return i & 0x3f;
}

For 8-bit integers (byte), it's a bit more complicated, but the general idea is there.

You can check out this link for more info on fast bit counting functions : http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

The fastest/easiest way for any integer, which is O(0) for the best case and O(n) for the worst case (where n is the number of bits in the value) is

static private int bitcount(int n)  {
   int count = 0 ;
   while (n != 0)  {
      count++ ;
      n &= (n - 1) ;
   }
   return count ;
}