Write a C# Program Different Bitcount Algorithm Function

Write a function to count a total number of set bits in a 32 bit Integer?

Bit counting is useful when using compact data structures in memory with bits. Here, 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.

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:

0
1
31
1

Press any key to continue...

Iterated bitcount algorithm:

This bit count is slow,simple and reliable.

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:

0
1
31
1

Press any key to continue...

Pre computed 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.

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:

0
1
31
1

Press any key to continue...