.net - 什么时候应该使用 BitVector32？

Question

我正在做一个项目，在某个时刻我需要展示一个月哪些日子仍然可用。有一个函数可以计算哪些天可用。我的同事说：“哦，我们知道，你应该返回一个BitVector32。这是处理布尔列表时最有效的方法。” 我会使用一个List<bool>或类似的东西。在我看来，当您实际使用位时， ABitVector32似乎是低级的东西。

所以，问题是。您是否应该BitVector32在需要一些少于 32 个项目的布尔值列表时使用它，还是应该只将它用于低级别的东西？

Answer 1

使用列表很容易扩展到其他时间段。假设您想一次显示两个月。哦，这比 32 大。我需要更改返回类型以及使用它的任何地方。伟大的！BitVector32甚至没有IEnumerable<T>实现.

除非它处于紧密循环中，可读性和可维护性最高。并且列表分配的开销并没有那么大，除非您每秒执行一百万次。

所以我同意你的观点，你应该只将 BitVector32 用于低级代码。

Answer 2

BitVector32 是围绕 c# 的位操作的包装器（或者您可以将其称为抽象）。例如，以下两个语句返回相同的结果：

• 1 << 1
• BitVector32.CreateMask(1)

假设有一个包含一些重复数字的整数数组。我们要查找所有重复项。当然，您可以简单地使用 Linq 中的 GroupBy 函数，但假设我们没有 Linq。

1. 第一个选项是蛮力方法，其中每个元素将与给定数组中的每个元素进行比较：

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

2. 由于蛮力方法将导致 N 平方运行时间，这非常低效，我们可以考虑使用 HashSet 它将提供恒定的查找时间或 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);
       }
   }
   

这种方法将导致线性运行时间或 O(n)。但是，它需要 n * 4 字节的额外内存（假设我们谈论的是 32 位整数）

1. 第三种方法类似于使用哈希集，只是它使用布尔数组需要更少的内存

   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;
       }
   }
   

它使用布尔数组而不是 HashSet。它具有相同的运行时间，即 O(n)，但需要 1/4 的内存量，因为 bool 类型占用 1 个字节（8 位），而整数占用 4 个字节（32 位）

1. 最后，我们可以使用 BitVector32 类或原生位移操作来解决这个问题。

   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;
       }
   }
   

它还将导致总共只有 32 位内存的线性运行时间。所以内存使用量是 n/32。当然，如果数组中的最大值大于 32，这将不起作用。我们可以使用 64 位无符号整数来增加掩码中的槽数，但它仍然有一个非常短的限制。在这种情况下，如果您创建一个BitVectory32数组，并且您可以将该位移动到该数组的下一个索引中的BitVector32对象。例如，代码将如下所示

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

这样，您不必受限于 32 位大小的限制。只要内存容量允许，您可以无限增加大掩码的大小。所以，把所有东西放在一起：

// 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;
    }
}