Multiplikation und Division können beispielsweise mit Bitoperatoren erreicht werden
i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)
und so weiter.
Ist es tatsächlich schneller, say (i<<3)+(i<<1)
zu verwenden, um mit 10 zu multiplizieren, als i*10
direkt zu verwenden? Gibt es irgendeine Art von Eingabe, die auf diese Weise nicht multipliziert oder geteilt werden kann?
Antworten:
Kurze Antwort: Nicht wahrscheinlich.
Lange Antwort: Ihr Compiler verfügt über einen Optimierer, der weiß, wie man so schnell multipliziert, wie es Ihre Zielprozessorarchitektur kann. Am besten teilen Sie dem Compiler Ihre Absicht klar mit (dh i * 2 statt i << 1) und lassen Sie ihn entscheiden, wie die schnellste Assembly- / Maschinencodesequenz lautet. Es ist sogar möglich, dass der Prozessor selbst den Multiplikationsbefehl als eine Folge von Verschiebungen und Additionen im Mikrocode implementiert hat.
Fazit: Verbringen Sie nicht viel Zeit damit, sich darüber Gedanken zu machen. Wenn Sie verschieben möchten, verschieben Sie. Wenn Sie multiplizieren möchten, multiplizieren Sie. Tun Sie, was semantisch am klarsten ist - Ihre Mitarbeiter werden es Ihnen später danken. Oder verfluchen Sie Sie später, wenn Sie etwas anderes tun.
quelle
gcc -O3
return i*10
millis() >> 2
; Wäre es zu viel verlangt worden, nur zu teilen?i / 32
vsi >> 5
undi / 4
vsi >> 2
auf gcc für cortex-a9 (das keine Hardware-Abteilung hat) mit Optimierung -O3 getestet und die resultierende Baugruppe war genau die gleiche. Ich mochte es nicht, zuerst Divisionen zu verwenden, aber es beschreibt meine Absicht und die Ausgabe ist dieselbe.Nur ein konkreter Punkt: Vor vielen Jahren habe ich zwei Versionen meines Hashing-Algorithmus verglichen:
und
Auf jeder Maschine, auf der ich das Benchmarking durchgeführt habe, war die erste mindestens so schnell wie die zweite. Etwas überraschend war es manchmal schneller (zB bei einem Sun Sparc). Wenn die Hardware keine schnelle Multiplikation unterstützte (und die meisten damals nicht), konvertierte der Compiler die Multiplikation in die entsprechenden Kombinationen von Shifts und Add / Sub. Und weil es das endgültige Ziel kannte, konnte es dies manchmal in weniger Anweisungen tun, als wenn Sie die Schichten und die Add / Subs explizit geschrieben haben.
Beachten Sie, dass dies vor etwa 15 Jahren war. Hoffentlich sind die Compiler seitdem nur besser geworden, sodass Sie sich darauf verlassen können, dass der Compiler das Richtige tut, wahrscheinlich besser als Sie. (Der Grund, warum der Code so C'ish aussieht, ist, dass er vor über 15 Jahren war. Ich würde ihn heute offensichtlich verwenden
std::string
und iterieren.)quelle
Lassen Sie mich neben all den anderen guten Antworten hier auf einen weiteren Grund hinweisen, warum Sie Shift nicht verwenden sollten, wenn Sie Teilen oder Multiplizieren meinen. Ich habe noch nie jemanden gesehen, der einen Fehler eingeführt hat, indem er die relative Priorität von Multiplikation und Addition vergessen hat. Ich habe Fehler gesehen, die eingeführt wurden, als Wartungsprogrammierer vergaßen, dass das "Multiplizieren" über eine Schicht logischerweise eine Multiplikation ist, aber nicht syntaktisch dieselbe Priorität wie die Multiplikation hat.
x * 2 + z
undx << 1 + z
sind sehr unterschiedlich!Wenn Sie an Zahlen arbeiten, verwenden Sie arithmetische Operatoren wie
+ - * / %
. Wenn Sie an Bit-Arrays arbeiten, verwenden Sie Bit-Twiddling-Operatoren wie& ^ | >>
. Mischen Sie sie nicht; Ein Ausdruck, der sowohl ein bisschen Twiddling als auch Arithmetik hat, ist ein Fehler, der darauf wartet, passiert zu werden.quelle
Dies hängt vom Prozessor und vom Compiler ab. Einige Compiler optimieren den Code bereits auf diese Weise, andere nicht. Sie müssen also jedes Mal überprüfen, wenn Ihr Code auf diese Weise optimiert werden muss.
Wenn Sie nicht dringend optimieren müssen, würde ich meinen Quellcode nicht verschlüsseln, nur um eine Montageanweisung oder einen Prozessorzyklus zu speichern.
quelle
>>
Operator schneller als/
und wenn die vorzeichenbehafteten Werte negativ sein können, ist er oft auch semantisch überlegen. Wenn man den Wert braucht, derx>>4
produzieren würde, ist das viel klarer alsx < 0 ? -((-1-x)/16)-1 : x/16;
, und ich kann mir nicht vorstellen, wie ein Compiler diesen letzteren Ausdruck zu etwas Schönem optimieren könnte.Möglicherweise befindet es sich auf Ihrem Computer oder nicht. Wenn Sie sich darum kümmern, messen Sie Ihren tatsächlichen Verbrauch.
Eine Fallstudie - von 486 bis Core i7
Benchmarking ist sehr schwierig sinnvoll durchzuführen, aber wir können uns einige Fakten ansehen. Unter http://www.penguin.cz/~literakl/intel/s.html#SAL und http://www.penguin.cz/~literakl/intel/i.html#IMUL erhalten wir eine Vorstellung von x86-Taktzyklen benötigt für arithmetische Verschiebung und Multiplikation. Nehmen wir an, wir halten uns an "486" (das neueste aufgelistete), 32-Bit-Register und sofort, IMUL benötigt 13-42 Zyklen und IDIV 44. Jeder SAL benötigt 2 und addiert 1, so dass selbst wenn einige von ihnen zusammen oberflächlich aussehen, dies aussieht wie ein Gewinner.
In diesen Tagen mit dem Kern i7:
(von http://software.intel.com/en-us/forums/showthread.php?t=61481 )
(von einem Intel Klappentext)
Das gibt Ihnen eine Vorstellung davon, wie weit die Dinge gekommen sind. Die Optimierungs-Trivia - wie Bit Shifting versus
*
-, die bis in die 90er Jahre ernst genommen wurden, sind jetzt einfach veraltet. Die Bitverschiebung ist immer noch schneller, aber für Nicht-Zweierpotenzen (Mul / Div) ist es wieder langsamer, wenn Sie alle Verschiebungen durchführen und die Ergebnisse hinzufügen. Dann bedeuten mehr Anweisungen mehr Cache-Fehler, mehr potenzielle Probleme beim Pipelining, mehr Verwendung temporärer Register kann mehr Speichern und Wiederherstellen von Registerinhalten aus dem Stapel bedeuten ... es wird schnell zu kompliziert, alle Auswirkungen endgültig zu quantifizieren, aber sie sind überwiegend negativ.Funktionalität im Quellcode vs. Implementierung
Im Allgemeinen ist Ihre Frage mit C und C ++ gekennzeichnet. Als Sprachen der 3. Generation wurden sie speziell entwickelt, um die Details des zugrunde liegenden CPU-Befehlssatzes auszublenden. Um ihre Sprachstandards zu erfüllen, müssen sie Multiplikations- und Verschiebungsvorgänge (und viele andere) unterstützen, auch wenn die zugrunde liegende Hardware dies nicht tut . In solchen Fällen müssen sie das erforderliche Ergebnis unter Verwendung vieler anderer Anweisungen synthetisieren. Ebenso müssen sie Softwareunterstützung für Gleitkommaoperationen bereitstellen, wenn der CPU diese fehlt und keine FPU vorhanden ist. Moderne CPUs unterstützen
*
und<<
Das mag absurd theoretisch und historisch erscheinen, aber die Bedeutung ist, dass die Freiheit, die Implementierung zu wählen, in beide Richtungen geht: Selbst wenn die CPU über eine Anweisung verfügt, die die im Quellcode im allgemeinen Fall angeforderte Operation implementiert, steht es dem Compiler frei Wählen Sie etwas anderes, das es bevorzugt, da es für den speziellen Fall, mit dem der Compiler konfrontiert ist, besser ist .Beispiele (mit einer hypothetischen Assemblersprache)
Anweisungen wie exklusiv oder (
xor
) haben keine Beziehung zum Quellcode, aber wenn Sie irgendetwas mit sich selbst verknüpfen, werden alle Bits gelöscht, sodass etwas auf 0 gesetzt werden kann. Quellcode, der Speicheradressen impliziert, erfordert möglicherweise keine Verwendung.Diese Art von Hacks wurde verwendet, solange es Computer gibt. In den frühen Tagen von 3GLs musste die Compiler-Ausgabe den vorhandenen Hardcore-Hand-optimierenden Assembler-Entwickler erfüllen, um die Entwickler-Aufnahme zu sichern. Community, dass der produzierte Code nicht langsamer, ausführlicher oder auf andere Weise schlechter war. Compiler haben schnell viele großartige Optimierungen vorgenommen - sie wurden zu einem besseren zentralen Speicher als jeder einzelne Assembler-Programmierer, obwohl es immer die Möglichkeit gibt, dass sie eine bestimmte Optimierung verpassen, die in einem bestimmten Fall entscheidend ist - Menschen können es manchmal Nut it out und tappen nach etwas Besserem, während Compiler einfach tun, was ihnen gesagt wurde, bis jemand diese Erfahrung in sie zurückspeist.
Selbst wenn das Verschieben und Hinzufügen auf einer bestimmten Hardware noch schneller ist, hat der Compiler-Writer wahrscheinlich genau dann geklappt, wenn es sowohl sicher als auch vorteilhaft ist.
Wartbarkeit
Wenn sich Ihre Hardware ändert, können Sie sie neu kompilieren. Sie wird sich die Ziel-CPU ansehen und eine weitere beste Wahl treffen, während Sie Ihre "Optimierungen" wahrscheinlich nie wieder besuchen oder auflisten möchten, welche Kompilierungsumgebungen Multiplikation verwenden und welche sich verschieben sollten. Denken Sie an all die bitverschobenen "Optimierungen" ohne Potenz von zwei, die vor mehr als 10 Jahren geschrieben wurden und jetzt den Code verlangsamen, in dem sie sich befinden, da er auf modernen Prozessoren ausgeführt wird ...!
Glücklicherweise können gute Compiler wie GCC in der Regel eine Reihe von Bitverschiebungen und Arithmetik durch eine direkte Multiplikation ersetzen, wenn eine Optimierung aktiviert ist (dh
...main(...) { return (argc << 4) + (argc << 2) + argc; }
->imull $21, 8(%ebp), %eax
), sodass eine Neukompilierung auch ohne Korrektur des Codes hilfreich sein kann. Dies ist jedoch nicht garantiert.Seltsamer Bitshifting-Code, der Multiplikation oder Division implementiert, ist weit weniger aussagekräftig für das, was Sie konzeptionell erreichen wollten. Andere Entwickler werden davon verwirrt sein, und ein verwirrter Programmierer führt eher Fehler ein oder entfernt etwas Wesentliches, um die scheinbare Vernunft wiederherzustellen. Wenn Sie nur nicht offensichtliche Dinge tun, wenn sie wirklich greifbar sind, und sie dann gut dokumentieren (aber keine anderen Dinge dokumentieren, die sowieso intuitiv sind), sind alle glücklicher.
Allgemeine Lösungen versus Teillösungen
Wenn Sie etwas mehr Wissen, wie , dass Ihr
int
Wille wirklich nur Werte werden zu speichernx
,y
undz
dann können Sie in der Lage sein , einige Anweisungen zu arbeiten , dass die Arbeit für diese Werte und erhalten Sie Ihr Ergebnis schneller , als wenn der Compiler nicht haben diese Einsicht und braucht eine Implementierung, die für alleint
Werte funktioniert . Betrachten Sie zum Beispiel Ihre Frage:Sie veranschaulichen die Multiplikation, aber wie steht es mit der Division?
Nach dem C ++ Standard 5.8:
Ihre Bitverschiebung hat also ein implementierungsdefiniertes Ergebnis, wenn sie
x
negativ ist: Auf verschiedenen Computern funktioniert sie möglicherweise nicht auf die gleiche Weise. Funktioniert aber/
weitaus vorhersehbarer. (Es ist möglicherweise auch nicht perfekt konsistent, da verschiedene Maschinen unterschiedliche Darstellungen negativer Zahlen und damit unterschiedliche Bereiche haben können, selbst wenn die gleiche Anzahl von Bits die Darstellung ausmacht.)Sie können sagen "Es ist mir egal ... das
int
speichert das Alter des Mitarbeiters, es kann niemals negativ sein". Wenn Sie diese Art von besonderen Einsichten haben, dann ja - Ihre>>
sichere Optimierung wird möglicherweise vom Compiler übergeben, es sei denn, Sie tun dies ausdrücklich in Ihrem Code. Aber es ist riskant und selten nützlich, da Sie diese Art von Einsicht oft nicht haben und andere Programmierer, die an demselben Code arbeiten, nicht wissen, dass Sie das Haus auf ungewöhnliche Erwartungen an die Daten gesetzt haben, die Sie haben. Ich kümmere mich um ... was als absolut sichere Änderung an ihnen erscheint, könnte aufgrund Ihrer "Optimierung" nach hinten losgehen.Ja ... wie oben erwähnt, haben negative Zahlen ein implementierungsdefiniertes Verhalten, wenn sie durch Bitverschiebung "geteilt" werden.
quelle
intVal>>1
wird dieselbe Semantik verwendet, die sich von denenintVal/2
auf eine Weise unterscheidet, die manchmal nützlich ist. Wenn man den Wert, den gewöhnliche Architekturen liefern würdenintVal >> 1
, auf tragbare Weise berechnen muss, müsste der Ausdruck etwas komplizierter und schwerer zu lesen sein und würde wahrscheinlich einen wesentlich schlechteren Code erzeugen als den, für den er erzeugt wurdeintVal >> 1
.Ich habe gerade versucht, auf meinem Computer Folgendes zu kompilieren:
Beim Zerlegen wird Folgendes ausgegeben:
Diese Version ist schneller als Ihr handoptimierter Code mit reinem Verschieben und Hinzufügen.
Sie wissen wirklich nie, was der Compiler einfallen wird, daher ist es besser, einfach eine normale Multiplikation zu schreiben und ihn so optimieren zu lassen, wie er möchte, außer in sehr präzisen Fällen, in denen Sie wissen, dass der Compiler nicht optimieren kann.
quelle
vector<T>::size()
. Mein Compiler war ziemlich alt! :)Das Schalten ist im Allgemeinen viel schneller als das Multiplizieren auf Anweisungsebene, aber Sie verschwenden möglicherweise Ihre Zeit mit vorzeitigen Optimierungen. Der Compiler kann diese Optimierungen durchaus zur Kompilierungszeit durchführen. Wenn Sie dies selbst tun, wird die Lesbarkeit beeinträchtigt und die Leistung wird möglicherweise nicht beeinträchtigt. Es lohnt sich wahrscheinlich nur, solche Dinge zu tun, wenn Sie ein Profil erstellt haben und festgestellt haben, dass dies ein Engpass ist.
Tatsächlich kann der Teilungstrick, der als "magische Teilung" bekannt ist, enorme Gewinne bringen. Wieder sollten Sie zuerst ein Profil erstellen, um zu sehen, ob es benötigt wird. Wenn Sie es jedoch verwenden, gibt es nützliche Programme, mit denen Sie herausfinden können, welche Anweisungen für dieselbe Teilungssemantik erforderlich sind. Hier ist ein Beispiel: http://www.masm32.com/board/index.php?topic=12421.0
Ein Beispiel, das ich aus dem OP-Thread auf MASM32 entfernt habe:
Würde erzeugen:
quelle
Shift- und Integer-Multiplikationsbefehle weisen auf den meisten modernen CPUs eine ähnliche Leistung auf - Integer-Multiplikationsbefehle waren in den 1980er Jahren relativ langsam, aber im Allgemeinen trifft dies nicht mehr zu. Ganzzahlige Multiplikationsbefehle können eine höhere Latenz aufweisen , sodass es immer noch Fälle geben kann, in denen eine Verschiebung vorzuziehen ist. Das Gleiche gilt für Fälle, in denen Sie mehr Ausführungseinheiten beschäftigen können (obwohl dies in beide Richtungen möglich ist).
Die Ganzzahldivision ist jedoch immer noch relativ langsam, daher ist die Verwendung einer Verschiebung anstelle der Division durch eine Zweierpotenz immer noch ein Gewinn, und die meisten Compiler werden dies als Optimierung implementieren. Beachten Sie jedoch, dass die Dividende entweder ohne Vorzeichen oder als positiv bekannt sein muss, damit diese Optimierung gültig ist. Bei einer negativen Dividende sind Verschiebung und Division nicht gleichwertig!
Ausgabe:
Wenn Sie dem Compiler helfen möchten, stellen Sie sicher, dass die Variable oder der Ausdruck in der Dividende explizit ohne Vorzeichen ist.
quelle
Dies hängt vollständig vom Zielgerät, der Sprache, dem Zweck usw. ab.
Pixelknirschen in einem Grafikkartentreiber? Sehr wahrscheinlich, ja!
.NET-Geschäftsanwendung für Ihre Abteilung? Absolut kein Grund, sich überhaupt damit zu beschäftigen.
Für ein Hochleistungsspiel für ein mobiles Gerät lohnt es sich möglicherweise, einen Blick darauf zu werfen, jedoch erst, nachdem einfachere Optimierungen durchgeführt wurden.
quelle
Tun Sie dies nur, wenn Sie dies unbedingt müssen und Ihre Code-Absicht eher eine Verschiebung als eine Multiplikation / Division erfordert.
An einem typischen Tag - Sie könnten möglicherweise einige Maschinenzyklen einsparen (oder verlieren, da der Compiler besser weiß, was zu optimieren ist), aber die Kosten lohnen sich nicht - verbringen Sie Zeit mit kleinen Details und nicht mit tatsächlichen Aufgaben. Die Pflege des Codes wird schwieriger und schwieriger Ihre Mitarbeiter werden Sie verfluchen.
Möglicherweise müssen Sie dies für Berechnungen mit hoher Last tun, bei denen jeder gespeicherte Zyklus Minuten Laufzeit bedeutet. Sie sollten jedoch jeweils einen Ort optimieren und jedes Mal Leistungstests durchführen, um festzustellen, ob Sie es wirklich schneller gemacht oder die Compilerlogik gebrochen haben.
quelle
Soweit ich weiß, kann die Multiplikation bei einigen Maschinen bis zu 16 bis 32 Maschinenzyklen erfordern. So Ja , je nach Maschinentyp sind bitshift Betreiber schneller als Multiplikation / Division.
Bestimmte Maschinen haben jedoch einen Mathematikprozessor, der spezielle Anweisungen zur Multiplikation / Division enthält.
quelle
Ich stimme der markierten Antwort von Drew Hall zu. Die Antwort könnte jedoch einige zusätzliche Hinweise enthalten.
Für die überwiegende Mehrheit der Softwareentwickler sind Prozessor und Compiler für die Frage nicht mehr relevant. Die meisten von uns sind weit jenseits von 8088 und MS-DOS. Es ist vielleicht nur für diejenigen relevant, die sich noch für eingebettete Prozessoren entwickeln ...
Bei meiner Softwarefirma sollte Mathematik (add / sub / mul / div) für die gesamte Mathematik verwendet werden. Während der Konvertierung zwischen Datentypen sollte Shift verwendet werden, z. ushort zu Byte als n >> 8 und nicht n / 256.
quelle
Bei vorzeichenbehafteten Ganzzahlen und Rechtsverschiebung gegenüber Division kann dies einen Unterschied machen. Bei negativen Zahlen rundet die Verschiebung in Richtung negativer Unendlichkeit, während die Division in Richtung Null rundet. Natürlich ändert der Compiler die Division in etwas Billigeres, aber normalerweise ändert er sie in etwas, das das gleiche Rundungsverhalten wie die Division aufweist, da er entweder nicht beweisen kann, dass die Variable nicht negativ ist, oder einfach nicht Pflege. Wenn Sie also nachweisen können, dass eine Zahl nicht negativ ist, oder wenn es Ihnen egal ist, in welche Richtung sie gerundet wird, können Sie diese Optimierung auf eine Weise durchführen, die mit größerer Wahrscheinlichkeit einen Unterschied macht.
quelle
unsigned
Python-Test, der dieselbe Multiplikation 100 Millionen Mal mit denselben Zufallszahlen durchführt.
Wenn Sie also in Python eine Verschiebung anstelle einer Multiplikation / Division mit einer Zweierpotenz durchführen, ergibt sich eine leichte Verbesserung (~ 10% für die Division; ~ 1% für die Multiplikation). Wenn es sich nicht um eine Zweierpotenz handelt, ist mit einer erheblichen Verlangsamung zu rechnen.
Auch diese #s ändern sich abhängig von Ihrem Prozessor, Ihrem Compiler (oder Interpreter - der Einfachheit halber in Python).
Optimieren Sie nicht wie bei allen anderen vorzeitig. Schreiben Sie gut lesbaren Code, Profil, wenn er nicht schnell genug ist, und versuchen Sie dann, die langsamen Teile zu optimieren. Denken Sie daran, Ihr Compiler kann viel besser optimieren als Sie.
quelle
Es gibt Optimierungen, die der Compiler nicht durchführen kann, da sie nur für einen reduzierten Satz von Eingaben funktionieren.
Unten finden Sie C ++ - Beispielcode, der eine schnellere Division durchführen kann, indem eine 64-Bit-Multiplikation mit dem Kehrwert durchgeführt wird. Sowohl Zähler als auch Nenner müssen unter einem bestimmten Schwellenwert liegen. Beachten Sie, dass es kompiliert werden muss, um 64-Bit-Befehle zu verwenden, um tatsächlich schneller als die normale Division zu sein.
quelle
Ich denke, in dem einen Fall, dass Sie mit einer Zweierpotenz multiplizieren oder dividieren möchten, können Sie mit der Verwendung von Bitshift-Operatoren nichts falsch machen, selbst wenn der Compiler sie in einen MUL / DIV konvertiert, da einige Prozessoren Mikrocode (wirklich a Makro) sie sowieso, so dass Sie in diesen Fällen eine Verbesserung erzielen, insbesondere wenn die Verschiebung mehr als 1 beträgt. Oder expliziter, wenn die CPU keine Bitshift-Operatoren hat, wird es sowieso ein MUL / DIV sein, aber wenn die CPU hat Bitshift-Operatoren vermeiden Sie einen Mikrocode-Zweig und dies sind ein paar Anweisungen weniger.
Ich schreibe gerade Code, der viele Verdopplungs- / Halbierungsoperationen erfordert, da er an einem dichten Binärbaum arbeitet, und es gibt eine weitere Operation, von der ich vermute, dass sie optimaler ist als eine Addition - eine Linke (Zweierpotenz multiplizieren) ) mit einem Zusatz verschieben. Dies kann durch eine Linksverschiebung und ein x oder ersetzt werden, wenn die Verschiebung breiter als die Anzahl der Bits ist, die Sie hinzufügen möchten. Ein einfaches Beispiel ist (i << 1) ^ 1, wodurch eins zu einem doppelten Wert hinzugefügt wird. Dies gilt natürlich nicht für eine Rechtsverschiebung (Zweierpotenz), da nur eine Linksverschiebung (Little Endian) die Lücke mit Nullen füllt.
In meinem Code werden diese Multiplikationen / Division durch zwei und Potenzen von zwei Operationen sehr intensiv verwendet, und da die Formeln bereits ziemlich kurz sind, kann jeder Befehl, der eliminiert werden kann, einen erheblichen Gewinn bedeuten. Wenn der Prozessor diese Bitshift-Operatoren nicht unterstützt, wird kein Gewinn erzielt, aber es wird auch kein Verlust auftreten.
Außerdem stellen sie in den Algorithmen, die ich schreibe, die Bewegungen visuell dar, so dass sie in diesem Sinne tatsächlich klarer sind. Die linke Seite eines Binärbaums ist größer und die rechte ist kleiner. Außerdem haben in meinem Code ungerade und gerade Zahlen eine besondere Bedeutung, und alle linken Kinder im Baum sind ungerade und alle rechten Kinder und die Wurzel sind gerade. In einigen Fällen, auf die ich noch nicht gestoßen bin, aber vielleicht habe ich nicht einmal daran gedacht, ist x & 1 möglicherweise eine optimalere Operation als x% 2. x & 1 für eine gerade Zahl ergibt Null, für eine ungerade Zahl jedoch 1.
Wenn ich für x & 3 Null bekomme, weiß ich, dass 4 ein Faktor unserer Zahl ist und dasselbe für x% 7 für 8 und so weiter. Ich weiß, dass diese Fälle wahrscheinlich nur einen begrenzten Nutzen haben, aber es ist schön zu wissen, dass Sie eine Moduloperation vermeiden und stattdessen eine bitweise Logikoperation verwenden können, da bitweise Operationen fast immer die schnellsten sind und für den Compiler am wenigsten wahrscheinlich mehrdeutig sind.
Ich erfinde so ziemlich das Feld der dichten Binärbäume, daher erwarte ich, dass die Leute den Wert dieses Kommentars möglicherweise nicht verstehen, da die Leute sehr selten nur Faktorisierungen nur mit Zweierpotenzen durchführen oder nur Zweierpotenzen multiplizieren / teilen wollen.
quelle
Ob es tatsächlich schneller ist, hängt von der tatsächlich verwendeten Hardware und dem tatsächlich verwendeten Compiler ab .
quelle
Wenn Sie die Ausgabe für die Syntax x + x, x * 2 und x << 1 auf einem gcc-Compiler vergleichen, erhalten Sie in der x86-Assembly dasselbe Ergebnis: https://godbolt.org/z/JLpp0j
Sie können gcc also als klug genug betrachten, um seine beste Lösung unabhängig von Ihrer Eingabe zu ermitteln.
quelle
Ich wollte auch sehen, ob ich das Haus schlagen könnte. Dies ist allgemeiner bitweise für eine beliebige Zahl durch eine beliebige Zahlenmultiplikation. Die von mir erstellten Makros sind etwa 25% mehr bis doppelt so langsam wie die normale * Multiplikation. Wie von anderen gesagt, wenn es nahe an einem Vielfachen von 2 liegt oder aus wenigen Vielfachen von 2 besteht, könnten Sie gewinnen. wie X * 23 aus (X << 4) + (X << 2) + (X << 1) + X wird langsamer als X * 65 aus (X << 6) + X.
quelle