Bitcounts

Many algorithms count bits. Bit counting is useful when using compact data structures in memory with bits. It can enable advanced optimizations.

There are many fascinating ways of tabulating the number of bits set in integers. Here we implement, and benchmark, 3 bit-counting algorithms in the C# language.

Sparse count

First we see the sparse counting algorithm. This algorithm that walks through all the bits that are set to one. It uses a while-loop.

using System;

// Use sparse bitcount.
Console.WriteLine( SparseBitcount(0));
Console.WriteLine( SparseBitcount(1));
Console.WriteLine( SparseBitcount(int.MaxValue));
Console.WriteLine( SparseBitcount(256));

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

Iterated count

This bitcount is slow and reliable. It is also static because it doesn't rely on state. It should only be considered when simplicity is more important than anything else.

using System;

// Use iterated bitcount.
Console.WriteLine( IteratedBitcount(0));
Console.WriteLine( IteratedBitcount(1));
Console.WriteLine( IteratedBitcount(int.MaxValue));
Console.WriteLine( IteratedBitcount(256));

static int IteratedBitcount(int n)
{
    int test = n;
    int count = 0;

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

Precomputed

Here we use a precomputed bit count lookup table. We use a lookup table of two 16-bit ranges to compute the bitcount for 32-bit integers.

using System;

class Program
{
    static void Main()
    {
        // Initialize the lookup table.
        InitializeBitcounts();

        // Get the bitcounts for these values by lookups.
        Console.WriteLine( PrecomputedBitcount(0));
        Console.WriteLine( PrecomputedBitcount(1));
        Console.WriteLine( PrecomputedBitcount(int.MaxValue));
        Console.WriteLine( PrecomputedBitcount(256));
    }

    static int[] _bitcounts; // Lookup table

    static void InitializeBitcounts()
    {
        _bitcounts = new int[65536];
        int position1 = -1;
        int position2 = -1;

        // Loop through all the elements and assign them.
        for (int i = 1; i < 65536; i++, position1++)
        {
            // Adjust the positions we read from.
            if (position1 == position2)
            {
                position1 = 0;
                position2 = i;
            }
            _bitcounts[i] = _bitcounts[position1] + 1;
        }
    }

    static int PrecomputedBitcount(int value)
    {
        // Count bits in each half of the 32-bit input number.
        return _bitcounts[value & 65535] + _bitcounts[(value >> 16) & 65535];
    }
}
0
1
31
1

Benchmark

Here we test the 3 bit counting methods. We run each in a tight loop. Because the performance results are so clear, we do not need to worry about the ordering of the tests.

using System;
using System.Diagnostics;

class Program
{
    static void Main()
    {
        InitializeBitcounts();
        const int m = 100000000;
        Stopwatch s1 = Stopwatch.StartNew();
        // Version 1: use sparse.
        for (int i = 0; i < m; i++)
        {
            SparseBitcount(i);
        }
        s1.Stop();
        Stopwatch s2 = Stopwatch.StartNew();
        // Version 2: use iterated.
        for (int i = 0; i < m; i++)
        {
            IteratedBitcount(i);
        }
        s2.Stop();
        Stopwatch s3 = Stopwatch.StartNew();
        // Version 3: use precomputed.
        for (int i = 0; i < m; i++)
        {
            PrecomputedBitcount(i);
        }
        s3.Stop();
        Console.WriteLine("{0}\n{1}\n{2}", s1.ElapsedMilliseconds, s2.ElapsedMilliseconds, s3.ElapsedMilliseconds);
    }

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

    static int IteratedBitcount(int n)
    {
        int test = n;
        int count = 0;

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

    static int[] _bitcounts;

    static void InitializeBitcounts()
    {
        _bitcounts = new int[65536];
        int position1 = -1;
        int position2 = -1;
        for (int i = 1; i < 65536; i++, position1++)
        {
            if (position1 == position2)
            {
                position1 = 0;
                position2 = i;
            }
            _bitcounts[i] = _bitcounts[position1] + 1;
        }
    }

    static int PrecomputedBitcount(int value)
    {
        return _bitcounts[value & 65535] + _bitcounts[(value >> 16) & 65535];
    }
}
704  ms    Sparse bit count
5198 ms    Iterated bit count
199  ms    Precomputed bit count

Visualize bits

That method will print out ones and zeros for bits set in numeric types. It uses an approach similar to the iterated bitcount here.

using System;

// Display bits of this integer.
int value = 0;
value |= (1 << 4);
value |= (1 << 20);
Console.WriteLine(GetIntBinaryString(value));

static string GetIntBinaryString(int b)
{
    return Convert.ToString(b, 2).PadLeft(32, '0');
}
00000000000100000000000000010000

Some algorithms need fast bit-counting. These methods work identically to C++ or C, but some overhead of the .NET Framework might reduce their performance.