0

我期待使用逻辑运算符和关系运算符检查 3 位数字是否为素数。该数字使用 3 个变量表示，其中 7-1 位设置为 0，只有位置 0 上的位是实际数据。假设我们有：

unsigned char x3, x2, x1;

可以假设素数是一个函数，如果该数是素数则f输出，否则。10

如何使用尽可能最优的按位运算（逻辑运算符）来解决这个问题？可以假设可以从真值表的 KV 图中提取最小合取/析取形式。

如何使用关系运算符解决这个问题？

哪个会更快？

一些有用的数据：

CDF: (~x2 & X1) | (X0 & X2)
CCF: (X1 | X2) & (X0 | ~X2)
4

3 回答 3

3

按位

我认为你在这里能做的最好的就是(x3 & x1) | (~x3 & x2)。在布尔代数中，这将表示为AC + (!A)B。*简化布尔代数表达式的常用规则似乎都不适用于这里，并且一些在线布尔代数表达式简化器似乎同意。

* （第二个A通常会在上面写一个条，但我不知道如何在降价中做到这一点）。

所以你会得到这样的东西（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，该x2位本质上是一个“素数”位，而对于值 4-7，该x1位是一个“素数”位。

此外，alinsoar 是正确的，查找表会更快，但前提是该值不拆分为单个位。使用单独变量中的位值，您要么必须使用类似的东西来重建数字x3<<2 | x2<<1 | x1，要么必须将查找表定义为 3D 数组，在这种情况下，编译器会生成一堆额外的指令来执行必要的地址运算索引一个 3D 数组。

于 2019-03-20T00:16:54.263 回答
1

因为没有太多输入，您可以定义一个预先计算的表 PRIME，其中素数的位置为 1，其余的为 0。

例如，PRIME(0,1,1) = 1 而 PRIME(1,0,1)=0，即 PRIME(3)=true，PRIME(6)=false。

于 2019-03-19T21:58:55.867 回答
1

较短的解决方案是：

int isPrime(unsigned char x3, unsigned char x2, unsigned char x1) {
  return x1 | (x2 & ~x3);
}
  • x1是匹配所有奇数。在区间 [1..7] 中，它们都是素数。
  • (x2 & ~x3)是匹配值 2（实际上它匹配 2 和 3）。

使用 Compiler Explorer，您可以比较各种编译器在各种架构上生成的代码。gcc x86_64 与 ARM64 的示例：https ://godbolt.org/z/JwtES4

注意：对于像这样的小函数， a#define将比函数调用更快且更短。

#define isPrime(x3,x2,x1) ((x1) | ((x2) & ~(x3)))
于 2019-03-19T22:47:44.153 回答