Transformieren die meisten Compiler% 2 in einen Bitvergleich? Ist es wirklich schneller?

Question

Bei der Programmierung muss oft geprüft werden, ob eine Zahl gerade oder ungerade ist. Dafür verwenden wir in der Regel:

n % 2 == 0 

aber mein Verständnis ist, dass der '%' Operator führt tatsächlich eine Division und gibt seinen Rest; Daher wäre es für den obigen Fall schneller, einfach das letzte Bit zu überprüfen. Lassen Sie uns sagen n = 5;

5 = 00000101 

Um zu überprüfen, ob die Zahl gerade oder ungerade ist, brauchen wir nur das letzte Stück zu überprüfen. Wenn es 1 ist, ist die Nummer ungerade; ansonsten ist es eben.

n & 1 == 0 

In meinem Verständnis wäre dies schneller als % 2 wie keine Trennung durchgeführt wird: in der Programmierung, würde es so ausdrücken. Ein einfacher Bitvergleich ist erforderlich.

Ich habe 2 Fragen dann:

1) schneller Der zweite Weg ist wirklich als die erste (in allen Fällen)?

2) Wenn die Antwort für 1 ja ist, sind Compiler (in allen Sprachen) intelligent genug, % 2 in einen einfachen Bit-Vergleich zu konvertieren? Oder müssen wir den zweiten Weg explizit nutzen, wenn wir die beste Leistung wollen?

Answer 1

Ja, ein Bit-Test ist viel schneller als ganzzahlige Division, by about a factor of 10 to 20, or even 100 for 128bit/64bit = 64bit idiv on Intel. Esp. da x86 mindestens eine test-Anweisung hat, die Bedingungsflags basierend auf dem Ergebnis einer bitweisen UND-Verknüpfung setzt, so dass Sie nicht teilen müssen und dann vergleichen; die bitweise ANDist der Vergleich.

entschied ich mich tatsächlich check the compiler output on Godbolt, und bekam eine Überraschung:

Es stellt sich heraus, dass n % 2 als 'Signed Integer-Wert (zB ein return n % 2 aus einer Funktion, die signed int zurück), anstatt nur zu testen es für Nicht-Null (if (n % 2)) erzeugt manchmal langsameren Code als return n & 1. Dies liegt daran, (-1 % 2) == -1, während (-1 & 1) == 1, so kann der Compiler nicht ein 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 n % 2 zurückgeben möchten, ist es am besten, wenn Sie einen unsignierten 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 unsigned even (%) Funktion und die int even_bit (bitweise &) Funktion den gleichen asm Code haben.

)

Mit einem bool (der 0 oder 1 sein muss, nicht nur irgendein Nicht-Null-Wert) ist eine weitere Option, aber der Compiler muss zusätzliche Arbeit tun zurückzukehren (bool) (n % 4) (oder einen Test anders als n%2). Die bitweise - und Version davon wird 0, 1, 2 oder 3 sein, also muss der Compiler jeden Wert ungleich Null in eine 1 umwandeln. (X86 hat eine effiziente setcc Anweisung, die ein Register auf 0 oder 1 setzt, abhängig auf die Fahnen, so es immer noch nur zwei Anweisungen anstelle von 1. Klirren/gcc Verwendung dieses finden aligned4_bool im Godbolt asm-Ausgang.)

Mit jeder Optimierungsstufe höher als -O0, gcc und Klirren optimieren if (n%2) zu dem, was wir erwarten . Die andere große Überraschung ist, dass icc 13 nicht. Ich verstehe nicht WTF icc thinks it's doing with all those branches.

Answer 2

Die Geschwindigkeit ist äquivalent.

Die Modulo-Version funktioniert in der Regel unabhängig davon, ob die Ganzzahl positiv, negativ oder Null ist, unabhängig von der implementierten Sprache. Die bitweise Version ist nicht.

Verwenden Sie das, was Sie am besten lesen können.