✔ Rechnen mit Bit-Verschiebung

[Raldus]

Hi !

Ich möchte eine Zahl zwischen 1000 und 9999 in zwei Teile zerlegen. Die ersten beiden Ziffern und die letzten beiden Ziffern. Bisher löse ich das mit Division und Modulo

long ziffer = 1250;

long a = ziffer/100;
long b = ziffer%100;

Das läuft aber bei größeren Zahlenmengen recht langsam ab.

Kennt jemand eine Möglichkeit diesen Vorgang erheblich zu beschleunigen

Mir ist zu Ohren gekommen das Rechenoperationen per Bitverschiebung sehr schnell sein sollen. Die einfache Verschiebung mit << oder >> ist mir schon klar, aber dort geht es ja immer nur mit 2, 4, 8, 16 usw als Devisor bzw Multiplikant. Ansonsten habe ich mit der Bitschieberei keinerlei Erfahrungen.

Wo könnte ich einen Lösungsansatz finden ?

MfG Raldus

 

[Matthias Reitinger]

Hallo,

Kennt jemand eine Möglichkeit diesen Vorgang erheblich zu beschleunigen

Mit C alleine wüsste ich jetzt keinen Weg. Mittels (Inline-)Assembler könnte man allerdings unter Umständen etwas schneller davonkommen, sofern dein Compiler nicht sowieso schon entsprechend optimiert.

Mir ist zu Ohren gekommen das Rechenoperationen per Bitverschiebung sehr schnell sein sollen. Die einfache Verschiebung mit << oder >> ist mir schon klar, aber dort geht es ja immer nur mit 2, 4, 8, 16 usw als Devisor bzw Multiplikant. Ansonsten habe ich mit der Bitschieberei keinerlei Erfahrungen.

Ja, mit normalen Bitschiebeoperationen kann man nur Multiplikation bzw. Division mit/durch Zweierpotenzen durchführen. Für deinen Anwendungsfall sind sie also vermutlich nicht geeignet.

Grüße,
Matthias

 

[jsendrow]

Mir ist zu Ohren gekommen das Rechenoperationen per Bitverschiebung sehr schnell sein sollen. Die einfache Verschiebung mit << oder >> ist mir schon klar, aber dort geht es ja immer nur mit 2, 4, 8, 16 usw als Devisor bzw Multiplikant. Ansonsten habe ich mit der Bitschieberei keinerlei Erfahrungen.

Die Antwort auf diese Frage ist ein entschiedenes Jein

Ob Bitshifting schneller ist oder nicht hängt auf modernen Prozessoren von so vielen Faktoren ab, daß es keine einfache Antwort mehr auf diese Frage gibt. Es kann sogar sein das man durch Bitshifting gewisse Optimierungsmöglichkeiten verhindert die mit einer Multiplikation möglich wären und dadurch sogar langsamer wird.

Eine Optimierungsmöglichkeit für deinen Code gibt es aber die ca 80% rausholt:

   long a = ziffer / 100;
   long b = ziffer - (a * 100);

Da Divisionen erheblich langsamer sind als Multiplikationen soltle das einen spürbaren Unterschied ausmachen.

Weiterhin solltest Du versuchen den Code so anzuordnen, daß Multiplikationen "in blöcken" liegen. Bei aufeinander folgenden Multiplikationen können moderne Prozessoren diese ineinander "verschachteln" (->Befehls-Pipelining). Das bedeutet, wenn eine Multiplikation z.B. 2 Taktzyklen braucht, brauchen 4 Aufeinanderfolgende nicht 8 sondern nur 6 Zyklen. (Nur ein Pseudo-Beispiel, die genauen Zyklen sind Prozessorspezifisch)

 

[Raldus]

Hi !

Vielen Dank für die Antworten. Ich habe das Modulo durch den Code von 'jsendrow' ersetzt und zusätzlich noch einige Zeigerdeferenzierungen aus den vorhandenen Schleifen ausgelagert - es macht sich doch deutlich bemerkbar ! Die Funktionen hatte ich vor längerer Zeit mal entwickelt und sie sind seit dem in Benutzung. Wenn ich damals schon so schlau gewesen wäre wie heute dann wäre vieles einfacher. Aber jetzt kann ich den grundsätzlichen Funktionsablauf nicht mehr grossartig ändern - halt nur versuchen ihn zu optimieren.

Danke nochmals für die Tipps

MfG Raldus