Die eine Sache, die Computer wirklich gut können, ist Rechnen. Du erwartest jetzt vielleicht, dass alle CPUs die vier Grundrechenarten beherrschen, aber das ist nicht der Fall. Die ersten 8-Bit-Prozessoren konnten Zahlen nur addieren und subtrahieren, und selbst die Subtraktion wurde durch Addition des negierten Subtrahenden durchgeführt. Multiplikations- und Divisionsbefehle tauchten erstmals bei 16-Bit-Prozessoren auf, obwohl sie in der ersten Generation noch sehr langsam waren.

Einfache Multiplikationen und Divisionen durch Zweierpotenzen können erreicht werden, indem man einen Wert bitweise nach links bzw. rechts verschiebt. Das heißt, das Verschieben eines Wertes um ein Bit nach links ist dasselbe wie die Multiplikation mit 2, während das Verschieben um zwei Bits nach links ihn mit 4 multipliziert, und so weiter.

Aber wie können wir zwei beliebige Zahlen multiplizieren? Das muss Schritt für Schritt gemacht werden, indem wir grundlegende Operationen wie Addition oder Bit-Rotation verwenden. Dieser Artikel wird erklären, wie das auf einer Z80-CPU funktioniert.

In der Schule haben wir gelernt, große Zahlen durch schriftliche Multiplikation zu multiplizieren. Im Grunde teilen wir das Problem auf, indem wir den Multiplikator mit jeder Ziffer des Multiplikanden multiplizieren und dann die Produkte summieren. Wenn wir zum Beispiel das Produkt von 27 und 12 berechnen wollen, berechnen wir 27×2 = 54 und 27×1 = 27, und summieren dann die Produkte 57+270 = 324.

  27 × 12
———————————
       54
 +    27∙
———————————
      324

Wir können denselben Algorithmus auf einem Computer verwenden. Aber warte, müssten wir nicht immer noch multiplizieren, wenn auch mit kleineren Zahlen? Eigentlich nicht! Da Computer Binärziffern verwenden, müssen wir nur entweder mit 1 multiplizieren, was den Wert selbst ergibt, oder mit 0, was immer 0 ergibt.

Das ist dieselbe schriftliche Multiplikation von 27 (11011) und 12 (1100) mit Binärzahlen:

  11011 × 1100
————————————————
         00000
        00000∙
       11011∙∙
 +    11011∙∙∙
————————————————
     101000100

Die Schritte können in einer Schleife ausgeführt werden. Zu Beginn wird ein Ergebnisregister mit Null initialisiert. Wenn das ganz rechte Bit des Multiplikanden 1 ist, wird der Multiplikator zum Ergebnisregister addiert. Danach wird der Multiplikand um ein Bit nach rechts rotiert und der Multiplikator um ein Bit nach links rotiert. Diese Schleife wird wiederholt, bis der Multiplikand null ist, da sich das Ergebnis danach nicht mehr ändert.

Das folgende Z80-Assemblercode-Beispiel multipliziert die Werte in den Registerpaaren BC und DE und gibt das Produkt im Registerpaar HL zurück. Wenn während der Multiplikation ein Überlauf aufgetreten ist, wird das Carry-Flag gesetzt.

Der Multiplikand wird im Registerpaar BC gehalten. Um ihn um ein Bit nach rechts zu rotieren, verwenden wir zuerst den Befehl srl b. Er rotiert das B-Register, verschiebt den Wert von Bit 0 in das Carry-Flag und fügt eine 0 an Bit 7 ein, sodass der Multiplikand bei jeder Rotation mit Nullen aufgefüllt wird. Danach rotiert rr c das C-Register und verschiebt den Inhalt des Carry-Flags an Bit 7. Beide Befehle kombiniert rotieren das Registerpaar BC um ein Bit nach rechts, fügen eine 0 in das höchste Bit ein. Das niedrigste Bit wird in das Carry-Flag verschoben, wo es getestet werden kann.

Wir machen im Wesentlichen dasselbe mit dem Multiplikator im Registerpaar DE, aber in der entgegengesetzten Richtung. Da eine Rotation nach links um ein Bit den Wert im Grunde nur verdoppelt, hätten wir auch add de,de verwenden können. Leider bietet der Z80 keinen solchen Befehl an.

multiply:	ld	hl, 0			; lösche das Ergebnisregister
.loop:		ld	a, b			; ist BC == 0?
			or	c				;   (setzt auch das Carry-Flag zurück)
			ret	z				; dann sind wir fertig!
			srl	b				; logischer Rechts-Shift von BC
			rr	c				; Bit 0 geht ins Carry-Flag
			jr	nc, .zerobit	; es sei denn, Bit 0 war 0
			add	hl, de			; addiere Multiplikator zum Ergebnis
			ret	c				;   Rückkehr bei Überlauf
.zerobit:	sla	e				; verschiebe Multiplikator nach links
			rl	d				;   oberstes Bit geht ins Carry-Flag
			ret	c				;   Rückkehr bei Überlauf
			jr	.loop			; nächste Iteration

Das Beispiel multipliziert nur positive ganze Zahlen. Um negative ganze Zahlen zu multiplizieren, müssen wir zuerst alle Faktoren in positive Zahlen umwandeln und die Multiplikation durchführen. Das Ergebnis muss dann negiert werden, wenn einer der Faktoren negativ war, aber nicht beide.