Division mit Bit-Shift
-
Hallo allerseits,
ich will mit C++ unter Einsatz von Bit-Shift Multiplikationen und Divisionen durchführen. Bei der Multiplikation kein Problem, bei einfachen Divisionen auch nicht. Aber wenn ich keine 2^n habe, klappt das nicht so ohne weiteres.Dies hier klappt:
int a = 262144;
int b; // b = a / 8 / 32 / 128 = 8
b = ( a >> 3 );
b = ( b >> 5 );
b = ( b >> 7 );Hier habe ich Probleme:
int a = 40;
int b; // b = 40 / 5 = 8Wie müsste ich diese Division durchführen, weil ich Teile ja nicht durch 2^n, sondern will ja durch 5 teilen. Wie muss ich das machen?
-
Der Trick mit dem Bit-Shifting ist zwar recht nett, aber er funktioniert auch nur, wenn der Dividend (bzw. der zweite Faktor) eine Zweierpotenz ist.
-
CStoll schrieb:
Der Trick mit dem Bit-Shifting ist zwar recht nett, aber er funktioniert auch nur, wenn der Dividend (bzw. der zweite Faktor) eine Zweierpotenz ist.
Heißt ich bin aufgeschmissen, wenn ich nicht durch 2^n mit n als ganze Zahl arbeiten will?
-
jo stimmt.
weshalb wolltest du ne division durch 5 durch nen shift ersetzen ? hat das einen bestimmten grund?Meep Meep
-
Meep Meep schrieb:
jo stimmt.
weshalb wolltest du ne division durch 5 durch nen shift ersetzen ? hat das einen bestimmten grund?Meep Meep
Ich muss in knapp 2 Wochen eine Informatik-Klausur schreiben. In einer alten Klausur sah ich eine Bit-Shift basierende Multiplikation. In einem Nebensatz sagte der Dozent, dass er sich für die Klausur vielleicht auch ne Division ausdenken könnte. Deshalb hab ich mich gefragt, ob ich auch mit Bit-Shift durch Zahen, die nicht 2^n entsprechen dividieren kann.
-
Also so wie man etwa eine Multiplikation y=x*5 durch y = (x<<2)+x (klappt nur für unsigned-Werte!) ersetzen kann, kann man auch Divisionen bei konstantem Divisor durch eine Reihe anderer Operationen ersetzen. Ein Compiler wie GCC macht das auch, wie man leicht sehen kann, wenn man mit -O3 übersetzt und sich dann den Assemblercode anschaut, sofern auf der verwendeten Plattform eine Division tatsächlich langsamer ist als die Ersatzoperationen.
Es ist daher für echte Programme selten sinnvoll, diese Optimierungen "zu Fuß" durchzuführen, das kann der Compiler besser.
In einem Tutorial oder Programmierkurs kann es natürlich sinnvoll sein, so eine Optimierung mal zu Fuß auszuprogrammieren, aber ich halte es für wenig zielführend, den Lernenden grundlos derartige "Tricks" beizubringen, das führt nur zu schlechtem Programmierstil.
Gruß,
Roker
-
Ok. Dann Danke @all.
