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

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

ShiftAnd**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.

© 2007-2020 Sam Allen. Send bug reports to info@dotnetperls.com.