Wie könnte ich logische Implikation mit bit- oder anderen effizienten Code in C implementieren?

Question

Ich mag 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 " logische Implikation "

Ich habe versucht, lange, um herauszufinden, wie diese in C mit bitweise Operationen zu machen, ohne conditionals zu verwenden. Vielleicht hat jemand ein paar Gedanken über es.

Danke

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.

Und noch besser, mit _Bool (dank @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   

Also, mit _Bool statt int ist eine gute Idee.

Da ich heute zu aktualisieren, ich habe 8.2.0 bestätigt gcc ähnlich produziert, wenn auch nicht identisch, Ergebnisse für _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 2

~p | q

Zur Visualisierung:

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

In engen Code, sollte dies schneller sein als „! P || q“, weil dieser eine Zweigniederlassung hat, die einen Stall in den CPU aufgrund eines Verzweigungsvorhersagefehler verursachen könnte. Die bitweise Version ist deterministisch und als Bonus können in einem 32-Bit-Integer als die boolean Version so viel Arbeit 32 mal tun!

Answer 3

!p || q

viel schneller ist. ernst, nicht darum kümmern.

Answer 4

Sie können lesen Sie auf Booleschen Ausdrücken von Wahrheitstabellen Ableiten (auch finden Sie unter kanonischer Form ), wie Sie jede Wahrheitstabelle als eine Kombination ausdrücken können boolean Primitiven oder Funktionen.

Answer 5

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

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

Es funktioniert, da durch den C-Standard stellt 0 falsch, und jeder anderer Wert true (1 für wahr von Booleschen Operatoren, int Typ zurückgegeben).

Die „Schmutzigkeit“ ist, dass ich booleans (p und q) Verwendung als ganze Zahlen, die einige starke Typisierung Politik (wie MISRA) widerspricht, na ja, das ist eine Optimierung Frage. Sie können immer es als Makro #define die schmutzigen Sachen zu verstecken.

Für die richtige boolean p und q (mit entweder 0 oder 1 binären Darstellungen) es funktioniert. Ansonsten T->T könnte T zu produzieren scheitern, wenn p und q beliebige Werte ungleich Null haben für die Darstellung wahr.

Wenn Sie nur das Ergebnis zu speichern, da das Pentium II gibt es die cmovcc (Conditional Move) Instruktion (wie in Derobert Antwort gezeigt). Für booleans jedoch selbst hatte die 386 eine branchless Option, die setcc Anweisung, die 0 oder 1 in Folge Byteort (Byte-Register oder Speicher) erzeugt. Sie können auch in Derobert Antwort sehen, dass, und diese Lösung stellt auch ein Ergebnis einen setcc (setbe: Gesetzt, wenn unter oder gleich) beteiligt ist.

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

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

ich habe folgende Zahlen, wenn für die x86-Zusammenstellung:

__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 der _Bool Typ verwendet wird, der Compiler nutzt deutlich, dass es nur zwei mögliche Werte (0 für falsch und 1 für true), ein sehr ähnliches Ergebnis an der ~a | b Lösung erzeugt (der einzige Unterschied ist, dass diese eine Ergänzung führt auf alle Bits statt nur den niedrigsten Bit).

für 64 Bit Kompilieren gibt nur etwa die gleichen Ergebnisse.

Wie auch immer, es ist klar, wird das Verfahren wirklich nicht von dem Punkt, egal Herstellung conditionals zu vermeiden.