CSharp_BitCountAlgorithm

Bitcount algorithm in C#

In this article, we will learn:

• Sparsh bitcount algorithm
• Iterated bitcount algorithm
• Precomputed bitcount algorithm

Bit counting is useful when using compact data structures in memory with bits. In this article, we will discuss various ways of counting total no of bits.

Sparsh bitcount 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

namespace ConsoleApplication {     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:

Iterated bitcount algorithm:

This bit count is slow,simple and reliable.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

namespace ConsoleApplication {     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:

Precomputed bitcount algorithm:

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

namespace ConsoleApplication {     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:

SPECIAL THANKS TO CSHARPSTAR