C# Bitcount Examples

Get bit counts from integers in different ways. Test and implement these algorithms.

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

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 bitcounting 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.

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

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.

C# program that uses iterated bit count 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. 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.

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

For

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

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.

C# program that benchmarks bit counts 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]; } } Output 704 ms Sparse bit count 5198 ms Iterated bit count 199 ms Precomputed bit count

Notes, lookup tables. Lookup tables allow you to encode control structures in memory. We can create more efficient control flow at run time for a program.

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.

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.Binary Representation

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.BitArray

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.Shift And

A summary. We counted some bits. These methods work identically to C++ or C, but some overhead of the .NET Framework might reduce their performance.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# Bitcount Examples

Related Links:

.Net

Java

Related Links