Welche Option ist besser geeignet, um eine ganze Zahl durch 2 zu dividieren?

Question

Welche der folgenden Techniken ist die beste Möglichkeit, eine ganze Zahl durch 2 zu teilen, und warum?

Technik 1:

x = x >> 1;

Technik 2:

x = x / 2;

Hier x ist eine ganze Zahl.

Answer 1

Ich stimme mit anderen Antworten überein, dass Sie Folgendes bevorzugen sollten x / 2 weil seine Absicht klarer ist und der Compiler ihn für Sie optimieren sollte.

Ein weiterer Grund für die Bevorzugung von x / 2 über x >> 1 ist, dass das Verhalten der >> ist abhängig von der Implementierung, wenn x ist eine vorzeichenbehaftete int und ist negativ.

Aus Abschnitt 6.5.7, Aufzählungspunkt 5 der ISO C99-Norm:

Das Ergebnis von E1 >> E2 est E1 rechts verschoben E2 Bit-Positionen. Wenn E1 h einen Typ ohne Vorzeichen hat oder wenn E1 h der Wert des Ergebnisses ist der ganzzahlige Teil des Quotienten aus E1 / 2 E2 . Wenn E1 einen vorzeichenbehafteten Typ und einen negativen Wert hat, ist der resultierende Wert ist implementierungsabhängig.

Answer 2

x / 2 ist klarer, und x >> 1 ist nicht viel schneller (laut einem Micro-Benchmark etwa 30 % schneller für eine Java JVM). Wie bereits von anderen erwähnt, ist die Rundung bei negativen Zahlen etwas anders, so dass Sie dies berücksichtigen müssen, wenn Sie negative Zahlen verarbeiten wollen. Einige Compiler können automatisch konvertieren x / 2 à x >> 1 wenn sie wissen, dass die Zahl nicht negativ sein kann (auch wenn ich dies nicht nachprüfen konnte).

Sogar x / 2 den (langsamen) Divisions-CPU-Befehl nicht verwenden darf, weil einige Abkürzungen sind möglich aber es ist immer noch langsamer als x >> 1 .

(Dies ist eine C / C++ Frage, andere Programmiersprachen haben mehr Operatoren. Für Java gibt es auch die vorzeichenlose Rechtsverschiebung, x >>> 1 , was wiederum anders ist. Sie ermöglicht die korrekte Berechnung des Mittelwerts (Durchschnittswerts) von zwei Werten, so dass (a + b) >>> 1 gibt den Mittelwert auch bei sehr großen Werten von a et b . Dies ist zum Beispiel für die binäre Suche erforderlich, wenn die Array-Indizes sehr groß werden können. Es gab ein Fehler in vielen Versionen der Binärsuche denn sie verwendeten (a + b) / 2 um den Durchschnitt zu berechnen. Dies funktioniert nicht korrekt. Die richtige Lösung ist die Verwendung von (a + b) >>> 1 stattdessen).

Answer 3

Sagte Knuth:

Vorzeitige Optimierung ist die Wurzel allen Übels.

Daher schlage ich vor, Folgendes zu verwenden x /= 2;

Auf diese Weise ist der Code einfach zu verstehen und ich denke auch, dass die Optimierung dieser Operation in dieser Form keinen großen Unterschied für den Prozessor bedeutet.

Answer 4

Schauen Sie sich die Compiler-Ausgabe an, um eine Entscheidung zu treffen. Ich habe diesen Test auf x86-64 mit
gcc (GCC) 4.2.1 20070719 [FreeBSD]

Siehe auch Compiler-Ausgaben online bei Godbolt .

Was Sie sehen, ist, dass der Compiler eine sarl (arithmetische Rechtsverschiebung) in beiden Fällen, so dass die Ähnlichkeit zwischen den beiden Ausdrücken erkannt wird. Wenn Sie die Divisionsanweisung verwenden, muss der Compiler auch negative Zahlen berücksichtigen. Dazu verschiebt er das Vorzeichenbit auf das Bit niedrigster Ordnung und addiert es zum Ergebnis. Auf diese Weise wird das Problem der Verschiebung negativer Zahlen um eins behoben, verglichen mit dem, was ein Divide tun würde.
Da der Divide-Fall zwei Verschiebungen vornimmt, während der explizite Shift-Fall nur eine vornimmt, können wir nun einige der Leistungsunterschiede erklären, die durch andere Antworten gemessen wurden.

C-Code mit Assembler-Ausgabe:

Bei einer Teilung würde Ihre Eingabe lauten

int div2signed(int a) {
  return a / 2;
}

und dies kompiliert zu

    movl    %edi, %eax
    shrl    $31, %eax            # (unsigned)x >> 31
    addl    %edi, %eax           # tmp = x + (x<0)
    sarl    %eax                 # (x + 0 or 1) >> 1  arithmetic right shift
    ret

ähnlich für Schicht

int shr2signed(int a) {
  return a >> 1;
}

mit Ausgang:

    sarl    %edi
    movl    %edi, %eax
    ret

Andere ISAs können dies ebenso effizient tun, wenn nicht sogar noch effizienter. Zum Beispiel verwendet GCC für AArch64:

        add     w0, w0, w0, lsr 31      // x += (unsigned)x>>31
        asr     w0, w0, 1               // x >>= 1
        ret

Answer 5

Nur eine zusätzliche Anmerkung -

x *= 0,5 ist in einigen VM-basierten Sprachen oft schneller - vor allem in Actionscript, da die Variable nicht auf Teilung durch 0 geprüft werden muss.