How BitArray Manages Compact Bit Storage in C

In .NET, the System.Collections.BitArray class provides a compact way to store and manipulate large sequences of boolean values without wasting memory. While a standard boolean array allocates one byte per value, BitArray packs individual bits into larger integer primitives, reducing memory usage by roughly 87.5 percent. This article explains the internal mechanics of BitArray, detailing how it utilizes integer arrays, bit-shifting arithmetic, and bitwise masks to achieve optimal density and high-speed execution.

The Memory Inefficiency of Standard Booleans

In C#, the standard bool data type requires 8 bits (1 byte) of memory. Because the CPU addresses memory at the byte level rather than the bit level, a single bool occupies an entire byte, leaving seven bits unused. Consequently, an array like bool[32] consumes 32 bytes of heap space plus object overhead.

BitArray solves this inefficiency by storing 32 distinct boolean flags within the footprint of a single 32-bit integer, using every individual bit as an independent true/false indicator.

Internal Data Representation

Internally, the BitArray class is backed by an array of 32-bit integers (int[] m_array), alongside an integer counter that tracks the total number of valid bits in the collection.

When a BitArray is instantiated, the runtime calculates the number of 32-bit integers required to accommodate the requested bit count:

\[\text{Array Length} = \frac{\text{Bit Count} + 31}{32}\]

Any division remainder means the final integer element in the array is only partially filled, with unused higher-order bits ignored by the public API.

Bit Mapping and Index Calculation

To read or update a specific bit at position i, BitArray determines both the target integer in the underlying array and the specific bit position within that integer using high-performance bitwise operators:

Integer Index (Word Position): Determines which int in the int[] holds the target bit.
```
int arrayIndex = index >> 5; // Equivalent to index / 32
```
Bit Offset (Bit Position): Determines the exact bit position inside the 32-bit integer (from 0 to 31).
```
int bitOffset = index & 31;  // Equivalent to index % 32
```

Reading Values (`Get` Operation)

To evaluate whether a bit at a given index is true or false, BitArray generates a bitmask by shifting the value 1 left by the calculated offset. It then performs a bitwise AND operation against the target integer:

bool isSet = (m_array[index >> 5] & (1 << (index & 31))) != 0;

If the bit at that position is 1, the result of the AND operation is non-zero, returning true. If the bit is 0, the result evaluates to zero, returning false.

Writing Values (`Set` Operation)

Setting a value requires updating the target bit without altering the remaining 31 bits in the same integer:

Setting to true: Uses a bitwise OR with the bitmask:

m_array[index >> 5] |= (1 << (index & 31));

Setting to false: Inverts the bitmask with a bitwise NOT (~) and performs a bitwise AND:
```
m_array[index >> 5] &= ~(1 << (index & 31));
```

Bulk Bitwise Operations

Beyond compact storage, BitArray improves computational throughput via word-level parallelism. Operations like And, Or, Xor, and Not do not iterate over individual bits. Instead, they apply bitwise operations across entire 32-bit integers at once:

for (int i = 0; i < m_array.Length; i++)
{
    this.m_array[i] &= other.m_array[i];
}

This design allows a modern processor to process 32 boolean operations in a single CPU cycle, offering significant performance gains over traditional loop iterations on bool[] collections.