我期待着使用逻辑和关系运算符检查 3 位数字是否是素数。该数字使用 3 个变量表示，其中位 7-1 设置为 0，只有位置 0 上的位是实际数据。假设我们有：
unsigned char x3, x2, x1;
可以假设素数是函数f，如果该数是素数，则输出1，否则0。
如何使用尽可能优化的按位运算(逻辑运算符)来解决此问题？可以假设可以从真值表的 K.V. 图中提取最小合取/析取形式。
如何使用关系运算符解决此问题？
哪一个会更快？
一些有用的数据：
CDF: (~x2 & X1) | (X0 & X2)
CCF: (X1 | X2) & (X0 | ~X2)
按位
我认为你在这里能做的最好的事情就是(x3 & x1) | (~x3 & x2)。在布尔代数中，这将表示为AC + (!A)B。*简化布尔代数表达式的常用规则似乎都不适用于这里，几个在线布尔代数表达式简化器似乎都同意。
*(第二个A通常会用一个栏写，但我不知道如何在 markdown 中做到这一点)。
所以你会得到这样的东西(使用uchar作为unsigned char的简写)：
uchar f_bitwise(uchar x3, uchar x2, uchar x1)
{
return (x3 & x1) | (~x3 & x2);
}
由此生成的程序集(-O0并丢弃函数调用开销)如下所示：
movzx eax, BYTE PTR [rbp-4] # move x3 into register eax
and al, BYTE PTR [rbp-12] # bitwise AND the lower half of eax with x1
mov ecx, eax # store the result in ecx
cmp BYTE PTR [rbp-4], 0 # compare x3 with 0
sete al # set lower half of eax to 1 if x3 was equal to 0
mov edx, eax # store the result in edx (this now equals ~x3)
movzx eax, BYTE PTR [rbp-8] # move x2 into eax
and eax, edx # bitwise AND ~x3 (in edx) with x2 (in eax)
or eax, ecx # finally, bitwise OR eax and ecx
结果存储在eax中。
逻辑
查看值 0-7 的位，并尝试识别一个简单的模式来抠键，您会注意到对于值 0-3，当且仅当x2为 1 时，该数字是素数。同样，对于值 4-7，当且仅当x1为 1 时，该数字为素数。此观察结果产生了一个简单的表达式：x3 ? x1 : x2。
我没有证据表明这是使用逻辑运算符的最短可能表达式，所以如果有人有较短的版本，请务必将其发布在评论中。但是，鉴于这本质上是一个单一的逻辑运算符，这似乎不太可能有更短的版本，如您所见，如果您将三元运算符扩展为适当的if/else：
uchar f_logical(uchar x3, uchar x2, uchar x1)
{
if (x3 != 0)
return x1;
else
return x2;
}
由此生成的程序集如下(同样是-O0，不计算函数调用开销)：
cmp BYTE PTR [rbp-4], 0 # compare x3 with 0
je .L2 # if equal, jump to label L2
movzx eax, BYTE PTR [rbp-12] # move x1 into register eax
jmp .L4 # jump to label L4 (i.e., return from function)
.L2:
movzx eax, BYTE PTR [rbp-8] # move x2 into register eax
.L4:
# Function return. Result is once again stored in eax.
我还没有测试过这两个功能的性能，但仅从组件来看，似乎几乎可以肯定f_logical会比f_bitwise运行得更快。它使用的指令要少得多，虽然更少的指令并不总是等同于更快的指令，但就CPU周期而言，这些指令似乎都不会特别昂贵。
如果您取消这两个函数的共同指令并比较剩余的指令，您将获得：
f_logical：je，jmp
f_bitwise：and(2)，mov(2)，sete，or
至于为什么逻辑版本更短，我认为答案是分支。由于只有按位运算而没有分支，您必须在单个表达式中考虑所有可能性。
例如，在(x3 & x1) | (~x3 & x2)中，最好去掉右侧的~x3，因为您已经知道那里x3为零，因为右侧表示值 0-3 的测试。但是计算机无法知道这一点，你不能把它分解成一个更简单的表达式。
借助分支功能，您可以使用单个比较运算符将问题拆分为两个子问题。同样，这是有效的，因为对于值 0-3，x2位本质上是"是素数"位，而对于值 4-7，x1位是"是素数"位。
此外，alinsoar是正确的，查找表会更快，但前提是该值没有拆分为单个位。由于位值位于单独的变量中，您要么必须使用x3<<2 | x2<<1 | x1之类的东西重建数字，要么必须将查找表定义为 3D 数组，在这种情况下，编译器会生成一堆额外的指令来执行索引 3D 数组所需的地址算术。
较短的解决方案是：
int isPrime(unsigned char x3, unsigned char x2, unsigned char x1) {
return x1 | (x2 & ~x3);
}
x1是匹配所有奇数。在区间 [1..7] 中，它们都是素数。(x2 & ~x3)是匹配值 2(实际上它匹配 2 和 3)。
使用编译器资源管理器，可以比较各种编译器在各种体系结构上生成的代码。gcc x86_64 vs ARM64 的示例：https://godbolt.org/z/JwtES4
注意：对于这样的小函数，#define将比函数调用更快且更短。
#define isPrime(x3,x2,x1) ((x1) | ((x2) & ~(x3)))
因为输入不多，所以您可以定义一个预先计算的表 PRIME，该表在素数的位置上有 1，其余位置有 0
。例如，PRIME(0,1,1) = 1，而 PRIME(1,0,1)=0，即 PRIME(3)=true，PRIME(6)=false。