Bit Arrays
If you need to deal with a number of bits, you can use the class BitArray and the struct BitVector32. BitArray is located in the namespace System.Collections, BitVector32 in the namespace System .Collections.Specialized. The most important difference between these two types is that BitArray is resizable, which is useful if you don’t know the number of bits needed in advance, and it can contain a large number of bits. BitVector32 is stack-based and therefore faster. BitVector32 contains only 32 bits, which are stored in an integer.
BitArray
The class BitArray is a reference type that contains an array of ints, where for every 32 bits a new integer is used. Members of this class are explained in the following table.
| BitArray Members | Description |
|---|---|
| Count Length | The get accessor of both Count and Length return the number of bits in the array. With the Length property, you can also define a new size and resize the collection. |
| Item | You can use an indexer to read and write bits in the array. The indexer is of type bool. |
| Get() Set() | Instead of using the indexer, you can also use the Get and Set methods to access the bits in the array. |
| SetAll() | The method SetAll() sets the values of all bits according to the parameter passed to the method. |
| Not() | The method Not() generates the inverse all bits of the array. |
| And() Or() Xor() | With the methods And(), Or and Xor() you can combine two BitArray objects. The And() method does a binary AND, where the result bits are only set if the bits from both input arrays are set. The Or() method does a binary OR, where the result bits are set if one or both of the input arrays are set. The Xor() method is an exclusive OR, where the result is set if only one of the input bits is set. |
Open table as spreadsheet | Tip | In Chapter 6, “Operators and Casts,” you can read about the C# operators for working with bits. |
The helper method DisplayBits() iterates through a BitArray and displays 1 or 0 to the console, depending if the bit is set or not:
static void DisplayBits(BitArray bits) { foreach (bool bit in bits) { Console.Write(bit ? 1 : 0); } } The example to demonstrate the BitArray class creates a bit array with 8 bits, indexed from 0 to 7. The SetAll() method sets all 8 bits to true. Then the Set() method changes bit 1 to false. Instead of the Set method, you can also use an indexer, as shown with index 5 and 7.
BitArray bits1 = new BitArray(8); bits1.SetAll(true); bits1.Set(1, false); bits1[5] = false; bits1[7] = false; Console.Write("initialized: "); DisplayBits(bits1); Console.WriteLine(); This is the displayed result of the initialized bits:
initialized: 10111010
The Not() method generates the inverse of the bits of the BitArray:
DisplayBits(bits1); bits1.Not(); Console.Write(" not "); DisplayBits(bits1); Console.WriteLine(); The result of Not() is all bits inversed. If the bit was true, it is false, and if it was false, it is true:
10111010 not 01000101
Here, a new BitArray is created. With the constructor, the variable bits1 is used to initialize the array, so the new array has the same values. Then the values for bits 0, 1, and 4 are set to different values. Before the Or() method is used, the bit arrays bits1 and bits2 are displayed. The Or() method changes the values of bits1.
BitArray bits2 = new BitArray(bits1); bits2[0] = true; bits2[1] = false; bits2[4] = true; DisplayBits(bits1); Console.Write(" or "); DisplayBits(bits2); Console.Write(" = "); bits1.Or(bits2); DisplayBits(bits1); Console.WriteLine(); With the Or() method, the set bits are taken from both input arrays. In the result, the bit is set if it was set with either the first or the second array:
01000101 or 10001101 = 11001101
Next, the And() method is used to operate on bits2 and bits1:
DisplayBits(bits2); Console.Write(" and "); DisplayBits(bits1); Console.Write(" = "); bits2.And(bits1); DisplayBits(bits2); Console.WriteLine(); The result of the And() method only sets the bits where the bit was set in both input arrays:
10001101 and 11001101 = 10001101
Finally the Xor() method is used for an exclusive OR:
DisplayBits(bits1); Console.Write(" xor "); DisplayBits(bits2); bits1.Xor(bits2); Console.Write(" = "); DisplayBits(bits1); Console.WriteLine(); With the Xor() method, the resultant bits are set only if the bit was set either in the first or the second input, but not both:
11001101 xor 10001101 = 01000000
BitVector32
If you know the number of bits you need in advance, you can use the BitVector32 structure instead of BitArray. BitVector32 is more efficient, as it is a value type and stores the bits on the stack inside an integer. With a single integer you have place for 32 bits. If you need more bits, you can use a multiple BitVector32 values or the BitArray. The BitArray can grow as needed; this is not an option with BitVector32.
The next table shows the members of BitVector that are very different from BitArray:
| BitVector Members | Description |
|---|---|
| Data | The property Data returns the data behind the BitVector32 as integer. |
| Item | The values for the BitVector32 can be set using an indexer. The indexer is overloaded - you can get and set the values using a mask or a section of type BitVector32.Section. |
| CreateMask() | CreateMask() is a static method that you can use to create a mask for accessing specific bits in the BitVector32. |
| CreateSection() | CreateSection() is a static method that you can use to create several sections within the 32 bit. |
The sample code creates a BitVector32 with the default constructor, where all 32 bits are initialized to false. Then masks are created to access the bits inside the bit vector. The first call to CreateMask() creates a mask to access the first bit. After CreateMask() is invoked, bit1 has a value of 1. Invoking CreateMask() once more and passing the first mask as a parameter to CreateMask() returns a mask to access the second bit, which is 2. bit3 then has a value of 4 to access bit number 3. bit4 has a value of 8 to access bit number 4.
Then the masks are used with the indexer to access the bits inside the bit vector and set fields accordingly:
BitVector32 bits1 = new BitVector32(); int bit1 = BitVector32.CreateMask(); int bit2 = BitVector32.CreateMask(bit1); int bit3 = BitVector32.CreateMask(bit2); int bit4 = BitVector32.CreateMask(bit3); int bit5 = BitVector32.CreateMask(bit4); bits1[bit1] = true; bits1[bit2] = false; bits1[bit3] = true; bits1[bit4] = true; bits1[bit5] = true; Console.WriteLine(bits1); The BitVector32 has an overridden ToString() method that not only displays the name of the class but also 1 or 0 if the bits are set or not, respectively:
BitVector32{00000000000000000000000000011101} Instead of creating a mask with the CreateMask() method, you can define the mask yourself; you can also set multiple bits at once. The hexadecimal value abcdef is the same as the binary value 1010 1011 1100 1101 1110 1111. All the bits defined with this value are set:
bits1[0xabcdef] = true; Console.WriteLine(bits1); With the output shown you can verify the bits that are set:
BitVector32{00000000101010111100110111101111} Separating the 32 bits to different sections can be extremely useful. For example, an IPv4 address is defined as a 4-byte number that is stored inside an integer. You can split the integer by defining four sections. With a multicast IP message several 32 bit values are used. One of these 32 bit values is separated in these sections: 16 bits for the number of sources, 8 bit for a querier’s query interval code, 3 bit for a querier’s robustness variable, a 1-bit suppress flag, and 4 bits that are reserved. You can also define your own bit meanings to save memory.
The example simulates receiving the value 0x79abcdef and passes this value to the constructor of BitVector32, so that the bits are set accordingly.
int received = 0x79abcdef; BitVector32 bits2 = new BitVector32(received); Console.WriteLine(bits2); The bits are shown on the console as initialized:
BitVector32{01111001101010111100110111101111} Then six sections are created. The first section requires 12 bits, as defined by the hexadecimal value 0xfff (12 bits are set); section B requires 8 bits; section C, 4 bits; section D and E, 3 bits; and section F, 2 bits. The first call to CreateSection() just receives 0xfff to allocate the first 12 bits. With the second call to CreateSection(), the first section is passed as an argument, so that the next section continues where the first section ended. CreateSection() returns a value of type BitVector32.Section that contains the offset and the mask for the section.
// sections: FF EEE DDD CCCC BBBBBBBB AAAAAAAAAAAA BitVector32.Section sectionA = BitVector32.CreateSection(0xfff); BitVector32.Section sectionB = BitVector32.CreateSection(0xff, sectionA); BitVector32.Section sectionC = BitVector32.CreateSection(0xf, sectionB); BitVector32.Section sectionD = BitVector32.CreateSection(0x7, sectionC); BitVector32.Section sectionE = BitVector32.CreateSection(0x7, sectionD); BitVector32.Section sectionF = BitVector32.CreateSection(0x3, sectionE); Passing a BitVector32.Section to the indexer of the BitVector32 returns an int just mapped to the section of the bit vector. Here, a helper method, IntToBinaryString(), is used to get a string representation of the int number:
Console.WriteLine("Section A: " + IntToBinaryString(bits2[sectionA], true)); Console.WriteLine("Section B: " + IntToBinaryString(bits2[sectionB], true)); Console.WriteLine("Section C: " + IntToBinaryString(bits2[sectionC], true)); Console.WriteLine("Section D: " + IntToBinaryString(bits2[sectionD], true)); Console.WriteLine("Section E: " + IntToBinaryString(bits2[sectionE], true)); Console.WriteLine("Section F: " + IntToBinaryString(bits2[sectionF], true)); IntoToBinaryString receives the bits in an integer and returns a string representation containing 0 and 1. With the implementation, 32 bits of the integer are iterated through. In the iteration, if the bit is set, 1 is appended to the StringBuilder; otherwise, 0 is appended. Within the loop, a bit shift happens to check if the next bit is set.
static string IntToBinaryString(int bits, bool removeTrailingZero) { StringBuilder sb = new StringBuilder(32); for (int i = 0; i < 32; i++) { if ((bits & 0x80000000) != 0) { sb.Append("1"); } else { sb.Append("0"); } bits = bits << 1; } string s = sb.ToString(); if (removeTrailingZero) { return s.TrimStart('0'); } else { return s; } } The result displays the bit representation of sections A to F, which you can now verify with the value that was passed into the bit vector:
Section A: 110111101111 Section B: 10111100 Section C: 1010 Section D: 1 Section E: 111 Section F: 1
