When should you use BitVector32?

Question

I am working on a project where at a certain point I need to show for one month which days are still available. There is a function that calculates which days are available. My colleagues said: "Oh, we know you should return BitVector32 , which is most effective when working with a list of logical elements." I would use a List<bool> or something like that. A BitVector32 seems to me a bit of a low-level thing when you actually work with bits.

So the question is. Should you use BitVector32 whenever you need a list of logical elements with less than 32 elements, or should you use it only for low-level materials?

Answer 1

The use of the list is easily expanded at other time periods. Say what you want to show right away for two months. Oh, which is more than 32. I need to change the type of return and wherever it was used. Large! And BitVector32 does not even implement IEnumerable<T> .

And unless it provides readability and serviceability at maximum performance. And the overhead of distributing lists is not so great unless you do it a million times per second.

Therefore, I agree with you that you should use BitVector32 only for low-level code.

Answer 2

BitVector32 is a wrapper (or you can call it an abstraction) around C # bit operations. For example, the following two statements return the same result:

• 1 <1
• BitVector32.CreateMask (1)

Let's say there is an integer array containing some repeating numbers. We want to find all the duplicates. Of course, you can simply use the GroupBy function in Linq, but do not pretend that we do not have Linq.

• The first option is a brute force approach, where each element will be compared with each element in this array:

   foreach(int i in list) { foreach(int j in list) { if (i == j) { // print this or store it in the result list } } } 

• Since the brute force approach will result in N square runtimes, which is pretty inefficient, we might consider using a HashSet that will provide constant search time or O (1)

   HashSet<int> hashSet = new HashSet<int>(); foreach(int i in list) { if (hashSet.Contains(i)) { // print the duplicate or add it to the result list } else { hashSet.Add(i); } } 

This approach will result in linear runtime or O (n). However, this requires additional memory n * 4 bytes (assuming we are talking about a 32-bit integer value)

• The third approach is similar to using hashset, except that it requires less memory using a boolean array

   bool[] masks = new bool[list.Length]; for (int i = 0; i < list.length; i++) { if (masks[list[i]]) { // print or add to the result list } else { masks[list[i]] = true; } } 

it uses a boolean array instead of a HashSet. It has the same runtime as O (n), but requires 1/4 of the memory size, since the bool type takes 1 byte (8 bits), while the integer takes 4 bytes (32 bits)

• Finally, we can solve this problem using the BitVector32 class or our own bit offset operations.

   int check = 0; for (int i=0; i < list.Length; i++) { int mask = 1 << list[i]; if (check & mask == mask) { // print or add list[i] to the result list } else { check = check | mask; } } 

This will also result in a linear trigger time of only 32 bits of memory. So the memory usage is n / 32. Of course, this will not work if the maximum value in the array is greater than 32. We can use a 64-bit unsigned integer to increase the number of slots in the mask, but it still has a very short limit. In this case, if you create a BitVectory32 array, and you can transfer the bit to the BitVector32 object in the next index of the array. For example, the code would look something like this:

 BitVector32[] bitVectorArray = new BitVector32[maxValue / 32]; bitVectorArray[list[i] / 32] = 1 << list[i] % 32; 

Thus, you do not need to be limited to a 32-bit size limit. You can increase the size of a large mask indefinitely while memory capacity allows. So, all together:

 // This code assumes you know the range of the number in the array BitVector32[] bitVectorArray = new BitVector32[maxValue / 32]; for (int i=0; i < list.Length; i++) { int mask = 1 << list[i] % 32; if (bitVectorArray[(list[i] - 1)/32][i] & mask == mask) { // print or add list[i] to the result list } else { bitVectorArray[(list[i] - 1)/32] = bitVectorArray[list[i] / 32] | mask; } }