如何在C中使用按位或其他有效代码实现逻辑含义？

Question

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

p    q    p ? q
T    T      T
T    F      F
F    T      T
F    F      T

据维基百科称,这被称为" 逻辑蕴涵 "

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

谢谢

Answer 1

~p | q

可视化:

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

在紧密的代码中,这应该比"!p || q"快,因为后者有一个分支,由于分支预测错误,可能会导致CPU停顿.按位版本是确定性的,作为奖励,可以在32位整数中执行32倍于布尔版本的工作!

Answer 2

!p || q

很快.认真的,不要担心.

Answer 3

仅供参考,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 4

您可以阅读从真值表派生布尔表达式（另请参阅规范形式），以及如何将任何真值表表达为布尔原语或函数的组合。