FAQ der Newsgroup de.comp.lang.assembler (d.c.l.a.)

Wie multipliziere ich ohne MUL?

In einem x86-Prozessor ist eine Aufgabe wie 23 * 10 leicht mit dem MUL-Befehl zu realisieren: 

mov ax, 23
mov bl, 10
mul bl

Danach steht im Register AX das Ergebnis.

Ein Sonderfall ist die Multiplikation mit 2. Hier wird besser geschoben. Das ist wie beim Dezimalsystem: Bei einer Aufgabe wie 23 * 10 wird an die 23 einfach hinten eine 0 angeklebt: 230. Auch im Binärsystem wird bei 10 geklebt. Allerdings ist im Binärsystem 10 (binär) = 2 (dezimal) und somit läuft die Kleberei bei der Multiplikation mit 2. 

Aufgabe: 23 * 2 = ?

Assembler:
mov ax, 23
shl ax, 1

Man kann auch mehrere Nullen hineinschieben. Wie im Dezimalsystem funktioniert das bei 10er-Potenzen, die aber im Binärsystem andere Dezimalzahlen darstellen:

Binär   Dezimal
1  =  20  =  1
10  =  21  =  2
100  =  22  =  4
1000  =  23  =  8
10000  =  24  =  16
100000  =  25  =  32
1000000  =  26  =  64
10000000  =  27  =  128
100000000  =  28  =  256
1000000000  =  29  =  512
10000000000  =  210  =  1024
  usw.
Aufgabe: 27 = ? 
Assembler:
    mov ax, 1
    mov cl, 7
    shl ax, cl

ab 80286:
    mov ax, 1
    shl ax, 7

Wenn der Multiplikator fest ist, dann kann man durch eine Kombination von Schiebe- und Additionsbefehlen manchmal die Ausführungszeit beschleunigen. Ein Term wie 23*10 lässt sich umwandeln in: (23*8)+(23*2). '*8' bedeutet 3 Schiebungen nach links, und '*2' bedeutet eine Schiebung nach links.

Aufgabe: 23 * 10
Umwandlung: = 23 * (8 + 2)
Distributivgesetz:   = (23 * 8) + (23 * 2)
Zweierpotenzen: = (23 * 23) + (23 * 21)
Assembler:
    mov ax, 23
    mov bx, ax
    shl ax, 3
    shl bx, 1
    add ax, bx
Aufgabe: 23 * 1000
Umwandlung: = 23 * (512 + 256 + 128 + 64 + 32 + 8)
Distributivgesetz:   = (23 * 512) + (23 * 256) + (23 * 128) + (23 * 64) + (23 * 32) + (23 * 8)
Zweierpotenzen: = (23 * 29) + (23 * 28) + (23 * 27) + (23 * 26) + (23 * 25) + (23 * 23)
Assembler:
    mov ax, 23
    mov dx, ax
    mov bx, ax
    shl ax, 9
    shl bx, 8
    add ax, bx
    mov bx, dx
    shl bx, 7
    add ax, bx
    mov bx, dx
    shl bx, 6
    add ax, bx
    mov bx, dx
    shl bx, 5
    add ax, bx
    mov bx, dx
    shl bx, 3
    add ax, bx

Wie kommt man nun oben bei der Umwandlung auf einfache Weise auf die Kombination '512 + 256 + ...'? Betrachten wir dasselbe im Dezimalsystem. Eine Zahl wie 1000 lässt sich umwandeln in: (1*1000) + (0*100) + (0*10) + (0*1). Eine Zahl wie 1024 lässt sich umwandeln in (1*1000) + (0*100) + (2*10) + (4*1). Man nimmt also immer eine Ziffer und multipliziert sie mit der entsprechenden 10er-Potenz: (1*103) + (0*102)+ (0*101) + (0*100). Wie man sieht, werden die Potenzen von rechts nach links mit 0 beginnend um jeweils 1 hochgezählt. Im Binärsystem läuft das genauso. Die Dezimalzahl 1000 wird im Binärsystem als 1111101000 dargestellt. Auch hier werden die Potenzen von rechts hochgezählt und mit den Ziffern multipliziert:

29 28 27 26 25 24 23 22 21 20
1 1 1 1 1 0 1 0 0 0
1 * 29 1 * 28 1 * 27 1 * 26 1 * 25 0 * 24 1 * 23 0 * 22 0 * 21 0 * 20

Auf diese Weise kann oben die Reihe 'Zweierpotenzen' bestimmt werden, danach die Reihe bei 'Distributivgesetz' und danach die Reihe bei 'Umwandlung'. Auf diese Weise kann aber auch ein allgemeiner Multiplikations-Algorithmus gebildet werden. An einzelne Bits kommt man mit Schieben, eine Zweierpotenz bildet man auch mit Schieben. 

Aufgabe:           23 * 1000
Assembler 
    xor ax, ax        ; Ergebnis
    mov dx, 23        ; Multiplikant
    mov bx, 1000      ; Multiplikator
    mov cx, 16        ; Schleifenzähler für 16 Bits
  Schleife:           ; for (cx=16; cx>0; cx--)
    shr bx, 1         ; nach rechts ins Carry
    jnc NoBit         ; Sprung, wenn Carry = 0
    add ax, dx        ; Carry = 1, DX kann addiert werden
  NoBit:
    shl dx, 1         ; DX = DX * 2
    loop Schleife

Ralph 'rkhb' Bauer Jul 2008