10

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?

SilentGhost
  • 307,395
  • 66
  • 306
  • 293
danatel
  • 4,844
  • 11
  • 48
  • 62
  • possible duplicate of [Best algorithm to count the number of set bits in a 32-bit integer?](http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer) – Hans Passant May 24 '10 at 12:03

3 Answers3

4

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.

Marcelo Cantos
  • 181,030
  • 38
  • 327
  • 365
  • 1
    I think that the first one should return i not n. – danatel May 24 '10 at 11:31
  • The first one CANNOT return i because I has fallen out of scope by the time we reach the return. In order to make it correct, you have to declare i before the for-next loop. It took twelve years for someone to spot that? – TDHofstetter Aug 16 '22 at 17:12
3

Here is a list of ways Bit twiddling hacks

Naveen
  • 74,600
  • 47
  • 176
  • 233
0

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 ;
}
Yanick Rochon
  • 51,409
  • 25
  • 133
  • 214
  • On the last one: both theoretically and practically it's still O(1) for the best case. Also interesting to note that if you use typical large integer representations (e.g BigInteger rather than int) then the worst case can often be O(n^2). – mikera May 24 '10 at 11:48