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 x
ist eine ganze Zahl.
c++
c
optimization
division
micro-optimization
Abhineet
quelle
quelle
x
erneut zuweisen möchten , ist keines auf diese Weise angemessen: Es sollte entwederx >>= 1
oder seinx /= 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.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.x /= 2
weil esx >>= 1
zu sehr nach monadischer Bindung aussieht;)x = x / 2
statt zu schreibenx /= 2
. Subjektive Präferenz vielleicht :)⬜=
Kombinationen haben, sollten diese verwendet werden, wann immer es möglich ist. Es entfernt Rauschen und betont die Tatsache, dassx
es 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.Antworten:
Verwenden Sie die Operation, die am besten beschreibt, was Sie versuchen.
Beachten Sie, dass sie nicht genau gleichwertig sind. Sie können für negative ganze Zahlen unterschiedliche Ergebnisse liefern. Zum Beispiel:
(ideone)
quelle
%
und/
sowohl für positive als auch für negative Operanden konsistent sein müssen, damit(a/b)*b+(a%b)==a
dies unabhängig von den Vorzeichen vona
und wahr istb
. Normalerweise trifft der Autor Entscheidungen, die die bestmögliche Leistung der CPU erzielen.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.quelle
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:
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.
quelle
a/b/c*d
(woa..d
numerische Variablen bezeichnet wurden) anstelle der weitaus besser lesbaren(a*d)/(b*c)
.a*d
oderb*c
einen Ü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.a/b/c*d
R-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).x=x/2;
ist nur "klarer" alsx>>=1
wennx
es niemals eine ungerade negative Zahl sein wird oder man sich nicht um einzelne Fehler kümmert. Ansonstenx=x/2;
undx>>=1;
haben unterschiedliche Bedeutungen. Wenn man den von berechneten Wert benötigtx>>=1
, würde ich dies als klarer alsx = (x & ~1)/2
oderx = (x < 0) ? (x-1)/2 : x/2
oder jede andere Formulierung betrachten, die ich mir vorstellen kann, die Division durch zwei zu verwenden. Ebenso, wenn man den von berechneten Wert benötigtx/=2
, ist das klarer als((x + ((unsigned)x>>31)>>1)
.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.
quelle
Verwenden Sie einfach dividieren (
/
), vorausgesetzt, es ist klarer. Der Compiler wird entsprechend optimieren.quelle
ASSUME(x >= 0); x /= 2;
over zu habenx >>= 1;
, aber das ist immer noch ein wichtiger Punkt, den ich ansprechen muss.Ich stimme anderen Antworten zu, die Sie bevorzugen sollten,
x / 2
da ihre Absicht klarer ist und der Compiler sie für Sie optimieren sollte.Aber ein weiterer Grund für die Bevorzugung
x / 2
überx >> 1
ist , dass das Verhalten der>>
Implementierung abhängig ist , wennx
ein signiertes istint
und negativ ist .Aus Abschnitt 6.5.7, Punkt 5 der ISO C99-Norm:
quelle
x>>scalepower
negative 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 Verwendungx/scalefactor
falsch ist, es sei denn, man korrigiert negative Werte.x / 2
ist klarer undx >> 1
nicht 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 inx / 2
,x >> 1
wenn sie wissen, dass die Zahl nicht negativ sein kann (obwohl ich dachte, ich könnte dies nicht überprüfen).Auch
x / 2
kann der (langsame) Teilungs-CPU-Befehl nicht verwendet werden, da einige Verknüpfungen möglich sind , aber er ist immer noch langsamer alsx >> 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) >>> 1
Wille Geben Sie den Mittelwert auch für sehr große Werte vona
und zurückb
. 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) >>> 1
stattdessen zu verwenden .)quelle
x/2
umx>>1
in Fällen , in denenx
negativ sein kann. Wenn man denx>>1
zu berechnenden Wert haben möchte, ist dies mit ziemlicher Sicherheit schneller als jeder Ausdruck, beix/2
dem derselbe Wert berechnet wird.x/2
,x>>1
wenn er weiß, dass der Wert nicht negativ ist. Ich werde versuchen, meine Antwort zu aktualisieren.div
Befehl, indem siex/2
in 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/4F8Ms4Knuth sagte:
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.
quelle
(n+8)>>4
funktioniert es gut. Können Sie einen Ansatz anbieten, der so klar oder effizient ist, ohne eine signierte Rechtsverschiebung zu verwenden?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
sarl
in 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
und das kompiliert zu
ähnlich für die Schicht
mit Ausgabe:
quelle
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 sindd
, von denen jedoch einer von Größe ist2*d-1
. Nicht gerade "gleiche" Abteilungen. Können Sie Vorschläge machen, wann die Oddball-Partition tatsächlich nützlich ist?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.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.
quelle
eval
) dies jedes Mal neu gemacht haben. Egal, ja, es ist ein ziemlich schlechter Test, weil es eine sehr dumme Optimierung ist.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.quelle
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.
quelle
x/2
zux>>1
. Für signierte Werte, fast alle Implementierungen definierenx>>1
eine Bedeutung haben , die zu äquivalent istx/2
, kann aber schneller berechnet werden , wennx
positiv, und ist sinnvollerweise andersx/2
alsx
negativ ist.Ich würde sagen, es gibt mehrere Dinge zu beachten.
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.
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.
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.
quelle
>>
funktioniert und was/
nicht.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 int
Dose (in einigen Fällen)int
aus zuvor genannten Gründen besser optimiert werden kann als eine . Wenn Sie keine vorzeichenbehaftete Arithmetik benötigen, geben Sie das Vorzeichenbit nicht an.quelle
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.
quelle
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.
quelle
Die Antwort darauf hängt von der Umgebung ab, in der Sie arbeiten.
x /= 2
inx >>= 1
eine solche verwandelt , zieht das Vorhandensein eines Teilungssymbols in dieser Umgebung mehr Augenbrauen hoch als Verwenden einer Verschiebung, um eine Teilung zu bewirken.x >>= 1
ein Kommentar, der die Argumentation erläutert, wahrscheinlich nur aus Gründen der Klarheit des Zwecks am besten.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.5
für bestimmte Sprachen wie ActionScript an.quelle
Mod 2, Test für = 1. Keine Ahnung die Syntax in c. aber das kann am schnellsten sein.
quelle
Im Allgemeinen teilt sich die richtige Verschiebung:
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.
quelle
(x+128)>>8
für Werte berechnet wird, diex
nicht nahe am Maximum liegen, wie kann man dies ohne Verschiebung präzise tun? Beachten Sie, dass dies(x+128)/256
nicht funktioniert. Kennen Sie einen schönen Ausdruck, der wird?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.
quelle
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! :) :)
quelle
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 ..
quelle
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:
quelle