c - 在 3 位数字上使用逻辑或关系运算符进行素数测试

Question

我期待使用逻辑运算符和关系运算符检查一个 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)

Answer 1

按位

我认为你在这里能做的最好的是(x3 & x1) | (~x3 & x2) .在 bool 代数中，这将表示为 AC + (!A)B . *简化 bool 代数表达式的常用规则似乎都不适用于此处，而且几个在线 bool 代数表达式简化器似乎也同意。

* (第二个 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 数组所需的地址算术。