如何在 C 中使用按位或其他高效代码实现逻辑蕴涵？

Question

我想实现一个尽可能高效的逻辑运算。我需要这个真值表：

p    q    p → q
T    T      T
T    F      F
F    T      T
F    F      T

根据维基百科，这被称为“逻辑含义"

我长期以来一直试图弄清楚如何在 C 中使用按位运算而不使用条件来实现这一点。也许有人对此有一些想法。

谢谢

Answer 1

仅供参考，用gcc-4.3.3：

int foo(int a, int b) { return !a || b; }
int bar(int a, int b) { return ~a | b; }

得到（从objdump的-d）：

0000000000000000 <foo>:
   0:   85 ff                   test   %edi,%edi
   2:   0f 94 c2                sete   %dl
   5:   85 f6                   test   %esi,%esi
   7:   0f 95 c0                setne  %al
   a:   09 d0                   or     %edx,%eax
   c:   83 e0 01                and    $0x1,%eax
   f:   c3                      retq   

0000000000000010 <bar>:
  10:   f7 d7                   not    %edi
  12:   09 fe                   or     %edi,%esi
  14:   89 f0                   mov    %esi,%eax
  16:   c3                      retq   

所以，没有分支，但两倍多的指令。

和甚至更好，与_Bool（感谢@litb）：

_Bool baz(_Bool a, _Bool b) { return !a || b; }

0000000000000020 <baz>:
  20:   40 84 ff                test   %dil,%dil
  23:   b8 01 00 00 00          mov    $0x1,%eax
  28:   0f 45 c6                cmovne %esi,%eax
  2b:   c3                      retq   

因此，使用_Bool代替int是一个好主意。

由于我今天更新，我们已经确认的gcc 8.2.0产生类似于但不相同，为_Bool:结果

0000000000000020 <baz>:
  20:   83 f7 01                xor    $0x1,%edi
  23:   89 f8                   mov    %edi,%eax
  25:   09 f0                   or     %esi,%eax
  27:   c3                      retq   

Answer 2

~p | q

有关的可视化：

perl -e'printf "%x\n", (~0x1100 | 0x1010) & 0x1111'
1011

在紧代码，这应该是比“P！|| q”型更快，因为后者有分支，这可能会导致所述CPU在失速由于分支预测错误。按位版本是确定的，作为奖励，可以做32倍多的工作在32位整数比布尔版本！

Answer 3

!p || q

是足够快。严重的是，不要担心。

Answer 4

可以在导出从真值表布尔表达式阅读起来（也看到规范形式），你如何能表达任何真值表作为组合布尔原语或功能。

Answer 5

C 布尔值的另一个解决方案（有点脏，但有效）：

((unsigned int)(p) <= (unsigned int)(q))

它按照 C 标准工作， 0 代表 false，任何其他值代表 true (1 布尔运算符返回 true， int 类型）。

“肮脏”是我使用布尔值（p 和 q）作为整数，这与一些强类型策略（例如 MISRA）相矛盾，好吧，这是一个优化问题。你可能永远 #define 它作为一个宏来隐藏脏东西。

对于正确的布尔值 p 和 q （有任一 0 或者 1 二进制表示）它有效。否则 T->T 可能无法产生 T 如果 p 和 q 有任意非零值来表示 true。

如果你只需要存储结果，从 Pentium II 开始，有 cmovcc （条件移动）指令（如德罗伯特的回答所示）。然而，对于布尔值，即使 386 也有无分支选项， setcc 指令，产生 0 或者 1 在结果字节位置（字节寄存器或内存）。您还可以在德罗伯特的回答中看到这一点，并且该解决方案还可以编译为涉及以下内容的结果： setcc (setbe: ：如果低于或等于则设置）。

德罗伯特和克里斯·多兰的 ~p | q 变体应该是处理大量数据最快的，因为它可以处理所有位的含义 p 和 q 单独。

请注意，甚至没有 !p || q 解决方案编译为 x86 上的分支代码：它用 setcc 指示。这是最好的解决方案，如果 p 或者 q 可以包含表示 true 的任意非零值。如果您使用 _Bool type，它会生成很少的指令。

我在x86编译时得到了以下数据：

__attribute__((fastcall)) int imp1(int a, int b)
{
 return ((unsigned int)(a) <= (unsigned int)(b));
}

__attribute__((fastcall)) int imp2(int a, int b)
{
 return (!a || b);
}

__attribute__((fastcall)) _Bool imp3(_Bool a, _Bool b)
{
 return (!a || b);
}

__attribute__((fastcall)) int imp4(int a, int b)
{
 return (~a | b);
}

组装结果：

00000000 <imp1>:
   0:   31 c0                   xor    %eax,%eax
   2:   39 d1                   cmp    %edx,%ecx
   4:   0f 96 c0                setbe  %al
   7:   c3                      ret    

00000010 <imp2>:
  10:   85 d2                   test   %edx,%edx
  12:   0f 95 c0                setne  %al
  15:   85 c9                   test   %ecx,%ecx
  17:   0f 94 c2                sete   %dl
  1a:   09 d0                   or     %edx,%eax
  1c:   0f b6 c0                movzbl %al,%eax
  1f:   c3                      ret    

00000020 <imp3>:
  20:   89 c8                   mov    %ecx,%eax
  22:   83 f0 01                xor    $0x1,%eax
  25:   09 d0                   or     %edx,%eax
  27:   c3                      ret    

00000030 <imp4>:
  30:   89 d0                   mov    %edx,%eax
  32:   f7 d1                   not    %ecx
  34:   09 c8                   or     %ecx,%eax
  36:   c3                      ret    

当使用 _Bool 类型，编译器清楚地利用了它只有两个可能的值（0 对于虚假和 1 为 true），产生与 ~a | b 解决方案（唯一的区别是后者对所有位执行补码，而不仅仅是最低位）。

编译 64 位会得到几乎相同的结果。

无论如何，很明显，从避免产生条件的角度来看，该方法并不重要。