c - 是否可以通过少于 9 次比较来检查 2 组 3 个整数中的任何一个是否相等？

Question

int eq3(int a, int b, int c, int d, int e, int f){
    return a == d || a == e || a == f 
        || b == d || b == e || b == f 
        || c == d || c == e || c == f;
}

此函数接收 6 个整数，如果前 3 个整数中的任何一个等于最后 3 个整数中的任何一个，则返回 true。是否有类似按位破解的方法来使其更快？

Answer 1

假设您预计 false 结果的发生率很高，您可以进行快速“预检查”以快速隔离此类情况:

如果在 a 中设置了一个位，但在 d、e 和 f 中都没有设置> 然后 a 不能等于其中任何一个。

像这样

int pre_eq3(int a, int b, int c, int d, int e, int f){
    int const mask = ~(d | e | f);
    if ((a & mask) && (b & mask) && (c & mask)) {
         return false;
    }
    return eq3(a, b, c, d, e, f);
}

可以加快它的速度(8 次操作而不是 9 17 次，但如果结果实际上是 true，成本会更高)。如果 mask == 0 那么这当然无济于事。

---

如果很有可能 a & b & c 设置了一些位，这可以进一步改进:

int pre_eq3(int a, int b, int c, int d, int e, int f){
    int const mask = ~(d | e | f);
    if ((a & b & c) & mask) {
        return false;
    }
    if ((a & mask) && (b & mask) && (c & mask)) {
         return false;
    }
    return eq3(a, b, c, d, e, f);
}

现在，如果 a、b 和 c 的所有都设置了位，而 d、e 和 c 都没有设置任何位，我们很快就会出局。