Bei der Programmierung muss oft überprüft werden, ob eine Zahl ungerade oder gerade ist. Dafür verwenden wir normalerweise:
%Vor% Ich verstehe jedoch, dass der Operator '%' tatsächlich eine Division ausführt und seinen Rest zurückgibt; Daher wäre es für den obigen Fall schneller, einfach das letzte Bit zu überprüfen. Sagen wir n = 5;
Um zu überprüfen, ob die Zahl ungerade oder gerade ist, müssen wir nur das letzte Bit überprüfen. Wenn es 1 ist, ist die Zahl ungerade; ansonsten ist es eben. In der Programmierung würde es so ausgedrückt werden:
Nach meinem Verständnis wäre dies schneller als % 2 , da keine Division durchgeführt wird. Ein einfacher Bitvergleich ist erforderlich.
Ich habe dann 2 Fragen:
1) Ist der zweite Weg wirklich (in allen Fällen) wirklich schneller als der erste?
2) Wenn die Antwort für 1 ja ist, sind Compiler (in allen Sprachen) intelligent genug, um % 2 in einen einfachen Bitvergleich umzuwandeln? Oder müssen wir den zweiten Weg explizit nutzen, wenn wir die beste Leistung wollen?
Ja, ein Bit-Test ist viel schneller als eine ganzzahlige Division, um etwa einen Faktor von 10 bis 20, oder sogar 100 für 128bit / 64bit = 64bit idiv auf Intel . Esp. da x86 mindestens eine test -Anweisung hat, die Bedingungsflags basierend auf dem Ergebnis einer bitweisen UND-Verknüpfung setzt, müssen Sie also nicht teilen und dann vergleichen; Die bitweise AND ist der Vergleich.
Ich entschied mich, die Compiler-Ausgabe auf Godbolt zu überprüfen und bekam eine Überraschung:
Es stellt sich heraus, dass die Verwendung von n % 2 als vorzeichenbehafteter Integer-Wert (zB return n % 2 von einer Funktion, die signed int zurückgibt) anstatt nur für Nicht-Null ( if (n % 2) ) zu testen, manchmal langsamer Code als %Code%. Dies liegt daran, dass return n & 1 und (-1 % 2) == -1 nicht kompatibel sind. Daher kann der Compiler kein bitweises UND verwenden. Compiler vermeiden jedoch immernoch eine ganzzahlige Division und verwenden stattdessen eine clevere shift / und / add / sub-Sequenz, weil das immer noch billiger ist als eine ganzzahlige Division. (gcc und clang verwenden unterschiedliche Sequenzen.)
Wenn Sie also einen Wahrheitswert basierend auf (-1 & 1) == 1 zurückgeben möchten, ist es am besten, wenn Sie einen nicht signierten Typ verwenden. Auf diese Weise kann der Compiler sie immer auf eine einzige UND-Anweisung optimieren. (Auf godbolt können Sie zu anderen Architekturen wie ARM und PowerPC wechseln und sehen, dass die Funktion n % 2 ( unsigned even ) und die Funktion % (bitweise int even_bit ) denselben asm-Code haben.)
Die Verwendung einer & (die 0 oder 1 sein muss, nicht irgendein Wert ungleich Null) ist eine andere Option, aber der Compiler muss zusätzliche Arbeit leisten, um bool (oder einen anderen Test als% co_de zurückzugeben) %). Die bitweise - und Version davon wird 0, 1, 2 oder 3 sein, also muss der Compiler jeden Wert ungleich Null in eine 1 verwandeln. (X86 hat eine effiziente (bool) (n % 4) Anweisung, die ein Register auf 0 oder 1 setzt , abhängig von den Flags, also sind es immernoch nur 2 Instruktionen anstelle von 1. clang / gcc nutze dies, siehe n%2 in der godbolt asm Ausgabe.)
Wenn eine Optimierungsebene höher als setcc ist, optimieren gcc und clang aligned4_bool auf das, was wir erwarten. Die andere große Überraschung ist, dass icc 13 nicht . Ich verstehe nicht WTF icc denkt es macht mit all diesen Zweigen .
Die Geschwindigkeit ist äquivalent.
Die Modulo-Version funktioniert im Allgemeinen garantiert unabhängig davon, ob die Ganzzahl positiv, negativ oder Null ist, unabhängig von der implementierenden Sprache. Die bitweise Version ist nicht.
Verwenden Sie das, was Sie für am besten lesbar halten.
Tags und Links c++ performance compiler-construction compiler-optimization division