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?

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

Marcelo Cantos · Accepted Answer · 2010-05-24T12:12:10.670

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

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;
}
```
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.

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

score 3 · Answer 2 · answered May 24 '10 at 11:03

3

Here is a list of ways Bit twiddling hacks

answered May 24 '10 at 11:03

Naveen

74,600
47
176
233

Yanick Rochon · Answer 3 · 2010-05-24T11:43:46.273

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 ;
}

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

Construction an logical expression which will count bits in a byte

3 Answers3

Linked