Die Integer-Arithmetik ist bei den meisten Prozessoren nach dem gleichen Schema gelöst. Die Integer-Arithmetik beinhaltet Addition, Subtraktion, Multiplikation und Division. Diese 4 Grundtypen können alle aufbauend aus den Logischen Operationen (AND, OR, XOR, ...) hergeleitet werden.
Einer- und Zweierkomplement
Vorgängig jedoch eine kleine Erklärung zum Einer- (NOT) und Zweierkomplement (NEG): Das Zweierkomplement macht meist nur mit den signed-Typen Sinn. In diesem Fall ist das Zweierkomplement einer Zahl nichts anderes als das negative Pendant. Das Einerkomplement errechnet sich durch:
Wobei r die Basis einer Zahl (in Computern die 2), n die Anzahl Ziffern (integers haben 32 Binärziffern), b die umzuwandelnde Zahl und e das zugehörige Einerkomplement ist. Eine Zeitsparende Errechnung des Einerkomplements ist:
Das Zweierkomplement nun ist nichts anderes als das Einerkomplement plus 1:
Addition und Subtraktion
Bei der Addition sowie der Subtraktion zweier Zahlen, die ein Register belegen, hat das Reslutat jeder denkbaren Rechnung Platz in einem gleich grossen Register plus einem zusätzlichen Bit. Dieses Bit wird bei einer unsigned-Rechnung Carry-Bit genannt, bei einer signed-Rechnung Overflow-Bit. Wenn wir annehmen, dass wir mit 8-Bit-Registern arbeiten, so zeigt das Carry-Bit an, ob ein Übertrag vom 7. Bit ins theoretisch 8. Bit stattgefunden hat. Das Overflow-Bit gibt an, ob theoretisch ein Übertrag vom 6. Bit ins 7. (Vorzeichen-)Bit stattgefunden hat.
Die Addition wird nun durch XOR und AND-Verknüpfungen erreicht. dabei betrachtet man folgende Tabelle für die Addition von 1-Bit-Werten:
| a | b | XOR = Summe | AND = Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Die Addition zweier 8-Bit-Zahlen rechnet nun genau mit diesen beiden Verknüpfungen und einer sll-Operation (Shift-Left) des Carry-Registers solange, bis das Carry-Resultat nur noch Nullen enthält.
a = 14: 00001110 b = 11: 00001011 AND = Carry: 00001010 XOR = Summe: 00000101 sll Carry: 00001010 AND = Carry: 00000100 XOR = Summe: 00010001 sll Carry: 00000100 AND = Carry: 00000000 XOR = Summe: 00011001 sum = 25
Betrachtet man die gleiche Rechnung mit 4-Bit Zahlen, so erhält man folgendes:
a = 14: 1110 b = 11: 1011 AND = Carry: 1010 XOR = Summe: 0101 sll Carry: 1010 AND = Carry: 0100 XOR = Summe: 10001 sll Carry: 0100 AND = Carry: 0000 XOR = Summe: 11001
sum = 9 mit gesetztem Carry-Bit (Overflow, also richtiges Resultat = 9 + 16 = 25). Betrachtet man nun diese 4-Bit-Zahlen als signed (das Bit Nummer 3 ist also das Vorzeichenbit), so erhält man folgendes:
a = -2: 1110 b = -5: 1011 ... XOR = Summe: 11001
sum = -7 mit gesetztem Carry-Bit (Hier jedoch kein Overflow, siehe unten)
Wie man sieht, funktioniert die Addition sowohl mit unsigned, als auch mit signed-Zahlen. Und somit ist auch klar, was bei einer Subtraktion zu tun ist: Man bildet einfach das Zweierkomplement des zweiten Operanden und führt dann eine normale Addition durch. Nun kommt nur noch die Frage, wann bei signed-Zahlen das Overflow-Bit gesetzt wird. Dazu geht man am besten alle möglichen Fälle durch (die Buchstaben bedeuten: S: Sign Flag, V: Overflow-Flag, C: Carry-Flag, fett=gesetzt, normal=nicht gesetzt):
Addition
| Operanden | Resultat | Beispiel | Beispiel in 4-Bit |
|---|---|---|---|
| positive Zahl (S) + positive Zahl (S) | positive Zahl (S C V) | 3+4=7 | 0011+0100 = 0111 |
| positive Zahl (S) + positive Zahl (S) | negative Zahl (S C V) | 4+5=-7 | 0100+0101 = 1001 |
| negative Zahl (S) + positive Zahl (S) | positive Zahl (S C V) | -2+5=3 | 1110+0101 =C0011 |
| negative Zahl (S) + positive Zahl (S) | negative Zahl (S C V) | -5+4=-1 | 1011+0100 = 1111 |
Subtraktion
| Operanden | Resultat | Beispiel | Beispiel in 4-Bit |
|---|---|---|---|
| positive Zahl (S) + negative Zahl (S) | positive Zahl (S C V) | 5-2=3 | 0101+1110 =C0011 |
| positive Zahl (S) + negative Zahl (S) | negative Zahl (S C V) | 4-6=-2 | 0100+1010 = 1110 |
| negative Zahl (S) + negative Zahl (S) | positive Zahl (S C V) | -5-4=7 | 1011+1100 =C0111 |
| negative Zahl (S) + negative Zahl (S) | negative Zahl (S C V) | -3-2=-5 | 1101+1110 =C1011 |
Eine einfach zu merkende Regel lautet: Wenn das Resultat ein anderes Vorzeichen besitzt, als der erste Operand, so ist ein Overflow aufgetreten. Mit diesen drei Flags und dem Zero-Flag, welches nur dann gesetzt ist, wenn ein Resultat genau Null ist können die Jump-, bzw. Branch-Befehle ausgeführt werden.
Multiplikation
Die Multiplikation funktioniert sehr ähnlich wie die die schriftliche Multiplikation im normalen Dezimalsystem:
123 * 456
---------
1368
912-
456--
---------
56088
Es werden also die Ziffern des ersten Operanden einzeln mit dem ganzen zweiten Operand multipliziert, wobei das jeweilige Resultat jeweils um eine Ziffer nach links verschoben wird (Ziffernverschiebung). Im Computer funktioniert dies nun nach einem sehr ähnlichen Schema, wobei hier nur jeweils mit 0 oder 1 Multipliziert werden muss (was zugegebenermassen nicht allzu schwierig ist). Das Resultat passt in jedem Fall in zwei Register. Des weiteren hat man sich folgendes überlegt: Da vom ersten Operanden zuerst nur die erste, dann die zweite, usw. Ziffer relevant ist, wird nach jedem Schritt das Register, in dem sich der erste Operand befindet, um 1 nach rechts verschoben; dadurch befindet sich das relevante Bit immer an der Bitposition 0.
Dasselbe gilt aber auch für das Resultat: Wenn man das Resultat des ersten Schrittes in das obere Register des endgültigen Resultat schreibt und dieses dann zusammen mit dem unteren Register um eines nach rechts verschiebt, so entspricht dies der Ziffern-Verschiebung. Somit hat man optimale Voraussetzungen für eine Platzeinsparung: Man definiert das Register des ersten Operanden als das untere Register des Resultates und setzt ein weiteres Register vornedran, in welches die jeweiligen Resultate der einzelnen Schritte eingetragen werden. Sodann werden beide Register zusammen um eines nach rechts verschoben, und man erhält stets eine Zwischensumme aller bisherigen Rechenschritte. Im Beispiel sieht dies folgendermassen aus:
a = 3 : 0011
b = 5 : 0101
0000 0011 * 0101 = 0101
/
-------ADD-------
/
0101 0011
shift--->
0010 1001 * 0101 = 0101
/
-------ADD-------
/
0111 1001
shift--->
0011 1100 * 0101 = 0000
/
-------ADD-------
/
0011 1100
shift--->
0001 1110 * 0101 = 0000
/
-------ADD-------
/
0001 1110
shift--->
0000 1111 = Resultat = 15
Dasselbe Resultat erhält man, wenn man den ersten und zweiten Operand vertauscht.
Wenn man signed-Zahlen multipliziert, treten bei diesem Algorithmus Probleme auf. Dies passiert genau dann, wenn der erste Operand negativ ist. Eine Lösung des Problemes wäre, wenn man vom ersten Operand von Anfang an das Zweierkomplement bildet. Eine andere Lösung (welche kleinere Register benötigt) ist die folgende: nach dem letzten (hier vierten) Schritt wird zum hohen Register des Resultates das Zweierkomplement des zweiten Operanden hinzugezählt. Hier ein Beispiel:
a = -3 : 1101
b = 5 : 0101 Zweierkomplement = -5 = 1011
0000 1101 * 0101 = 0101
/
-------ADD-------
/
0101 1101
shift--->
0010 1110 * 0101 = 0000
/
-------ADD-------
/
0010 1110
shift--->
0001 0111 * 0101 = 0101
/
-------ADD-------
/
0110 0111
shift--->
0011 0011 * 0101 = 0101
/
-------ADD-------
/
1000 0011
shift--->
0100 0001
+ 1011 0000 (Zweierkomplement im oberen Register)
-----------
1111 0001 = -15
Division
Die Division wird grundsätzlich nach dem Subtraktionsverfahren errechnet und funktioniert nach folgendem Prinzip: Es soll a durch b geteilt werden.
- d = b um y Ziffern nach links geshiftet, sodass die höchsten Einsen von b und a gleichauf liegen
- Falls a kleinergleich d: a = a - d und Resultat = Resultat + 2^y
- Falls a grösser als b, gehe zu 1
Am besten spielt man diesen Algorithmus einmal durch, um zu sehen, wie er funktioniert (Zuhause probiert man es dann einmal mit 0 als zweiten Operanden aus):
a = 737 : 01011100001
b = 32 : 0100000 Zweierkomplement = -32 = 1100000
Ergebnis sollte 23 Rest 1 sein
1. d = 01000000000 (b um y = 4 Stellen geshiftet)
2. a ist grössergleich d
a = 01011100001
+ 11000000000
-------------
a = 00011100001
Resultat = 00000 + 10000 = 10000
3. a ist grösser b, also zu 1:
-----------------
1. d = 00010000000 (b um y = 2 Stellen geshiftet)
2. a ist grössergleich d
a = 00011100001
+ 11110000000
-------------
a = 00001100001
Resultat = 10000 + 00100 = 10100
3. a ist grösser b, also zu 1:
-----------------
1. d = 00001000000 (b um y = 1 Stellen geshiftet)
2. a ist grössergleich d
a = 00001100001
+ 11111000000
-------------
a = 00000100001
Resultat = 10100 + 00010 = 10110
3. a ist grösser b, also zu 1:
-----------------
1. d = 00000100000 (b um y = 0 Stellen geshiftet)
2. a ist grössergleich d
a = 00000100001
+ 11111100000
-------------
a = 00000000001
Resultat = 10110 + 00001 = 10111
3. a ist nicht grösser b, also fertig.
Resultat = 10111 = 23, Rest = a = 1