C# Bitcount Algorithms

Bitcounts. Many algorithms count bits.

Bit counting is useful when using compact data structures in memory with bits, or completing computer science homework. There are many fascinating ways of tabulating the number of bits set in integers.

Sparse. First we see the sparse bitcounting algorithm. This is a simple and fast algorithm that walks through all the bits that are set to one. It is static. It does not rely on saving state.

Tip: It always has accurate results, but it performs the fastest when most bits are set to zero.

C# program that counts bits with sparse method

using System;

class Program
{
    static void Main()
    {
	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;
    }
}

Output

0
1
31
1

The effects of the binary operators are not part of this article, but they set, remove and shift bits. Bitwise operators cannot be used in place of boolean operators, and the reverse is also true.

Iterated. Here we see the iterated bitcount algorithm. This bitcount is slow, simple 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.

C# program that uses iterated bitcount

using System;

class Program
{
    static void Main()
    {
	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;
    }
}

Output

0
1
31
1

Precomputed. This program demonstrates the use of a precomputed bitcount lookup table. The InitializeBitcounts method uses a logical method to precompute the bits in the table based on how the binary representation changes.

Note: You can instead use another bit counting mechanism to initialize each element in the table.

C# program that uses precomputed bit counts

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

Output

0
1
31
1

This program uses a lookup table of two 16-bit ranges to compute the bitcount for 32-bit integers. Each of the 16-bit integers is equal to the bitcount of its index value. InitializeBitcounts populates each index with its bitcount.

And: Because bits in number representations use a pattern, the program uses an efficient loop mechanism to initialize them.

For

Contribution: The bitcount initialization function shown here was contributed. Topher Cooper provided this algorithm.

Note: The previous method of using another bit computation on each element in the lookup table was almost ten times slower in my tests.

Next, lookup tables allow you to actually encode control structures in read/write memory. By doing this, you can create more efficient control flow at run time for your application.

Info: The book Code Complete by Steve McConnell offers an overview of using lookup tables to enhance performance for many computations.

Performance. Here, we discuss the performance of these bitcount methods. The iterated bitcount is normally slower than the sparse bitcount. For runtime speed, it is best to use the precomputed bitcount.

However: Precomputed bitcounts have a startup penalty for filling the array. This must be considered.

Out of interest, I performed a simple test of 100,000,000 random numbers having their bits counted with the three methods. My results are easy to interpret. Precomputed bitcounts are fastest, followed by sparse bitcounts.

Benchmark results for bitcount algorithms

Sparse bitcount:       2792 ms
Iterated bitcount:    12855 ms
Precomputed bitcount:  1248 ms [fastest]

Visualize bits. You can visualize the bits set in an integer by using my binary representation method. That method will print out ones and zeros for bits set in numeric types. It uses an approach similar to the iterated bitcount here.

Binary Representation for Integer

BitArray. The .NET Framework provides an object-oriented way of counting bits, displaying bits, and storing bits. The class BitArray is an encapsulation of these methods. For performance, it might suffer over custom methods such as those above.

BitArray Collection

Operators. You may be unfamiliar with the exact usage of the bitwise operators used in the code. They perform unary and shift operations on numbers. Detailed descriptions of these operators are available on this site.

Shift OperatorsAnd Bitwise Operator

Edsger Dijkstra. In the famous lecture titled The Humble Programmer, Edsger Dijkstra noted how programming and computer science is complex. It is the only activity in which humans must deal with numbers ranging nine orders of magnitude.

This suggests the complexity of numerical computations in computer programming. And bit counting allows you to actually store values inside individual bits. You are dealing with individual bits in an environment of billions of bits.

Summary. We saw different ways of counting bits in the C# programming language. These methods work identically to C++ or C, but some overhead of the .NET Framework might reduce their performance and size requirements.

Note: If you decide to use the high-performance precomputed approach, use another bitcounting method for initializing the lookup tables.

Related Links