Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Construction an logical expression which will count bits in a byte

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?

like image 547
danatel Avatar asked May 24 '10 10:05

danatel


2 Answers

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.

like image 104
Marcelo Cantos Avatar answered Sep 20 '22 10:09

Marcelo Cantos


Here is a list of ways Bit twiddling hacks

like image 43
Naveen Avatar answered Sep 20 '22 10:09

Naveen