Dot Net Perls

Problem

Find bitcounts quickly. Bitcounting is often used for low-level algorithms, but it has its place in higher-level algorithms as well. Bit counting enables us to use more compact data structures because we can compact our information into bits. We want to compare and examine three different C# methods for finding bitcounts.

C# Solution

Bit-counting is interesting, but there isn't much innovation going on in the field of counting bits. I think MIT hackers and assembly programmers from several decades ago conquered this problem. Let's start looking at some different algorithms.

Sparse bitcount algorithm

The first bitcount method I want to show here is called the sparse bitcount method and it works very well. It walks through all the bits that are set to 1, which is simple and fast. This method is a static one because it doesn't rely on the state of the class it is stored in.

/// <summary>
/// Finds the number of bits in the parameter.
/// </summary>
static private byte SparseBitcount(int testThis)
{  
    int count = 0;
    while (testThis != 0)
    {
        count++;
        testThis &= (testThis - 1);
    }
    return (byte)count;
}

Iterated bitcount algorithm

The next bitcount I want to show is the iterated bitcount method. This bitcount is slow, but works reliably and is simple. If your requirements are simple, it is sometimes a good choice. This version is also a static function because it doesn't rely on state in the class you put it in.

/// <summary>
/// Finds the number of bits in the parameter.
/// </summary>
static private byte IteratedBitcount(int testThis)
{
    int test = testThis;
    int count = 0;

    while (test != 0)
    {
        if ((test & 1) == 1)
        {
            count++;
        }
        test >>= 1;
    }
    return (byte)count;
}

Precomputed bitcount algorithm

Finally, I want to show the fastest bit counting algorithm I know--the precomputed bitcount method, which uses two 16-bit arrays together. What it does is store all bitcounts for 16-bit integers, and then when you want to find the bitcount of any number, it looks up both parts independently.

/// <summary>
/// Stores 65 thousand bytes, which each hold the number of bits in the
/// index used to access them.
/// </summary>
static byte[] _bitcounts = new byte[65536];

/// <summary>
/// Generate the bit count value array.
/// </summary>
static private void InitializeBitcounts()
{
    for (int i = 0; i < 65536; i++)
    {
        _bitcounts[i] = SparseBitcount(i);
    }
}

/// <summary>
/// Find the number of bits in the parameter integer. This is written like this
/// because it is often the faster technique to count bits. These different
/// techniques have been tested a lot, at least in C.
/// </summary>
static private int Bitcount(int testThis)
{
    return _bitcounts[testThis & 65535] + _bitcounts[(testThis >> 16) & 65535];
}

How do the methods perform?

The iterated bitcount is almost always slower than the sparse bitcount. For the best runtime speed, though, use the precomputed bitcount. There is a startup time penalty with precomputed bitcounts, but it is in the ones of milliseconds. You will need to combine one of the iterated or sparse bitcounts with the precomputed bitcounts.

Conclusion

Bitcounting is not a popular topic in C#, but I am very happy with the results of these functions. They work identically to C++ or C, although are slower overall. Use bitcounting to optimize and compact data structures. Look at this Stanford University page for more information about the methods in C.

Downloads

Get all the bitcounting code above in a much easier to see package at my bitcount source code page. It is easier to scan and copy there.

Ads by The Lounge