是否有一种通用方法来优化区分两个任意整数集的按位表达式？

Question

对于上下文，我需要为 0 到 7 之间的整数编写一个测试，对于

{1,3,4,6}

计算结果为 true，对于

{0,2,5,7}

计算结果为 false。我想了几分钟，是否有一个简短的表达式组合了一些按位运算来完成这项工作（例如，类似于

n & 1

在

{1,3,5,7}

上的工作方式），但没有一个让我惊讶。

在实践中，这里并不迫切需要使用按位算术，诸如开关或查找表之类的东西可以很好地工作，但这确实让我想知道是否存在确定性的方法来找到这样的表达式：给出非零结果当对第一组中的数字进行评估时，对第二组中的数字进行零评估时，仅使用按位

and

、

or

、

not

和

xor

（因此，例如，没有布尔值

&&

或

 ==

）

我没有数学背景来证实它，但感觉应该可以合理地假设应该可以编写某种“强力”表达式，无论上限如何，其中每种情况都单独评估，并通过以下方式链接在一起

|

，但是有没有一种更有效的方法，要么简化“最坏情况”的实现，要么从头开始构建一个？

Answer 1

在这种特殊情况下，最佳解决方案是单字节查找表，例如

(1 << x & (1 << 1 | 1 << 3 | 1 << 4 | 1 << 6)) != 0

。这比使用 and、or、not 和 xor 的任何组合来计算相同的结果更有效。

顺便说一句，C/C++/Rust 编译器很智能。给定

assert!(x >= 0 && x <= 7);

，rustc 从

!matches!(x, 0 | 2 | 5 | 7)

生成几乎最佳的代码，并且从

matches!(x, 1 | 3 | 4 | 6)

几乎同样好。