## A Bit Matrix in C#

The other day I was testing very large graphs. I needed a data structure to store information about which nodes in the graph are connected to each other. For example if a graph had four nodes and node 0 was connected to nodes 1 and 3 I could use a 4 by 4 matrix of booleans where the entries in the first row are false (node 0 is not connected to itself), true (node 0 is connected to node 1), false, and true. See image below. But using booleans uses a lot of space. If a boolean is 32 bits then the matrix for a very large graph could be too large to fit in memory. So I wanted a matrix of bits which would allow me to store 32 true or false values at a time. In the old days with C++ I’d have had to write a lot of bit manipulation code with shifting and masks. I’ve done this before and it’s not fun. But C# has a BitArray class that stores an array of booleans as bits which made creating a BitMatrix class very easy. Calling the class looks like:

BitMatrix matrix = new BitMatrix(4); // create a 4×4 matrix
matrix.SetValue(0, 1, true); // [0,1] = true
. . .
bool b = matrix.GetValue(0, 1); // fetch value at [0, 1]
Console.WriteLine(b.ToString()); // display as 0s and 1s
. . .

Here’s my BitMatrix class:

class BitMatrix
{
public BitArray[] data; // an array of arrays
public int dim; // dimension

public BitMatrix(int n)
{
this.data = new BitArray[n];
for (int i = 0; i < data.Length; ++i)
{
this.data[i] = new BitArray(n);
}
this.dim = n;
}
public bool GetValue(int row, int col)
{
return data[row][col];
}
public void SetValue(int row, int col, bool value)
{
data[row][col] = value;
}
public override string ToString()
{
string s = “”;
for (int i = 0; i < data.Length; ++i)
{
for (int j = 0; j < data[i].Length; ++j)
{
if (data[i][j] == true) s += “1 “; else s += “0 “;
}
s += Environment.NewLine;
}
return s;
}

} // class BitMatrix