通过位运算符可以检查一个数字是否在数组中吗？

Question

也许这听起来有些无聊。我思考了很多，想知道是否可能实现类似的功能：将数组的所有元素相加，并使用结果与位掩码进行比较，以确定哪些数字在数组中。事实上，我不知道如何做到这一点，但应该差不多是这样的。

这种方法可行吗？

- cheroky

---

我猜你想这样做是为了避免循环遍历数组。无论哪种解决方案，你都需要以某种方式循环遍历数组。 - m0skit0

当然，你可以使用位运算符（xnor、水平AND）实现相等性检查，但是为什么要这样做呢？ - harold

@Harold，你能给个例子吗？我对这个非常感兴趣。 - cheroky

这里可能与“布隆过滤器”有关。 - Nick Zavaritsky

实际上，这听起来像是制作一个比要查找的数字数组更小的哈希函数/表，以确定数字是否[可能]在数组中。因此，您正在寻找一个哈希函数，并想知道是否可以使用位操作符来实现。 - Paul Ogilvie

Answer 1

只有当数组的所有元素都是精确的2的幂时，您才能这样做。 在这种情况下，可以用其元素的并集替换数组，并通过检查数字是否是2的幂以及其唯一位是否存在于和中来检查数字是否在数组中：

int sum = 0;
int array[] = { 1, 4, 8, 256, ... };
...
for (size_t i = 0; i < sizeof array/sizeof *array; i++) {
    sum |= array[i];
}
...
int n = get_value_for_n();

if ((n & (n - 1)) == 0 && (sum & n) != 0) {
    // n is a power of 2 present in sum
}

如果n为0，那么判断2的幂次方可能会出现错误的结果，但是sum & n无论如何都会等于0。

在大多数其他情况下，您需要遍历数组。如果这个数组很大，您可以对其进行排序，并使用二分查找来定位其中的数字。

- chqrlie

---

纯粹主义者可能会反对上述代码应该真正使用“unsigned int”以避免在“INT_MIN”上出现未定义的行为。 - chqrlie

如果您不知道数组的大小并且其中至少有2个相等的元素，这是否有效？ - VAndrei

只要数组元素都是2的幂次方，即使有重复项也可以使用“|”而不是“+”，这个方法仍然有效。你需要一种遍历数组的方法...你要么知道大小，要么可以计算它（就像我在示例中所做的那样），要么可以通过特定值（如“0”）来确定结尾。 - chqrlie

Answer 2

好的，如果你把这些数字加起来，你就无法确定数组中是否有某个特殊的数字。例如，想象一下你有一个数组：

int a[2]={2,4};

总和为6，但6可以由1+5得到，因此您在总和中丢失了信息。如果您的目标是快速在数组中查找数字，则建议使用二分查找。有关示例，请参见http://www.cplusplus.com/reference/algorithm/binary_search/。这是c++，而不是c，但您可以找到适用于c的兼容实现，例如http://www.programmingsimplified.com/c/source-code/c-program-binary-search。

- Mel Viso Martinez