Wie könnte ich logische Implikation mit bitweisem oder anderem effizientem Code in C implementieren?

Question

Ich möchte eine logische Operation implementieren, die so effizient wie möglich funktioniert. Ich brauche diese Wahrheitstabelle:

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

Dies ist laut wikipedia genannt wird „logical implication“

Ich habe lange versucht, herauszufinden, wie man dies in C mit bitweise Operationen ohne Verwendung conditionals zu machen. Vielleicht hat jemand ein paar Gedanken dazu.

Dank

Answer 1

FYI, mit gcc-4.3.3:

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

Gibt (von 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 

Also, keine Verzweigungen, aber doppelt so viele Anweisungen.

@litb: Ok, ist hier mit _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 

Also, mit _Bool statt int eine gute Idee ist.

Answer 2

!p || q 

viel schneller ist. ernsthaft, mach dir keine Sorgen darüber.

Answer 3

~p | q 

Zur Visualisierung:

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

In engen Code, sollte dies schneller sein als "! P || q", weil die letztere hat einen Zweig, der einen Stall in der CPU verursachen könnten aufgrund ein Verzweigungsvorhersagefehler. Die bitweise Version ist deterministisch und kann als Bonus 32 Mal mehr in einer 32-Bit-Ganzzahl als die boolesche Version arbeiten!

Answer 4

Sie können lesen auf deriving boolean expressions from truth Tables (siehe auch canonical form), auf, wie Sie jede Wahrheitstabelle als eine Kombination von booleschen Primitiven oder Funktionen ausdrücken können.

Answer 5

Eine andere Lösung für C booleans (ein bisschen schmutzig, aber funktioniert):

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

Es seit der C-Standard arbeitet, 0 stellt falsch, und jeder andere Wert true (1 wird true zurückgegeben von booleschen Operatoren, int Typ).

Die "Schmutzigkeit" ist, dass ich booleans (und q) als Ganzzahlen verwenden, die einige starke Schreibstrategien (wie MISRA) widerspricht, nun, das ist eine Optimierungsfrage. Sie können immer #define es als ein Makro, um die schmutzigen Sachen zu verbergen.

Für richtig boolean und q (entweder 0 oder 1 binäre Darstellungen) funktioniert es. Sonst könnte T->TT nicht erzeugen, wenn und q beliebige Nicht-Null-Werte für die Darstellung von true haben.

Wenn Sie nur das Ergebnis speichern müssen, gibt es seit dem Pentium II die Anweisung cmovcc (Conditional Move) (wie in Deroberts Antwort gezeigt). Für Booleans hatte jedoch selbst der 386 eine Verzweigungslose-Option, die setcc-Anweisung, die 0 oder 1 in einer Ergebnisbyteposition (Byte-Register oder Speicher) erzeugt. Sie können dies auch in Deroberts Antwort sehen, und diese Lösung kompiliert auch zu einem Ergebnis, das eine setcc (setbe: Set wenn unter oder gleich) enthält.

Derobert und Chris Dolan ~p | q Variante sollte die schnellste für die Verarbeitung großer Datenmengen sein, da es die Auswirkungen auf alle Bits von p und q einzeln verarbeiten kann.

Beachten Sie, dass nicht einmal die !p || q Lösung kompiliert zu Verzweigung Code auf dem x86: Es verwendet setcc Anweisungen. Das ist die beste Lösung, wenn oder q willkürliche Werte ungleich Null enthalten können, die wahr darstellen. Wenn Sie den Typ _Bool verwenden, werden nur sehr wenige Anweisungen generiert.

bekam ich folgende Zahlen, wenn für die x86-Kompilierung:

__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); 
} 

Montage Ergebnis:

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  

Wenn die Art _Bool Verwendung der Compiler nutzt deutlich, dass es nur zwei mögliche Werte hat (0 für false und 1 für true), was ein sehr ähnliches Ergebnis ergibt wie die ~a | b Lösung (der einzige Unterschied ist, dass letzterer eine Ergänzung für alle Bits durchführt, anstatt nur die niedrigstes Bit).

Compiling für 64 Bits gibt nur ungefähr die gleichen Ergebnisse.

Wie auch immer, es ist klar, die Methode spielt keine Rolle, um die Herstellung von Bedingungen zu vermeiden.