Integer-Arithmetik
Die Integer-Arithmetik behandelt die Grundoperationen Addition, Subtraktion, Multiplikation und Division innerhalb eines Prozessors. Integer-Zahlen werden in Prozessoren in sogenannten Registern
verarbeitet. Register sind Speicherzellen, welche einen einzigen Wert speichern. Zu Beginn der Heimcomputer-Ära verarbeiteten Register 8 oder 16 Bit, wenig später konnten jedoch auch 32 Bit-Werte verarbeitet werden. Die 32-Bit-Ära hielt sich relativ lange, womit sich ein Quasi-Standard von 32 Bits für den überall verwendeten int-Typ etablierte. Heutige Prozessoren besitzen 64-Bit-Register.
In einem einzelnen Register können verschiedene Integer-Grössen gespeichert und verarbeitet werden, die eingebauten Grundoperationen erwarten jedoch normalerweise, dass die Register der beiden Operanden dieselbe Grösse, also dieselbe Anzahl binärer Ziffern speichern.
Die vier Grundoperationen können binär grundsätzlich genau gleich behandelt werden, wie die dezimalen Rechnungen, welche in der Grundschule gelernt werden. Nur müssen in einem Prozessor Rechnungen mittels des Binärsystems abgebildet und mithilfe logischer Verknüpfungen durchgeführt werden. Auf dieser Seite wird der Einfachheit halber nur die Ganzzahlcodierung mittels des Zweierkomplements betrachtet.
Addition und Subtraktion
Bei der Addition zweier Zahlen mit gleich vielen Ziffern (egal in welchem Zahlensystem) kann das Resultat stets mit gleich vielen Ziffern plus einer zusätzlichen Ziffer gespeichert werden. Die zusätzliche Ziffer wird zu Deutsch Übertrag
oder auf Englisch Carry
genannt. Beispielsweise ergibt 7 + 8 = 15, also die Summe 5 mit Übertrag 1. Bei binären Ziffern sind folgende vier Kombinationen möglich:
Aus dieser Tabelle wird ersichtlich, dass die Summe als XOR-Verknüpfung und der Übertrag als AND-Verknüpfung der beiden Operanden nachgebildet werden kann. Ein Prozessor führt diese logischen Verknüpfungen für alle binären Ziffern gleichzeitig aus. Falls nach der Verknüpfung ein Übertrag bleibt, so wird dieser in einem weiteren Schritt der jeweils nächst höheren Ziffer mittels einer Shift-Left-Operation (SHL) hinzuaddiert.
Decimal 14
Decimal 11
Sum: 25
Da die Register in einem Prozessor nicht beliebig viele binäre Ziffern speichern können, kann es sein, dass bei einer Addition ein Übertrag entsteht, welcher nicht mehr in dem Register Platz findet. Dieses überzählige Bit wird als Carry-Bit
bezeichnet. Wenn im folgenden beispielsweise 4-Bit-Register verwendet werden (mit Bit-Nummern 0 bis 3), so bezeichnet das Carry-Bit (abgekürzt mit C) das hypothetische Bit Nummer 4 des Registers. Dasselbe Beispiel wie oben sieht nun folgendermassen aus:
Decimal 14
Decimal 11
Sum: 9 + Carry
Das Resultat ist (fälschlicherweise) 9 mit gesetztem Carry-Bit. Nach Ausführung der Addition bleibt das Carry-Bit im Prozessor gesetzt und kann bei Bedarf ausgelesen werden. Somit dient das Carry-Bit als Statusanzeige darüber, ob die vorherige Operation einen Übertrag ergeben hat. In diesem Zusammenhang wird das Bit auch als Flag
bezeichnet (Anzeigeflagge).
Ein gesetztes Carry-Flag bedeutet jedoch nur, dass bei der Verknüpfung der Ziffern ein Übertrag ins überzählige Bit stattfand. Je nachdem, wie die Bits interpretiert werden, muss dies jedoch noch lange nicht heissen, dass das Ergebnis deswegen falsch wäre. Bislang wurde in dem Beispiel implizit angenommen, dass die verwendeten Zahlen unsigned, also ohne Vorzeichen zu interpretieren sind. Wenn nun jedoch die Zahlen als signed angenommen werden, so ergibt sich folgende Interpretation der Rechnung:
Decimal: -2
Decimal: -5
Sum: -7 + Carry
Dieses Resultat entspricht nun bereits dem korrekten Ergebnis, wenn die Zahlen im Zweierkomplement codiert sind. Das höchstwertige Bit des 4-Bit-Registers wird als Vorzeichen aufgefasst und als Sign-Bit
bezeichnet. Auch dieses Bit bleibt nach Ausführung der Operation als Sign-Flag
im Prozessor gespeichert, egal, ob nun die Zahlen als signed oder unsigned zu interpretieren sind. Dadurch ist es sehr einfach möglich, abzufragen, ob das Resultat negativ oder positiv ist (wenn es sich denn um eine signed-Zahl handelt).
Durch die Verwendung des Zweierkomplements können bei der Addition sowohl positive als auch negative Zahlen genau gleich behandelt werden können. Zudem kann durch die Verwendung des Zweierkomplements ganz einfach aus einer Addition eine Subtraktion gemacht werden: Einfach den zweiten Operanden negieren.
Weitere arithmetische Flags
Die oben angesprochenen Flags sind für die eigentliche Operation nicht wichtig, jedoch für nachfolgende Entscheidungen. Beispielsweise soll je nachdem, ob das Sign-Flag gesetzt ist oder nicht (also ob das Resultat positiv oder negativ ist), anderer Code ausgeführt werden. Genauso häufig wird getestet, ob eine Zahl Null ist oder ob eine Zahl grösser oder kleiner als eine andere ist. Solche Entscheidungen werden im Prozessor allesamt mittels der Subtraktion zweier binärer Zahlen getroffen. Nach Ausführung der Subtraktion sind alle benötigten Flags gesetzt und ein Prozessor kann sie auf Wunsch auslesen und entsprechenden Code ausführen.
Für eine korrekte Behandlung und Entscheidung aller möglichen Fälle einer Addition oder Subtraktion sind die oben angesprochenen Carry- und Sign-Flags jedoch noch nicht ausreichend. Zum einen wird das sogenannte Zero-Flag
benötigt. Es wird vom Prozessor gesetzt wenn (und nur wenn) das Resultat gleich Null ist. Damit kann beispielsweise geprüft werden, ob zwei Zahlen gleich sind, indem sie voneinander subtrahiert werden. Wenn das Resultat Null ergibt, sind sie gleich gross.
Des weiteren wird das sogenannte Overflow-Flag
benötigt, welches angibt, ob aufgrund einer Operation ein Überlauf eines signed-Wertes entstanden ist. Dieses Bit wird gesetzt, wenn bei der Addition zweier Werte der Übertrag an die höchstwertige Stelle sich von dem Carry-Bit unterscheidet.
Für eine Erklärung dieser Verknüpfung wird folgende Überlegung gemacht: Wenn zwei positive signed-Werte addiert werden, ist das Carry-Bit auf jeden Fall gelöscht. Sollte es passieren, dass aufgrund zu grosser Werte ein Übertrag an das höchstwertige Bit entsteht, so wird das Resultat negativ, was nicht korrekt ist. Wenn demgegenüber zwei negative signed-Werte addiert werden, ist das Carry-Bit auf jeden Fall gesetzt, die Summe der beiden Sign-Bits ergibt jedoch für sich alleine betrachtet 0, was nicht korrekt wäre. Das Resultat ist somit nur dann korrekt, wenn zusätzlich ein Übertrag an das höchstwertige Bit entsteht, sprich, die beiden Summanden ausreichend klein sind. Somit ist das Resultat in beiden Fällen genau dann korrekt, wenn der Übertrag an das höchstwertige Bit gleich ist wie das Carry-Bit.
Wenn bei der Addition zwei signed-Summanden mit unterschiedlichem Vorzeichen verwendet werden, so muss unterschieden werden, ob der Betrag des negativen Summanden kleiner oder grösser ist als derjenige des positiven Summanden. Wenn der Betrag des negatven Summanden kleiner ist, so muss das Resultat positiv sein. Aufgrund der Codierung mittels des Zweierkomplements entsteht auf jeden Fall ein Übertrag an das höchstwertige Bit. Da zudem genau einer der Summanden negativ war, wird dadurch auch das Carry-Bit gesetzt werden. Wenn der Betrag des negativen Summanden grösser ist als derjenige des positiven Summanden, so findet aufgrund der Codierung mittels des Zweierkomplements garantiert kein Übertrag an das höchstwertige Bit statt. Da wiederum nur einer der Summanden negativ war, wird jedoch auch das Carry-Bit nicht gesetzt werden. Somit ist das Resultat bei signed-Operanden mit unterschiedlichem Vorzeichen stets korrekt und folgt ebenfalls der Regel, dass das Carry-Flag gleich sein muss wie der Übertrag an das höchstwertige Bit.
Zusammenfassung: Das Carry-, das Overflow-Flag und das Sign-Flag bezeichnen unterschiedliche Dinge. Das Sign-Flag bezeichnet, wie das höchstwertige Bit des Resultates gesetzt ist. Das Carry-Flag bezeichnet, ob der Werteumfang einer unsigned-Zahl gesprengt wurde. Das Overflow-Flag bezeichnet, ob der Werteumfang einer signed-Zahl gesprengt wurde.
Bei der Addition beliebiger unsigned- und signed-Zahlen können somit unterschiedliche Kombinationen aus Carry-, Sign- und Overflow-Flag entstehen. Folgende Tabelle gibt eine Auflistung aller möglichen Fälle. Das Zero-Flag ist hier nicht aufgeführt, es wird einfach dann gesetzt, wenn das Resultat Null ergibt.
In dieser Tabelle wird ersichtlich, dass das Resultat einer unsigned-Rechnung genau dann falsch ist, wenn das Carry-Flag gesetzt ist. Das Resultat einer signed-Rechnung indes ist genau dann falsch, wenn das Overflow-Flag gesetzt ist. In diesen Fällen ist das Register Unter- oder Überlaufen, was auf englisch als Underflow
, beziehungsweise Overflow
bezeichnet wird. Hierbei muss jedoch klar getrennt werden zwischen dem Overflow des Registers und dem Overflow-Bit. Von einem Over- oder Under-Flow wird allgemein gesprochen, wenn bei einer beliebigen Operation der Werteumfang eines Typs gesprengt wird und das Resultat somit nicht mit demselben Typ gespeichert werden kann.
Mit was für Tricks diese Flags nun benutzt werden, um zu entscheiden, ob Zahlen grösser, kleiner oder gleich sind, wird auf dieser Seite nicht behandelt. Hierfür wird auf Literatur zu Assembler verwiesen. Die Ausführungen zu den Flags wurden nur der Vollständigkeit halber hier aufgeführt.
Multiplikation
Die Multiplikation funktioniert sehr ähnlich wie die schriftliche Multiplikation im normalen Dezimalsystem:
Jede Ziffer des ersten Operanden wird einzeln mit dem ganzen zweiten Operanden multipliziert, wobei das jeweilige Zwischenresultat jeweils um eine Ziffer nach links verschoben (Ziffernverschiebung) und am Schluss aufsummiert wird. Im Computer funktioniert dies nun nach 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 ein Register, welches doppelt so gross ist wie die ursprünglichen Operanden. Im folgenden Beispiel wird mit 4-Bit Registern gerechnet, womit das Resultat in einem 8-Bit-Register Platz findet.
Decimal: 3
Decimal: 5
Decimal: 15
Hier auf dieser Seite sei die Erklärung der Multiplikation mit diesem Beispiel grundsätzlich abgeschlossen. Dennoch sei darauf hingewiesen, dass die tatsächliche Ausführung in einem Prozessor noch stark optimiert werden kann. Da früher Registerplatz sehr rar war, wurde jedes Bit wo möglich doppelt genutzt. Für detailierte Informationen wird jedoch auf andere Seiten verwiesen.
Ein Augenmerk sei jedoch noch darauf gerichtet, dass diese Methode nur dann fehlerfrei funktioniert, wenn beide Operanden positiv sind. Hier ein Beispiel für eine fehlerhafte Berechnung:
Decimal: -3
Decimal: 5
Decimal: 65
Die naheliegendste Lösung dieses Problems wäre, die negativen Operanden mittels des Zweierkomplements umzuwandeln, die Multiplikation ganz normal mit positiven Zahlen durchzuführen und am Schluss der Rechnung das Resultat je nach Vorzeichen der beiden Operanden (Minus mal Minus gibt Plus) wieder zu negieren. Die Digitaltechnik kennt auch für die Berechnung von negativen Multiplikationen einige erstaunliche mathematische Tricks. Auf dieser Seite werden sie jedoch nicht weiter erläutert, der interessierte Leser möge sich andernorts schlaumachen.
Division
Bei der Integer-Division wird normalerweise nach einem sogenannten Subtraktions-Algorithmus
vorgegangen. Der erste Operand wird Dividend und der zweite Operand Divisor genannt. Die Überlegung beim Subtraktionsalgorithmus ist, dass stets ein möglichst grosses Vielfaches des Divisors vom Dividenden abgezogen wird, bis dass am Schluss der Dividend zu klein wird, um überhaupt noch geteilt zu werden. Dieser Restbetrag wird wie in der Schulbuchmathematik als Rest
, oder auf Englisch Remainder
genannt.
Um im Binärsystem ein Vielfaches des Divisors herzustellen, können einfach sämtliche Bits nach links verschoben werden. Im folgenden Beispiel werden zwei 8-Bit-Zahlen durch einander dividiert. Der Divisor wird hierbei zu Beginn so weit nach links verschoben, dass die höchstwertige Ziffer 1 der binären Zahl an der höchstwertigen Stelle des 8-Bit-Registers steht. Daraufhin wird sukzessive der Divisor um eine Ziffer nach rechts verschoben (shift right, SHR), während der Dividend immer kleiner wird, wenn der Divisor vollständig im Dividenden Platz findet und von ihm abgezogen wird.
Dividend: 220
Divisor: 12
Dividend: 220
Divisor: 192
Dividend: 28
Divisor: 96
Dividend: 28
Divisor: 48
Dividend: 28
Divisor: 24
Dividend: 4
Divisor: 12
Ergebnis: 18 Rest 4
Auf eine detailierte Beschreibung verschiedener Optimierungen und Randbedingungen wird auf dieser Seite verzichtet. Auch hier wird wieder auf die Spezialbehandlung von negativen Zahlen hingewiesen, Informationen darüber sind jedoch bei anderen Quellen zu finden.
Nächstes Kapitel: ASCII und UTF-8