11

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

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

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

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

谢谢

4

5 回答 5

12 
!p || q

很快。说真的，别担心。

于 2009-03-21T02:59:33.110 回答
11 
~p | q

对于可视化：

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

在紧凑的代码中，这应该比“！p || q”更快，因为后者有一个分支，这可能会由于分支预测错误而导致 CPU 停顿。位版本是确定性的，作为奖励，在 32 位整数中的工作量是布尔版本的 32 倍！

于 2009-03-21T03:00:25.557 回答
9

仅供参考，使用 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
于 2009-03-21T03:52:28.367 回答
4

您可以阅读从真值表派生布尔表达式（另见规范形式），了解如何将任何真值表表示为布尔基元或函数的组合。

于 2009-03-21T07:05:04.410 回答
1

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

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

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

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

对于正确的布尔值p和q（具有任一0或1二进制表示形式），它可以工作。否则T->T可能无法生成Tifp并且q具有任意非零值来表示真。

如果您只需要存储结果，从 Pentium II 开始，就有cmovcc（条件移动）指令（如 Derobert 的答案所示）。然而，对于布尔值，即使是 386 也有一个无分支选项，即setcc指令，它在结果字节位置（字节寄存器或内存）中产生0或产生。1您还可以在 Derobert 的回答中看到这一点，并且此解决方案还编译为涉及 a setcc( setbe: Set if below or equal) 的结果。

Derobert 和 Chris Dolan 的~p | q变体对于处理大量数据应该是最快的，因为它可以单独处理所有位的p含义q。

请注意，即使!p || q解决方案也无法编译为 x86 上的分支代码：它使用setcc指令。p如果或q可能包含表示真的任意非零值，那是最好的解决方案。如果您使用该_Bool类型，它将生成很少的指令。

在为 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类型时，编译器清楚地利用它只有两个可能的值（0false 和1true），产生与~a | b解决方案非常相似的结果（唯一的区别是后者对所有位执行补码，而不仅仅是最低位）。

为 64 位编译给出了几乎相同的结果。

Anyway, it is clear, the method doesn't really matter from the point of avoiding producing conditionals.

于 2016-08-16T11:51:27.130 回答