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

Question

我正在尝试快速检测 C# 中 BitArray 之间的冲突（使用 AND 布尔运算），这会导致单个 BitArray 表示重叠区域。

显然，如果生成的数组仅由零组成，则不会发生冲突。检查这个的最快方法是什么？简单的迭代太慢了。我不关心碰撞在哪里，或者有多少——只关心数组中某处有一个非零值。

似乎应该有某种类似 "cast the entire bit array to an int value" 的快速案例（特别是行不通，因为 BitArrays 是可变大小的），但我想不出一个。

Answer 1

您需要 And() 方法生成的 BitArray 吗？如果没有，您可以循环输入数组并在第一次碰撞时 return 为真。

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 建议使用整数而不是 BitArrays

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

Answer 2

以防万一有人还在寻找一个好的解决方案，因为这里没有：

Bitarrays 用零初始化，所以你可以简单地将一个新的 BitArray（相同长度）与你的 AND-result 的两个 BitArrays 进行比较（注意“！”，反转 bool ...）：

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

速度快，适合我。确保避开 LINQ-approach，它非常慢。

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

Fastest way to check C# BitArray for non-zero value

c#

arrays

algorithm

bitarray

collision