TheDeveloperBlog.com


C# BitArray Collection

BitArray is a compact and easy-to-use object. Found in System.Collections, it offers a clear interface to bitwise operations. It allows you to perform bitwise operations. With it we count and display bits.


Example. First, BitArray has many constructors, including ones that receive int32, int32 arrays, byte arrays and default values. When you pass values to the constructor, integers are copied, but bytes and bools are processed first.

Next: We use the BitArray type. This example initializes a BitArray from a bool array.

C# program that creates new BitArray

using System;
using System.Collections;

class Program
{
    static void Main()
    {
	// Create array of 5 elements and 3 true values.
	bool[] array = new bool[5];
	array[0] = true;
	array[1] = false; // <-- False value is default
	array[2] = true;
	array[3] = false;
	array[4] = true;

	// Create BitArray from the array.
	BitArray bitArray = new BitArray(array);

	// Display all bits.
	foreach (bool bit in bitArray)
	{
	    Console.WriteLine(bit);
	}
    }
}

Output

True
False
True
False
True

The program creates a bool array with true and false values, and then the BitArray constructor converts those into one bit each. This means that instead of one byte for a bool, the values are stored as one bit, in one-eighth the space.

True and False

Set, count. Here we assign bits with the indexer and the Set method, and also Count the BitArray's capacity. The program here also shows how to count bits set to one in a loop. This loop is likely far slower than more optimized bitcounting methods.

Bitcounts
C# program that sets and counts bits

using System;
using System.Collections;

class Program
{
    static void Main()
    {
	// Create BitArray from the array.
	BitArray bitArray = new BitArray(32);

	// Set three bits to 1.
	bitArray[3] = true;     // You can set the bits with the indexer.
	bitArray[5] = true;
	bitArray.Set(10, true); // You can set the bits with Set.

	// Count returns the total of all bits (1s and 0s).
	Console.WriteLine("--- Total bits ---");
	Console.WriteLine(bitArray.Count);

	// You can loop to count set bits.
	Console.WriteLine("--- Total bits set to 1 ---");
	Console.WriteLine(CountBitArray(bitArray));
    }

    /// <summary>
    /// Count set bits in BitArray.
    /// </summary>
    static int CountBitArray(BitArray bitArray)
    {
	int count = 0;
	foreach (bool bit in bitArray)
	{
	    if (bit)
	    {
		count++;
	    }
	}
	return count;
    }
}

Output

--- Total bits ---
32
--- Total bits set to 1 ---
3

The Count on BitArray instances does not return the number of set bits. Instead, it returns the count of all bits of any value. Therefore, you will need to loop over bits individually to count them. You can also use a for-loop.


Display. Here we display all the bits as ones and zeros in a BitArray. This is easier than doing the iteration with bitwise operators. We also use the bitwise And method on BitArray, which shows how to get all the bits that are one in both arrays.

C# program that displays bits and uses And

using System;
using System.Collections;

class Program
{
    static void Main()
    {
	//
	// Initialize BitArray with 4 true bits and 12 false bits.
	//
	BitArray bitArray1 = new BitArray(16);
	bitArray1.Set(0, true);
	bitArray1.Set(1, true);
	bitArray1.Set(4, true);
	bitArray1.Set(5, true);

	//
	// Display the BitArray.
	//
	DisplayBitArray(bitArray1);

	//
	// Initialize BitArray with two set bits.
	//
	BitArray bitArray2 = new BitArray(16);
	bitArray2.Set(0, true);
	bitArray2.Set(7, true);
	DisplayBitArray(bitArray2);

	//
	// And the bits.
	//
	bitArray1.And(bitArray2);
	DisplayBitArray(bitArray1);
    }

    /// <summary>
    /// Display bits as 0s and 1s.
    /// </summary>
    static void DisplayBitArray(BitArray bitArray)
    {
	for (int i = 0; i < bitArray.Count; i++)
	{
	    bool bit = bitArray.Get(i);
	    Console.Write(bit ? 1 : 0);
	}
	Console.WriteLine();
    }
}

Output

1100110000000000
1000000100000000
1000000000000000


Bitwise methods. The BitArray class defines several more useful methods you can call. These methods, including the bitwise operations Not(), Or() and Xor() provide functionality equivalent to the bitwise operators.

Note: You can find more reference on the behavior of these operators on Wikipedia.


Internals. BitArray contains an integer array that stores the bits themselves, and a separate length value. The length member is accessed through the Count property. The Get method returns bit values by using an "AND" and shift on the internal array.

Internal members of BitArray

private int[] m_array;
private int m_length;

Internally, each call to Get will result in the method checking all the parameters. This introduces two extra branches, which may be a burden on certain algorithms that require top performance.

Therefore: The BitArray is unsuitable for performance-sensitive applications that access many separate bits.

Memory allocation of BitArray. I instrumented an application with CLRProfiler, which revealed that each bit in a BitArray is stored as a single bit in memory. Therefore, BitArray uses eight times less memory on large bit collections.

Note: Please see the screenshot at top, which shows allocations for one million bools/bits.


Summary. We saw examples of using the BitArray class in the C# language. This is a powerful wrapper over the complex bitwise operations that connect an array of four-byte integers with single bits.

Thus: This class provides a memory-efficient mechanism for using sets of bits without writing elaborate bit manipulations from scratch.

Bool Array Memory