How could I implement logical implication with bitwise or other efficient code in C?

Question

I want to implement a logical operation that works as efficient as possible. I need this truth table:

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

This, according to wikipedia is called "logical implication"

I've been long trying to figure out how to make this with bitwise operations in C without using conditionals. Maybe someone has got some thoughts about it.

Thanks

Answer 1

!p || q

is plenty fast. seriously, don't worry about it.

Answer 2

~p | q

For visualization:

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

In tight code, this should be faster than "!p || q" because the latter has a branch, which might cause a stall in the CPU due to a branch prediction error. The bitwise version is deterministic and, as a bonus, can do 32 times as much work in a 32-bit integer than the boolean version!

Answer 3

FYI, with gcc-4.3.3:

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

Gives (from 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

So, no branches, but twice as many instructions.

@litb: Ok, here is with _Bool:

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

So, using _Bool instead of int is a good idea.

Answer 4

You can read up on deriving boolean expressions from truth Tables (also see canonical form), on how you can express any truth table as a combination of boolean primitives or functions.