Welche Option ist besser, um eine Ganzzahl durch 2 zu teilen?

406

Welche der folgenden Techniken ist die beste Option, um eine Ganzzahl durch 2 zu teilen, und warum?

Technik 1:

x = x >> 1;

Technik 2:

x = x / 2;

Hier xist eine ganze Zahl.

Abhineet
quelle
75
Wenn Sie das Ergebnis wirklich xerneut zuweisen möchten , ist keines auf diese Weise angemessen: Es sollte entweder x >>= 1oder sein x /= 2, je nachdem, was Sie mit der Operation ausdrücken möchten . Nicht weil es schneller ist (jeder moderne Compiler kompiliert sowieso alle äquivalenten Varianten zu identischer, schneller Assemblierung), sondern weil es weniger verwirrend ist.
links um
33
Ich bin nicht einverstanden mit leftaroundabout. - Aber ich denke, es ist bemerkenswert, dass es in vielen Programmiersprachen eine Operation namens arithmetische Verschiebung gibt, die das Vorzeichenbit an Ort und Stelle hält und daher erwartungsgemäß für vorzeichenbehaftete Werte funktioniert. Die Syntax kann wie folgt sein x = x >>> 1. Beachten Sie auch, dass es je nach Plattform und Compiler durchaus sinnvoll sein kann, Divisionen und Multiplikationen mithilfe von Verschiebungen manuell zu optimieren. - Denken Sie beispielsweise an Mikrocontroller ohne direkte ALU-Unterstützung für die Multiplikation.
JimmyB
36
Ich bevorzuge, x /= 2weil es x >>= 1zu sehr nach monadischer Bindung aussieht;)
Fredoverflow
19
@leftaroundabout - Ich halte es einfach für viel lesbarer, x = x / 2statt zu schreiben x /= 2. Subjektive Präferenz vielleicht :)
JimmyB
8
@HannoBinder: sicherlich subjektiv, insbesondere viel Gewohnheit. IMO, in einer Sprache, in der alle arithmetischen Operatoren die ⬜=Kombinationen haben, sollten diese verwendet werden, wann immer es möglich ist. Es entfernt Rauschen und betont die Tatsache, dass xes geändert wird , während der allgemeine =Operator eher vorschlägt, einen völlig neuen Wert anzunehmen, der vom alten unabhängig ist. - Immer die kombinierten Akteure vermieden werden (so dass es lesbar ist so jemand, der mathematische Operatoren nur weiß) seine Stelle als auch haben, aber dann würden Sie die äußerst nützlich verzichten müssen ++, --, +=auch.
links um

Antworten:

847

Verwenden Sie die Operation, die am besten beschreibt, was Sie versuchen.

  • Wenn Sie die Zahl als eine Folge von Bits behandeln, verwenden Sie Bitshift.
  • Wenn Sie es als numerischen Wert behandeln, verwenden Sie Division.

Beachten Sie, dass sie nicht genau gleichwertig sind. Sie können für negative ganze Zahlen unterschiedliche Ergebnisse liefern. Zum Beispiel:

-5 / 2  = -2
-5 >> 1 = -3

(ideone)

Mark Byers
quelle
20
Die ursprüngliche Frage war auch vage über den Begriff "am besten". "Beste" in Bezug auf Geschwindigkeit, Lesbarkeit, Prüfungsfrage, um Schüler auszutricksen usw. Da keine Erklärung dafür vorliegt, was "am besten" bedeutet, scheint dies die richtigste Antwort zu sein.
Ray
47
In C ++ 03 sind beide Implementierungen für negative Zahlen definiert und führen möglicherweise zu denselben Ergebnissen. In C ++ 11 ist die Division für negative Zahlen gut definiert, die Verschiebung ist jedoch noch implementiert.
James Kanze
2
Während die Definition von / Implementierung ist (gilt, wenn für negative Zahlen aufgerundet oder abgerundet wird), definiert in frühen C-Standards. Es muss immer mit% übereinstimmen (Modulo / Restoperator).
Strg-Alt-Delor
7
"Implementierung definiert" bedeutet, dass der Implementierer des Compilers zwischen mehreren Implementierungsoptionen wählen muss, normalerweise mit erheblichen Einschränkungen. Hier besteht eine Einschränkung darin, dass die Operatoren %und /sowohl für positive als auch für negative Operanden konsistent sein müssen, damit (a/b)*b+(a%b)==adies unabhängig von den Vorzeichen von aund wahr ist b. Normalerweise trifft der Autor Entscheidungen, die die bestmögliche Leistung der CPU erzielen.
RBerteig
6
Jeder, der sagt "der Compiler wird es sowieso in eine Schicht konvertieren", ist falsch, oder? Sofern der Compiler nicht garantieren kann, dass es sich um eine nicht negative Ganzzahl handelt (entweder eine Konstante oder ein Int ohne Vorzeichen), kann er diese nicht in eine Verschiebung ändern
Kip
225

Sieht der erste nach Teilen aus? Nein. Wenn Sie teilen möchten, verwenden Sie x / 2. Der Compiler kann es optimieren, um wenn möglich eine Bitverschiebung zu verwenden (dies wird als Festigkeitsreduzierung bezeichnet), was es zu einer nutzlosen Mikrooptimierung macht, wenn Sie es alleine tun.

Cat Plus Plus
quelle
15
Viele Compiler werden die Division durch Zweierpotenz nicht in eine Bitverschiebung verwandeln. Das wäre eine falsche Optimierung für vorzeichenbehaftete Ganzzahlen. Sie sollten versuchen, die Assembly-Ausgabe Ihres Compilers zu überprüfen und sich selbst davon zu überzeugen.
exDM69
1
IIRC Ich habe das verwendet, um die parallele Reduktion auf CUDA zu beschleunigen (vermeiden Sie Integer Div). Dies war jedoch vor mehr als einem Jahr. Ich frage mich, wie intelligent die CUDA-Compiler heutzutage sind.
Nils
9
@ exDM69: Viele Compiler tun dies auch für vorzeichenbehaftete Ganzzahlen und passen sie einfach an die Vorzeichen an. Ein schönes Werkzeug, um mit diesen Dingen zu spielen, ist folgendes: tinyurl.com/6uww253
PlasmaHH
19
@ exDM69: Und das ist relevant, wie? Ich sagte "wenn möglich", nicht "immer". Wenn die Optimierung nicht korrekt ist, wird sie durch manuelles Ausführen nicht korrekt (wie bereits erwähnt, ist GCC intelligent genug, um den richtigen Ersatz für vorzeichenbehaftete Ganzzahlen zu finden).
Cat Plus Plus
4
Auf der WikiPedia-Seite ist dies anscheinend umstritten, aber ich würde es nicht als Kraftreduzierung bezeichnen. Eine Stärkeverringerung liegt vor, wenn Sie in einer Schleife beispielsweise von der Multiplikation zur Addition reduzieren, indem Sie zu den vorherigen Werten in der Schleife addieren. Dies ist eher eine Gucklochoptimierung, die Compiler ziemlich zuverlässig durchführen können.
SomeCallMeTim
189

Zum Anhäufen: Es gibt so viele Gründe, die Verwendung zu bevorzugen. x = x / 2; Hier einige:

  • es drückt Ihre Absicht klarer aus (vorausgesetzt, Sie haben es nicht mit Bit-Twiddling-Registerbits oder so zu tun)

  • Der Compiler reduziert dies ohnehin auf eine Shift-Operation

  • Selbst wenn der Compiler es nicht reduziert und eine langsamere Operation als die Verschiebung gewählt hat, ist die Wahrscheinlichkeit, dass dies die Leistung Ihres Programms messbar beeinflusst, selbst verschwindend gering (und wenn es messbar wirkt, haben Sie eine tatsächliche Grund für eine Schicht)

  • Wenn die Division Teil eines größeren Ausdrucks sein soll, ist es wahrscheinlicher, dass Sie die richtige Priorität haben, wenn Sie den Divisionsoperator verwenden:

    x = x / 2 + 5;
    x = x >> 1 + 5;  // not the same as above
  • Vorzeichenbehaftete Arithmetik kann die Dinge noch komplizierter machen als das oben erwähnte Vorrangproblem

  • um es noch einmal zu wiederholen - der Compiler wird dies ohnehin schon für Sie tun. Tatsächlich wandelt es die Division durch eine Konstante in eine Reihe von Verschiebungen, Additionen und Multiplikationen für alle Arten von Zahlen um, nicht nur für Zweierpotenzen. In dieser Frage finden Sie Links zu weiteren Informationen dazu.

Kurz gesagt, Sie kaufen nichts, indem Sie eine Verschiebung codieren, wenn Sie wirklich multiplizieren oder dividieren möchten, außer vielleicht einer erhöhten Wahrscheinlichkeit, einen Fehler einzuführen. Es ist ein Leben lang her, dass Compiler nicht klug genug waren, um solche Dinge gegebenenfalls auf eine Verschiebung zu optimieren.

Michael Burr
quelle
5
Es ist auch erwähnenswert, dass es zwar Vorrangregeln gibt, die Verwendung von Klammern jedoch nichts Falsches ist. Während ich einen Produktionscode überarbeitete, sah ich tatsächlich etwas von der Form a/b/c*d(wo a..dnumerische Variablen bezeichnet wurden) anstelle der weitaus besser lesbaren (a*d)/(b*c).
1
Die Leistung und Optimierungen hängen vom Compiler und vom Ziel ab. Zum Beispiel arbeite ich für einen Mikrocontroller, bei dem alles, was höher als -O0 ist, deaktiviert ist, es sei denn, Sie kaufen den kommerziellen Compiler, sodass der Compiler die Teilung definitiv nicht in Bitverschiebungen umwandelt. Darüber hinaus dauern Bitverschiebungen einen Zyklus und das Teilen 18 Zyklen für dieses Ziel. Da die Taktrate des Mikrocontrollers ziemlich niedrig ist, kann dies tatsächlich ein spürbarer Leistungseinbruch sein (dies hängt jedoch von Ihrem Code ab - Sie sollten auf jeden Fall / verwenden, bis die Profilerstellung es Ihnen sagt Es ist ein Problem!)
4
@ JackManey, wenn es eine Möglichkeit gibt a*doder b*ceinen Überlauf erzeugen würde, ist die weniger lesbare Form nicht gleichwertig und hat einen offensichtlichen Vorteil. PS Ich stimme zu, dass Klammern dein bester Freund sind.
Mark Ransom
@MarkRansom - Ein fairer Punkt (obwohl ich auf a/b/c*dR-Code gestoßen bin - in einem Kontext, in dem ein Überlauf bedeuten würde, dass etwas ernsthaft mit den Daten nicht stimmt - und nicht beispielsweise in einem leistungskritischen Block von C-Code).
Der Code x=x/2;ist nur "klarer" als x>>=1wenn xes niemals eine ungerade negative Zahl sein wird oder man sich nicht um einzelne Fehler kümmert. Ansonsten x=x/2;und x>>=1;haben unterschiedliche Bedeutungen. Wenn man den von berechneten Wert benötigt x>>=1, würde ich dies als klarer als x = (x & ~1)/2oder x = (x < 0) ? (x-1)/2 : x/2oder jede andere Formulierung betrachten, die ich mir vorstellen kann, die Division durch zwei zu verwenden. Ebenso, wenn man den von berechneten Wert benötigt x/=2, ist das klarer als ((x + ((unsigned)x>>31)>>1).
Supercat
62

Welches ist die beste Option und warum zum Teilen der Ganzzahl durch 2?

Kommt darauf an, was du am besten meinst .

Wenn Sie möchten, dass Ihre Kollegen Sie hassen oder Ihren Code schwer lesbar machen, würde ich definitiv die erste Option wählen.

Wenn Sie eine Zahl durch 2 teilen möchten, wählen Sie die zweite.

Die beiden sind nicht äquivalent, sie verhalten sich nicht gleich, wenn die Zahl negativ ist oder sich in größeren Ausdrücken befindet - Bitshift hat eine niedrigere Priorität als +oder -, Division hat eine höhere Priorität.

Sie sollten Ihren Code schreiben, um seine Absicht auszudrücken. Machen Sie sich keine Sorgen, wenn die Leistung Ihr Anliegen ist. Der Optimierer leistet bei solchen Mikrooptimierungen gute Arbeit.

Luchian Grigore
quelle
58

Verwenden Sie einfach dividieren ( /), vorausgesetzt, es ist klarer. Der Compiler wird entsprechend optimieren.

Justin
quelle
34
Der Compiler sollte entsprechend optimieren.
Noctis Skytower
12
Wenn der Compiler nicht entsprechend optimiert, sollten Sie einen besseren Compiler verwenden.
David Stone
3
@DavidStone: Auf welchen Prozessoren kann ein Compiler die Division einer möglicherweise negativ vorzeichenbehafteten Ganzzahl durch eine andere Konstante als 1 optimieren, um so effizient wie eine Verschiebung zu sein?
Supercat
1
@ Supercat: Das ist ein guter Punkt. Sie können den Wert natürlich in einer vorzeichenlosen Ganzzahl speichern (die meiner Meinung nach einen viel schlechteren Ruf hat als sie sollte, wenn sie mit vorzeichenlosen / vorzeichenlosen Nichtübereinstimmungswarnungen kombiniert werden), und die meisten Compiler haben auch die Möglichkeit, ihnen bei der Optimierung mitzuteilen, dass etwas wahr ist . Ich würde es vorziehen, das in ein Kompatibilitätsmakro zu packen und so etwas wie ASSUME(x >= 0); x /= 2;over zu haben x >>= 1;, aber das ist immer noch ein wichtiger Punkt, den ich ansprechen muss.
David Stone
39

Ich stimme anderen Antworten zu, die Sie bevorzugen sollten, x / 2da ihre Absicht klarer ist und der Compiler sie für Sie optimieren sollte.

Aber ein weiterer Grund für die Bevorzugung x / 2über x >> 1ist , dass das Verhalten der >>Implementierung abhängig ist , wenn xein signiertes ist intund negativ ist .

Aus Abschnitt 6.5.7, Punkt 5 der ISO C99-Norm:

Das Ergebnis E1 >> E2sind nach E1rechts verschobene E2Bitpositionen. Wenn E1ein vorzeichenloser Typ oder E1ein vorzeichenbehafteter Typ und ein nicht negativer Wert vorhanden sind, ist der Wert des Ergebnisses der integrale Bestandteil des Quotienten von E1/ 2 E2. Wenn E1ein vorzeichenbehafteter Typ und ein negativer Wert vorhanden sind, ist der resultierende Wert implementierungsdefiniert.

Jamesdlin
quelle
3
Es ist anzumerken, dass das Verhalten, das viele Implementierungen für x>>scalepowernegative Zahlen definieren , genau das ist, was erforderlich ist, wenn ein Wert durch eine Zweierpotenz für Zwecke wie das Rendern von Bildschirmen geteilt wird, während die Verwendung x/scalefactorfalsch ist, es sei denn, man korrigiert negative Werte.
Supercat
32

x / 2ist klarer und x >> 1nicht viel schneller (laut einem Mikro-Benchmark etwa 30% schneller für eine Java-JVM). Wie andere angemerkt haben, unterscheidet sich die Rundung bei negativen Zahlen geringfügig. Sie müssen dies berücksichtigen, wenn Sie negative Zahlen verarbeiten möchten. Einige Compiler konvertieren möglicherweise automatisch in x / 2, x >> 1wenn sie wissen, dass die Zahl nicht negativ sein kann (obwohl ich dachte, ich könnte dies nicht überprüfen).

Auch x / 2kann der (langsame) Teilungs-CPU-Befehl nicht verwendet werden, da einige Verknüpfungen möglich sind , aber er ist immer noch langsamer als x >> 1.

(Dies ist ein C / C ++ Frage, andere Programmiersprachen mehr Operatoren haben. Für Java gibt es auch die unsigned Verschiebung nach rechts, x >>> 1, was wiederum anders ist. Es ermöglicht richtig den Mittelwert (Durchschnitt) Wert von zwei Werten zu berechnen, so dass (a + b) >>> 1Wille Geben Sie den Mittelwert auch für sehr große Werte von aund zurück b. Dies ist beispielsweise für die binäre Suche erforderlich, wenn die Array-Indizes sehr groß werden können. In vielen Versionen der binären Suche ist ein Fehler(a + b) / 2 aufgetreten , da sie zur Berechnung des Durchschnitts verwendet wurden funktioniert nicht richtig. Die richtige Lösung ist (a + b) >>> 1stattdessen zu verwenden .)

Thomas Müller
quelle
1
Compiler kann nicht konvertieren , x/2um x>>1in Fällen , in denen xnegativ sein kann. Wenn man den x>>1zu berechnenden Wert haben möchte, ist dies mit ziemlicher Sicherheit schneller als jeder Ausdruck, bei x/2dem derselbe Wert berechnet wird.
Supercat
Du hast recht. Ein Compiler darf nur dann konvertieren x/2, x>>1wenn er weiß, dass der Wert nicht negativ ist. Ich werde versuchen, meine Antwort zu aktualisieren.
Thomas Mueller
Compiler vermeiden jedoch immer noch einen divBefehl, indem sie x/2in konvertieren (x + (x<0?1:0)) >> 1(wobei >> eine arithmetische Rechtsverschiebung ist, die sich in Vorzeichenbits verschiebt). Dies erfordert 4 Anweisungen: Kopieren Sie den Wert, shr (um nur das Vorzeichenbit in einer Registrierung zu erhalten), add, sar. goo.gl/4F8Ms4
Peter Cordes
Die Frage ist mit C und C ++ gekennzeichnet.
Josh Sanford
22

Knuth sagte:

Vorzeitige Optimierung ist die Wurzel allen Übels.

Also schlage ich vor zu verwenden x /= 2;

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

Ivan Californias
quelle
4
Was würden Sie als bevorzugte Methode betrachten, um eine Zahl um eine Zweierpotenz zu verkleinern, wenn man möchte, dass ganze Zahlen das Axiom (das für natürliche Zahlen und reelle Zahlen gilt) einhalten, das (n + d) / d = (n / d) + ist 1? Verstöße, die beim Skalieren von Grafiken auftreten, führen zu sichtbaren "Nähten" im Ergebnis. Wenn man etwas will, das einheitlich und fast symmetrisch um Null ist, (n+8)>>4funktioniert es gut. Können Sie einen Ansatz anbieten, der so klar oder effizient ist, ohne eine signierte Rechtsverschiebung zu verwenden?
Supercat
19

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

Siehe auch Compiler-Ausgaben online bei godbolt .

Was Sie sehen, ist, dass der Compiler sarlin beiden Fällen eine Anweisung (arithmetische Rechtsverschiebung) verwendet, sodass er die Ähnlichkeit zwischen den beiden Ausdrücken erkennt. Wenn Sie die Division verwenden, muss der Compiler auch negative Zahlen anpassen. Dazu wird das Vorzeichenbit auf das Bit niedrigster Ordnung verschoben und dem Ergebnis hinzugefügt. Dies behebt das Off-by-One-Problem beim Verschieben negativer Zahlen im Vergleich zu einer Teilung.
Da der Divisionsfall zwei Verschiebungen ausführt, während der explizite Verschiebungsfall nur eine Schicht ausführt, können wir hier einige der Leistungsunterschiede erklären, die durch andere Antworten hier gemessen werden.

C-Code mit Baugruppenausgabe:

Für die Teilung wäre Ihre Eingabe

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

und das kompiliert zu

    movl    %edi, %eax
    shrl    $31, %eax
    addl    %edi, %eax
    sarl    %eax
    ret

ähnlich für die Schicht

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

mit Ausgabe:

    sarl    %edi
    movl    %edi, %eax
    ret
Michael Donohue
quelle
Je nachdem , was man tut, kann sie den Off-by-one Fehler beheben, oder es kann dazu führen , ein Off-by-one Fehler ( im Vergleich mit dem, was tatsächlich benötigt wird ) , die den Einsatz weiterer Code erforderlich machen , es zu beheben. Wenn man ein bodenständiges Ergebnis will, ist eine Rechtsverschiebung schneller und einfacher als jede mir bekannte Alternative.
Supercat
Wenn Sie eine Etage benötigen, ist es unwahrscheinlich, dass Sie das, was Sie wollen, als "Teilen durch 2" beschreiben
Michael Donohue
Die Division sowohl natürlicher als auch reeller Zahlen bestätigt das Axiom (n + d) / d = (n / d) +1. Die Division reeller Zahlen hält auch (-n) / d = - (n / d) aufrecht, ein Axiom, das bei natürlichen Zahlen bedeutungslos ist. Es ist nicht möglich, einen Divisionsoperator zu haben, der für ganze Zahlen geschlossen ist und beide Axiome unterstützt. Meiner Meinung nach erscheint es natürlicher zu sagen, dass das erste Axiom für alle Zahlen und das zweite nur für Real gelten sollte, als zu sagen, dass das erste für ganze Zahlen oder Real gelten sollte, aber nicht für ganze Zahlen. Außerdem bin ich gespannt, in welchen Fällen das zweite Axiom tatsächlich nützlich ist .
Supercat
1
Eine Ganzzahldivisionsmethode, die das erste Axiom erfüllt, unterteilt die Zahlenlinie in Größenbereiche d. Eine solche Partitionierung ist für viele Zwecke nützlich. Selbst wenn der Haltepunkt lieber an einer anderen Stelle als zwischen 0 und -1 liegen soll, wird er durch Hinzufügen eines Versatzes verschoben. Eine ganzzahlige Division, die das zweite Axiom erfüllt, unterteilt die Zahlenlinie in Bereiche, die größtenteils von Größe sind d, von denen jedoch einer von Größe ist 2*d-1. Nicht gerade "gleiche" Abteilungen. Können Sie Vorschläge machen, wann die Oddball-Partition tatsächlich nützlich ist?
Supercat
Ihre Compiler-Ausgabe für shr2signed ist falsch. gcc auf x86 implementiert >> von vorzeichenbehafteten Ganzzahlen mit arithmetischen Verschiebungen ( sar). goo.gl/KRgIkb . Dieser Mailinglistenbeitrag ( gcc.gnu.org/ml/gcc/2000-04/msg00152.html ) bestätigt, dass gcc in der Vergangenheit arithmetische Verschiebungen für vorzeichenbehaftete Ints verwendet. Daher ist es sehr unwahrscheinlich, dass FreeBSD gcc 4.2.1 eine vorzeichenlose Verschiebung verwendet. Ich habe Ihren Beitrag aktualisiert, um das zu beheben, und der frühe Absatz besagt, dass beide shr verwendet haben, wenn es tatsächlich SAR ist, die beide verwenden. Mit dem SHR wird das Vorzeichenbit für den /Fall extrahiert . Enthält auch einen Godbolt-Link.
Peter Cordes
15

Nur eine zusätzliche Anmerkung -

x * = 0,5 ist in einigen VM-basierten Sprachen häufig schneller - insbesondere in Actionscript, da die Variable nicht auf Division durch 0 überprüft werden muss.

ansiart
quelle
2
@minitech: Das ist so ein schlechter Test. Der gesamte Code im Test ist konstant. Bevor der Code überhaupt JITed ist, werden alle Konstanten entfernt.
@ M28: Ich war mir ziemlich sicher, dass die Interna von jsPerf (dh eval) dies jedes Mal neu gemacht haben. Egal, ja, es ist ein ziemlich schlechter Test, weil es eine sehr dumme Optimierung ist.
Ry-
13

Verwenden Sie x = x / 2; OR, x /= 2;da möglicherweise in Zukunft ein neuer Programmierer daran arbeitet. So wird es für ihn einfacher sein herauszufinden, was in der Codezeile vor sich geht. Solche Optimierungen sind möglicherweise nicht jedem bekannt.

Imdad
quelle
12

Ich erzähle zum Zweck der Programmierung von Wettbewerben. Im Allgemeinen haben sie sehr große Eingaben, bei denen die Division durch 2 viele Male stattfindet und bekannt ist, dass die Eingabe positiv oder negativ ist.

x >> 1 ist besser als x / 2. Ich habe auf ideone.com nachgesehen, indem ich ein Programm ausgeführt habe, in dem mehr als 10 ^ 10 Division durch 2 Operationen stattgefunden haben. x / 2 dauerte fast 5,5 Sekunden, während x >> 1 für dasselbe Programm fast 2,6 Sekunden dauerte.

Shashwat Kumar
quelle
1
Für Werte ohne Vorzeichen sollte ein Compiler optimieren x/2zu x>>1. Für signierte Werte, fast alle Implementierungen definieren x>>1eine Bedeutung haben , die zu äquivalent ist x/2, kann aber schneller berechnet werden , wenn xpositiv, und ist sinnvollerweise anders x/2als xnegativ ist.
Supercat
12

Ich würde sagen, es gibt mehrere Dinge zu beachten.

  1. Bitshift sollte schneller sein, da keine spezielle Berechnung erforderlich ist, um die Bits zu verschieben. Wie bereits erwähnt, gibt es jedoch potenzielle Probleme mit negativen Zahlen. Wenn Sie sicher sind, positive Zahlen zu haben und Geschwindigkeit suchen, würde ich Bitshift empfehlen.

  2. Der Divisionsoperator ist für Menschen sehr leicht zu lesen. Wenn Sie also nach Lesbarkeit von Code suchen, können Sie diese verwenden. Beachten Sie, dass der Bereich der Compileroptimierung einen langen Weg zurückgelegt hat. Daher ist es empfehlenswert, Code leicht lesbar und verständlich zu machen.

  3. Abhängig von der zugrunde liegenden Hardware können Vorgänge unterschiedliche Geschwindigkeiten haben. Amdals Gesetz ist es, den allgemeinen Fall schnell zu machen. Möglicherweise verfügen Sie über Hardware, die andere Vorgänge schneller als andere ausführen kann. Zum Beispiel kann das Multiplizieren mit 0,5 schneller sein als das Teilen durch 2. (Zugegeben, Sie müssen möglicherweise das Wort der Multiplikation ergreifen, wenn Sie die Ganzzahldivision erzwingen möchten).

Wenn Sie nach reiner Leistung suchen, würde ich empfehlen, einige Tests zu erstellen, die die Operationen millionenfach ausführen können. Probieren Sie die Ausführung mehrmals aus (Ihre Stichprobengröße), um festzustellen, welche statistisch am besten zu Ihrem Betriebssystem / Ihrer Hardware / Ihrem Compiler / Ihrem Code passt.

James Oravec
quelle
2
"Bitshift sollte schneller sein". Compiler werden die Unterteilung in Bitshifts optimieren
Trevor Hickey
Ich hoffe, sie würden, aber wenn Sie nicht Zugriff auf die Quelle des Compilers haben, können Sie nicht sicher sein :)
James Oravec
1
Ich würde Bitshift auch empfehlen, wenn die Implementierung auf die gängigste Weise damit umgeht und die Art und Weise, wie mit negativen Zahlen umgegangen werden soll, mit dem übereinstimmt, was >>funktioniert und was /nicht.
Supercat
12

In Bezug auf die CPU sind Bitverschiebungsoperationen schneller als Divisionsoperationen. Der Compiler weiß dies jedoch und optimiert es so weit wie möglich entsprechend, sodass Sie so codieren können, wie es am sinnvollsten ist, und sich darauf verlassen können, dass Ihr Code effizient ausgeführt wird. Denken Sie jedoch daran, dass eine unsigned intDose (in einigen Fällen) intaus zuvor genannten Gründen besser optimiert werden kann als eine . Wenn Sie keine vorzeichenbehaftete Arithmetik benötigen, geben Sie das Vorzeichenbit nicht an.

tylerl
quelle
11

x = x / 2; ist der geeignete Code für die Verwendung. Eine Operation hängt jedoch von Ihrem eigenen Programm ab, wie die Ausgabe erzeugt werden soll.

Gooner
quelle
11

Machen Sie Ihre Absichten klarer ... Wenn Sie beispielsweise teilen möchten, verwenden Sie x / 2 und lassen Sie den Compiler es optimieren, um den Operator (oder etwas anderes) zu verschieben.

Die heutigen Prozessoren lassen diese Optimierungen keinen Einfluss auf die Leistung Ihrer Programme haben.

Atul Kumar
quelle
10

Die Antwort darauf hängt von der Umgebung ab, in der Sie arbeiten.

  • Wenn Sie an einem 8-Bit-Mikrocontroller oder etwas anderem ohne Hardware-Unterstützung für die Multiplikation arbeiten, wird eine Bitverschiebung erwartet und ist alltäglich. Während sich der Compiler mit ziemlicher Sicherheit x /= 2in x >>= 1eine solche verwandelt , zieht das Vorhandensein eines Teilungssymbols in dieser Umgebung mehr Augenbrauen hoch als Verwenden einer Verschiebung, um eine Teilung zu bewirken.
  • Wenn Sie in einer leistungskritischen Umgebung oder einem Codeabschnitt arbeiten oder Ihr Code bei deaktivierter Compileroptimierung kompiliert werden könnte, x >>= 1 ein Kommentar, der die Argumentation erläutert, wahrscheinlich nur aus Gründen der Klarheit des Zwecks am besten.
  • Wenn Sie sich nicht unter einer der oben genannten Bedingungen befinden, machen Sie Ihren Code durch einfaches Verwenden besser lesbar x /= 2. Es ist besser, dem nächsten Programmierer, der sich Ihren Code ansieht, die 10-Sekunden-Doppelaufnahme Ihres Schichtbetriebs zu ersparen, als unnötig zu beweisen, dass Sie wussten, dass die Schicht ohne Compiler-Optimierung effizienter ist.

Alle diese nehmen vorzeichenlose ganze Zahlen an. Die einfache Verschiebung ist wahrscheinlich nicht das, was Sie für signiert wollen. DanielH spricht auch einen guten Punkt zur Verwendung x *= 0.5für bestimmte Sprachen wie ActionScript an.

gkimsey
quelle
8

Mod 2, Test für = 1. Keine Ahnung die Syntax in c. aber das kann am schnellsten sein.

circusdei
quelle
7

Im Allgemeinen teilt sich die richtige Verschiebung:

q = i >> n; is the same as: q = i / 2**n;

Dies wird manchmal verwendet, um Programme auf Kosten der Klarheit zu beschleunigen. Ich denke nicht, dass du es tun solltest. Der Compiler ist intelligent genug, um die Beschleunigung automatisch durchzuführen. Dies bedeutet, dass Sie durch das Einsetzen einer Schicht nichts auf Kosten der Klarheit gewinnen .

Schauen Sie sich diese Seite aus der praktischen C ++ - Programmierung an.

Mouna Cheikhna
quelle
Wenn man den Wert berechnen möchte, der z. B. (x+128)>>8für Werte berechnet wird, die xnicht nahe am Maximum liegen, wie kann man dies ohne Verschiebung präzise tun? Beachten Sie, dass dies (x+128)/256nicht funktioniert. Kennen Sie einen schönen Ausdruck, der wird?
Supercat
7

Wenn Sie Ihren Code für den nächsten Mann schreiben, der ihn liest, achten Sie natürlich auf die Klarheit von "x / 2".

Wenn jedoch Geschwindigkeit Ihr Ziel ist, versuchen Sie es in beide Richtungen und messen Sie die Ergebnisse.Vor ein paar Monaten habe ich an einer Bitmap-Faltungsroutine gearbeitet, bei der ein Array von ganzen Zahlen durchlaufen und jedes Element durch 2 geteilt wurde. Ich habe alle möglichen Dinge getan, um es zu optimieren, einschließlich des alten Tricks, "x >> 1" durch "x" zu ersetzen / 2 ".

Als ich tatsächlich beide Wege zeitlich festlegte, stellte ich zu meiner Überraschung fest, dass x / 2 schneller als x >> 1 war

Hierbei wurde Microsoft VS2008 C ++ mit aktivierten Standardoptimierungen verwendet.

Chris Bennet
quelle
4

In Bezug auf die Leistung. Die Schaltvorgänge der CPU sind erheblich schneller als das Teilen von Op-Codes. Teilen durch zwei oder Multiplizieren mit 2 usw. profitieren also alle von Schichtoperationen.

In Bezug auf das Erscheinungsbild. Als Ingenieure haben wir uns so sehr für Kosmetik interessiert, dass selbst schöne Damen sie nicht benutzen! :) :)

Farjad
quelle
3

X / Y ist ein korrekter ... und ">>" Verschiebungsoperator. Wenn wir zwei eine ganze Zahl teilen wollen, können wir den (/) Dividendenoperator verwenden. Der Shift-Operator wird verwendet, um die Bits zu verschieben.

x = x / 2; x / = 2; wir können so verwenden ..

Schokoladenjunge
quelle
0

Während x >> 1 schneller als x / 2 ist, ist die richtige Verwendung von >> beim Umgang mit negativen Werten etwas komplizierter. Es erfordert etwas Ähnliches wie das Folgende:

// Extension Method
public static class Global {
    public static int ShiftDivBy2(this int x) {
        return (x < 0 ? x + 1 : x) >> 1;
    }
}
Darin
quelle