C# Bit Counting Algorithms

You want to compute the number of bits set to one in an integer. This is useful when using compact data structures in memory with bits, or completing computer science homework assignments. There are many fascinating ways of tabulating the number bits set in integers, but here we look at the simpler methods, using the C# programming language.

=== Benchmark results for C# bitcount algorithms ===

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

Sparse bitcount algorithm

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 because it doesn't rely on saving state. It always has accurate results, but it performs the fastest when most bits are set to zero.

=== Program that counts bits with sparse method (C#) ===

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 of the program ===

0
1
31
1

Note on bitwise operators. The effects of the binary operators are out of the scope 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 bitcount algorithm

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.

=== Program that uses iterated bitcount (C#) ===

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 of program ===

0
1
31
1

Precomputed bitcount algorithm

Here we note the precomputed bitcount algorithm, which is a way to store bitcount integers in an array and then access the array in lookup method. This is one of the fastest approaches—when you don't count its startup penalty. This version stores all bitcounts for 16-bit integers. Then when you want to find the bitcount of a 32-bit number, it looks up both parts separately. The precomputed bitcount algorithm is described more completely in a separate article.

(See Precomputed Bitcount.)

Performance

In this section, we discuss the performance of these bitcount methods. The iterated bitcount is normally slower than the sparse bitcount. For runtime speed, use the precomputed bitcount. However, precomputed bitcounts have a startup penalty for filling the array.

Benchmarking the bitcount methods. 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. See figures above.

Visualizing bits

You can see the bits set in an integer by using my binary representation method. That method will print out 1's and 0's for bits set in numeric types. It uses an approach similar to the iterated bitcount here.

(See Binary Representation for Integer.)

Using BitArray

The framework provides an object-oriented way of counting bits, displaying bits, and storing bits compactly. The class BitArray is an encapsulation of these methods, and is considerably easier to use. However, for performance, it might suffer over custom methods such as those above.

(See BitArray Collection Use.)

Operators

You may be unfamiliar with the exact usage of the bitwise operators used in this article. They perform unary and shift operations on numbers. Microsoft provides a cheat sheet of all the operators in the C# language.

(Visit msdn.microsoft.com.)

Summary

Here 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 runtime might reduce their performance and size requirements. If you decide to use the high-performance precomputed approach, use another bitcounting method for initializing the lookup tables.

(Do not copy this page.)