如何找到区分两个整数集合的高效位运算表达式？

问题拆解 #

我们需要构造仅使用&、|、~、^的位运算表达式，使得输入整数n∈{1,3,4,6}时返回非零值，n∈{0,2,5,7}时返回零值。由于n是0-7的整数，对应3位二进制数b2b1b0（b2为最高位，对应4；b1对应2；b0对应1），可以将问题转化为布尔函数化简问题。

确定性构造方法：卡诺图化简 #

1. 先列出所有输入的二进制与期望输出：

   n	二进制(b2b1b0)	输出（非零/零）
   0	000	零
   1	001	非零
   2	010	零
   3	011	非零
   4	100	非零
   5	101	零
   6	110	非零
   7	111	零

2. 绘制3变量卡诺图并分组：

   b1b0
   b2 | 00 01 11 10
   0  | 0  1  1  0
   1  | 1  0  0  1
   

   可以找到两组最大的有效区域：

   • b2=0且b0=1（对应n=1、3）：表达式为~b2 & b0
   • b2=1且b0=0（对应n=4、6）：表达式为b2 & ~b0

3. 合并两组表达式：
   上述两个表达式的合并等价于b2与b0异或（b2 ^ b0），因为异或的逻辑就是两个位不同时结果为真。

最终位运算表达式 #

将布尔表达式转化为针对整数n的位运算：

• b2是n的最高位，可通过n >> 2获取（右移2位后得到0或1）
• b0是n的最低位，可通过n & 1获取
• 异或运算直接用^操作符

最终表达式为：

(n >> 2) ^ (n & 1)

验证所有情况 #

• n=0：0 >>2 ^ 0&1 = 0^0=0 ✔️
• n=1：0>>2 ^1&1=0^1=1（非零）✔️
• n=2：0>>2 ^2&1=0^0=0 ✔️
• n=3：0>>2 ^3&1=0^1=1（非零）✔️
• n=4：4>>2 ^4&1=1^0=1（非零）✔️
• n=5：5>>2 ^5&1=1^1=0 ✔️
• n=6：6>>2 ^6&1=1^0=1（非零）✔️
• n=7：7>>2 ^7&1=1^1=0 ✔️

对比暴力拼接方式 #

暴力方式需要逐个匹配目标数的位特征再用|拼接，例如：

((~n & ~2 & 1) | (~n & 2 & 1) | (n & ~2 & ~1) | (n & 2 & ~1)) & 1

显然化简后的异或表达式更简洁高效，运算量仅为两次位操作+一次异或，远优于暴力方式。

内容的提问来源于stack exchange，提问作者gbromios