alvatar alvatar - 3 months ago 36
C Question

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

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

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.

Comments