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

Issue

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

Solution

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.

And even better, with _Bool (thanks @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   

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

Since I'm updating today, I've confirmed gcc 8.2.0 produces similar, though not identical, results for _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   

Answered By - derobert

Answer Checked By - Clifford M. (PHPFixing Volunteer)