C# - Bitcount Examples - Dot Net Perls

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.

while

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

Info The effects of the binary operators are not part of this article, but they set, remove and shift bits.

Important Bitwise operators cannot be used in place of boolean operators, and the reverse is also true.

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.

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

Tip This populates each index with its bitcount. We use an efficient loop mechanism to initialize the bit counts.

for

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.

Version 1 This version of the code uses the sparse bit count method. Internally each iteration uses a loop.

Version 2 Here we use the iterated bit count method. This version appears to be the slowest by far.

Version 3 The precomputed version uses a lookup table, and this is not counted in the benchmark here.

Result For runtime speed, it is best to use the precomputed bitcount. There is a start up and memory cost here.

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.

Bitwise Representation

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.