Ich möchte eine logische Operation implementieren, die so effizient wie möglich funktioniert. Ich brauche diese Wahrheitstabelle:
%Vor%Dies wird laut Wikipedia " logische Implikation "
genanntIch habe lange versucht, herauszufinden, wie man dies mit bitweisen Operationen in C macht, ohne Bedingungen zu verwenden. Vielleicht hat jemand ein paar Gedanken dazu.
Danke
Zur Visualisierung:
%Vor%In tightem Code sollte dies schneller als "! p || q" sein, weil letzterer eine Verzweigung hat, die aufgrund eines Verzweigungsvorhersagefehlers einen Stillstand in der CPU verursachen könnte. Die bitweise Version ist deterministisch und kann als Bonus 32 Mal so viel in einer 32-Bit-Ganzzahl arbeiten als die boolesche Version!
Sie können auf Boolesche Ausdrücke aus Wahrheitstabellen ableiten (siehe auch Kanonform ), wie man eine Wahrheitstabelle als eine Kombination von booleschen Primitiven oder Funktionen ausdrücken kann.
Eine andere Lösung für C booleans (ein bisschen schmutzig, aber funktioniert):
((unsigned int)(p) <= (unsigned int)(q))
Es funktioniert, da nach dem C-Standard 0 false darstellt und jeder andere Wert true ( 1 wird von booleschen Operatoren mit int type zurückgegeben).
Die "Schmutzigkeit" besteht darin, dass ich boolesche Werte ( p und q ) als Ganzzahlen verwende, was einigen starken Schreibstrategien (wie MISRA) widerspricht, nun, das ist eine Optimierungsfrage. Du kannst immer #define als Makro verwenden, um die schmutzigen Sachen zu verstecken.
Für die richtige boolesche p und q (mit 0 oder 1 binären Darstellungen) funktioniert es. Andernfalls könnte T->T T nicht erzeugen, wenn p und q willkürliche Werte ungleich Null 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 Option ohne Verzweigung, die setcc Anweisung, die 0 oder 1 in einer Ergebnisbyteposition (Byte-Register oder Speicher) erzeugt. Sie können dies auch in der Antwort von Derobert sehen, und diese Lösung wird auch zu einem Ergebnis kompiliert, das ein setcc ( setbe : Set, wenn unter oder gleich) enthält.
Die ~p | q -Variante von Derobert und Chris Dolan sollte für die Verarbeitung großer Datenmengen am schnellsten sein, da sie die Implikation für alle Bits von p und q individuell verarbeiten kann.
Beachten Sie, dass nicht einmal die !p || q -Lösung zum Verzweigungscode auf dem x86 kompiliert: Sie verwendet setcc -Anweisungen. Das ist die beste Lösung, wenn p oder q willkürliche Werte ungleich Null enthalten können, die "true" darstellen. Wenn Sie den Typ _Bool verwenden, werden nur wenige Anweisungen generiert.
Ich habe die folgenden Zahlen beim Kompilieren für das x86 erhalten:
%Vor%Montageergebnis:
%Vor% Wenn der _Bool -Typ verwendet wird, nutzt der Compiler eindeutig, dass er 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 (die einzige Der Unterschied besteht darin, dass letzterer ein Komplement für alle Bits durchführt und nicht nur für das niedrigste Bit.
Das Kompilieren für 64 Bits ergibt ungefähr die gleichen Ergebnisse.
Wie auch immer, es ist klar, dass die Methode keine Rolle spielt, um die Herstellung von Bedingungen zu vermeiden.
Tags und Links c c++ performance logic algebra