检查C# BitArray中非零值的最快方法

Question

我正在尝试在C#中快速检测BitArrays之间的碰撞（使用AND布尔运算），这会产生一个表示重叠区域的单个BitArray。

显然，如果结果数组只包含零，则没有发生碰撞。如何最快地检查这一点？简单的迭代太慢了。我不关心碰撞发生在哪里，或者有多少个——只关心数组中是否存在非零值。

看起来应该有某种快速情况，类似于“将整个位数组转换为int值”（这特别行不通，因为BitArrays是可变大小的），但我想不出一个。

- Brent Sodman

---

你有没有考虑过不使用 BitArrays，而是直接使用 ints？ - itsme86

如果您自己实现，还可以避免在发生碰撞的情况下计算整个交集，并且不需要空间来存储交集。BitArray 的实现方式相当慢。 - harold

大家提供了很好的想法，感谢大家的帮助！ - Brent Sodman

Answer 1

你需要 And() 方法的结果 BitArray 吗？如果不需要，你可以只需循环遍历输入数组，并在第一次冲突时返回 true。

bool collision(BitArray a1, BitArray a2) {
   if (a1 == null || a2 == null) throw new ArgumentException("arguments cannot be null");
   if (a1.Count != a2.Count) throw new ArgumentException("arrays don't have same length");
   for (int i = 0; i < a1.Count; i++)
       if (a1[i] && a2[i]) return true;

   return false;
}

这样可以避免两次循环数组——即一次用于And()，一次用于检查。平均而言，您只需要遍历一半的数组一次，因此可以将速度提高4倍。

另一种方法是像@itsme86建议的那样使用int而不是BitArrays。

int a1, a2;
bool collision = (a1 & a2) > 0;

- derpirscher

---

我建议使用(a1 & a2) != 0，这样你就可以使用32个可用位而不仅仅是31个。 - harold

@Aron 不行。这个问题的整点意义就在于效率。 - harold

@Aron，你的代码片段存在一些问题：

1. BitArray没有实现System.Collections.Generic.IEnumerable接口，因此不能与Enumerable.Zip一起使用。
2. BitArray的项是布尔值，因此All(x => x>0)无法编译通过。

- derpirscher

@Aron 当然，你可以慢慢做，然后再并行化 - 但你也可以快速地并行化。故意让它变慢没有任何意义。 - harold

@Aron 当然，希望它能做得不错，使其变得不那么糟糕。至于证据，你也没有提供任何证据，这样我们就处于什么位置呢？你肯定之前也检查过这种情况，我也是，其他人也是。结果总是一样的，LINQ会输给普通的 for 循环。 - harold

Answer 2

如果有人仍在寻找一个好的解决方案，因为这里还没有：

比特数组以零进行初始化，因此您可以将一个新的比特数组（长度相同）与两个比特数组的AND结果进行比较（注意“！”反转布尔值...）：

if (!new BitArray(bitCountOfResult).Equals(result)) {
    // We hit!
}

快速且适用于我。请确保避免使用LINQ方法，它非常慢。

- OldManCoding