H
ich mach mir mal die muehe...
// register eax und ebx enthalten zu multiplizierende operanden a & b
mov ecx,0 // ergebnis initial = 0
mulloop:
test eax,1 // pruefe unterstes bit von operand a
jz skip // wenn's nicht gesetzt ist, folgende addition ueberspringen
add ecx,ebx // addiere operand b zum ergebnis
skip:
shl ebx,1 // alle bits von operand b um ein bit nach oben verschieben
shr eax,1 // alle bits von operand a um ein bit nach unten verschieben
jnz mulloop // solang operand a ungleich 0...
done:
// ergebnis in ecx
je nach verwendetem compiler sind die sprungmarken mit beliebig vielen @ zu versehen.
was der algorithmus macht ist, fuer jedes gesetzte bit "n" von operand a zum ergebnis b*(2^n) zu addieren, also das gleiche wie eine schriftliche multiplikation nur eben im dual- anstatt im dezimalsystem.
anstatt jeweils das n-te bit von operand a zu pruefen, wird immer das unterste bit geprueft und der komplette operand um eine bitstelle verschoben (shr eax,1), wobei automatisch das zero-flag gesetzt wird, falls operand a nur noch nullen enthaellt, und dadurch die schleife (mulloop) unterbrochen.
operand b wird entsprechend jeweils um eine stelle nach oben verschoben, sodass ebx bei jedem durchlauf "n" schon b*(2^n) enthaelt und bei einem gesetzten bit0 in eax einfach auf das ergebnis addiert werden muss.
der algorithmus funktioniert auch fuer negative zahlen, weil das vorzeichen im obersten bit erhalten bleibt. nachteil in dem fall ist, dass die loop fuer einen negativen operand a immer 32 durchlaeufe macht, da ja dessen oberstes bit gesetzt ist. fuer kleine zahlen waere es also performanter das vorzeichen im vorfeld zu ueberpruefen, den algorithmus mit positivem a auszufuehren und das vorzeichen am ende entsprechend anzupassen.
da die fortfuehrung der schleife erst am ende geprueft wird, wird sie auch einmal fuer den fall a=0 durchlaufen, was quatsch ist, aber den code kuerzer macht - wer performant mit 0 multiplizieren will, findet dafuer auch sicherlich geistreichere moeglichkeiten...
darueber hinaus koennen in operand a beliebige bitmuster stehen, sodass die sprungvorhersage zum ueberspringen der addition relativ wahrscheinlich versagen wird. performanter waere daher die addition immer auszufuehren und aus dem zustand des gesetzten bit0 eine entsprechende bitmaske zu erzeugen, die den zu addierenden operand b entweder auf 0 setzt (bit0=0) oder unveraendert laesst (bit0=1), zb so:
mov edx,eax // operand a in temporaeres register laden
and edx,1 // nur bit0 behalten
dec edx // 1 subtrahieren (bit0=0: 0xffffffff bit0=1: 0)
not edx // bits negieren (bit0=0: 0 bit0=1: 0xffffffff)
and edx,ebx // und-verknuepfung mit operand b (bit0=0: 0 bit0=1: b)
add ecx,edx // zum ergebnis addieren
damit sollte das thema eigentlich inhaltlich erschoepft sein...