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

Question

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

unsigned char x3, x2, x1;

可以假设质数是函数 f，如果该数是质数，则输出 1，否则输出 0。

如何使用尽可能最优的按位运算（逻辑运算符）来解决这个问题？可以假设可以从 K.V 中提取最小 conjunctive/disjunctive 形式。真相图 table。

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

哪个会更快？

一些有用的数据：

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

Answer 1

因为输入不多，可以定义一个预计算的table PRIME，素数位置为1，其余位置为0。

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

Answer 2

较短的解决方案是：

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

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

#define isPrime(x3,x2,x1) ((x1) | ((x2) & ~(x3)))

Answer 3

按位

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

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

所以你会得到这样的结果（使用 uchar 作为 unsigned char 的 shorthand）：

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。

我没有证据证明这是使用逻辑运算符的最短表达式，所以如果有人有更短的版本，一定要 post 在评论中。然而，似乎不太可能有更短的版本，因为这本质上是一个单一的逻辑运算符，正如您将三元运算符扩展为适当的 if/else:[=45 时所看到的那样=]

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 快。它使用的指令要少得多，尽管指令越少并不总是意味着速度越快，但这些指令中的 none 似乎在 CPU 周期方面特别昂贵。

如果你取消两个函数共有的指令并比较剩下的指令，你会得到：

f_logical: je, jmp

f_bitwise: and (2), mov (2), sete, or

至于为什么逻辑版本更短，我想答案是分支。只有按位运算而没有分支，您必须在单个表达式中考虑所有可能性。

例如，在 (x3 & x1) | (~x3 & x2) 中，去掉右边的 ~x3 会更好，因为 you 已经知道x3 在那里为零，因为右侧代表值 0-3 的测试。但是计算机无法知道这一点，您也无法将其分解为更简单的表达式。

有了分支能力，您可以使用单个比较运算符将问题拆分为两个子问题。同样，这是有效的，因为对于值 0-3，x2 位本质上是一个 "is prime" 位，而对于值 4-7，x1 位是一个 "is prime" 位.

此外，alinsoar 是正确的，查找 table 会更快，但前提是值没有拆分为单独的位。对于单独变量中的位值，您要么必须使用 x3<<2 | x2<<1 | x1 之类的东西重建数字，要么必须将查找 table 定义为 3D 数组，在这种情况下，编译器会生成一堆执行索引 3D 数组所需的地址算术的额外说明。

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

Primality test using logical or relational operators on a 3-bit number

c

logical-operators

primality-test

relational-operators