什么时候应该使用BitVector32？

Question

我在一个项目中工作，在某个时刻，我需要显示一个月，哪些天仍然是可用的。有一个函数可以计算哪些天是可用的。我的同事说：“哦，我们知道，你应该返回一个BitVector32。这是处理布尔值列表时最有效的。”我会使用List或类似的东西。在我看来，当您实际使用bits时，BitVector32似乎是用于低级内容的东西。

所以，问题是。当需要少于32项的布尔值列表时，是否应该使用BitVector32，还是应该只将其用于低级内容？

Answer 1

使用列表很容易扩展到其他时间段。假设你想一次显示两个月。哦，这比32大多了。我需要改变返回类型和使用它的地方。太棒了！而且BitVector32甚至没有实现IEnumerable<T>。

除非它处于一个紧凑的循环中，否则可读性和可维护性是最高效率的。列表分配的开销不是很大，除非你每秒做一百万次。

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

Answer 2

BitVector32是对c#位操作的封装(或者你也可以称之为抽象)。例如，下面两条语句返回相同的结果：

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

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

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

foreach(列表中的int i){foreach(列表中的int j) { if (i == j){ //打印此结果或将其存储在结果列表中}}

• 由于暴力破解方法将导致N平方运行时间，这是非常低效的，我们可以考虑利用HashSet，它将提供恒定的查找时间或O(1)

HashSet hashSet = new HashSet()；foreach(列表中的int i){ if (hashSet.Contains(i)) { //打印副本或将其添加到结果列表} else { hashSet.Add(i)；} }

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

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

bool[] boollist.Length=新掩码；for (int i= 0；i< list.length；i++) { if ( masks[listi] ) { //打印或添加到结果列表} else {masks[listi]= 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 << listi；if (check & mask == mask) { //将listi打印或添加到结果列表} 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;
    }
}