Ganzzahl, Zweierkomplement
Ganzzahlen werden in einem Computer mit dem Binärsystem abgebildet, sprich mit den Ziffern 0 und 1. Dieses System ist analog definiert zu dem für Menschen heutzutage üblichen Dezimalsystem, welches die Ziffern 0 bis 9 verwendet. Im Dezimalsystem wird zusätzlich zu den Ziffern ein sogenanntes Vorzeichen
verwendet, um eine Zahl als Positiv oder Negativ zu kennzeichnen. Im Binärsystem jedoch kann kein zusätzliches Zeichen ausser 0 und 1 auftreten, weswegen vorzeichenbehaftete Ganzzahlen mittels einer speziellen Codierung gespeichert werden müssen. Die heutzutage übliche Codierung speichert negative Werte als sogenanntes Zweierkomplement
.
Ein Javascript-Programm zur Veranschaulichung der Codierung von Ganzzahlen ist beim Zahlensystem-Umrechner zu finden.
Details
Vorzeichenlose Ganzzahlen einer bestimmten Bitlänge werden in C und C++ mit dem unsigned-Modifikator deklariert. Sie werden durch eine geordnete Aufzählung im Binärsystem abgebildet und nutzen sämtliche zur Verfügung stehenden Bits für die Speicherung des Zahlenwertes. Da sie als vorzeichenlos definiert sind, sind sie stets positiv. Eine detailierte Abhandlung kann auf der Seite über Zahlensysteme nachgelesen werden. Hier an dieser Stelle sollen folgende Beispiele für vorzeichenlose Ganzzahlen mit 16 Bit zur Veranschaulichung genügen:
Binary
0000 0000 0000 0000
0000 0000 0000 0001
0000 0000 0000 0010
0000 0000 0000 0011
0000 0000 0000 0100
...
Nebst vorzeichenlosen Ganzzahlen gibt es jedoch auch vorzeichenbehaftete Ganzzahlen, also Zahlen, welche explizit entweder als positiv oder negativ gekennzeichnet sind. In C und C++ werden vorzeichenbehaftete Ganzzahlen mit dem signed-Modifikator deklariert. Da jedoch ein Prozessor grundsätzlich nicht mit Werten, sondern mit Daten arbeitet, kann er nicht unterscheiden, ob es sich bei vorliegenden Daten um vorzeichenbehaftete oder vorzeichenlose Ganzzahlen handelt.
1101 1001 1001 1101
1101 1001 1001 1101
Um in einem Prozessor sowohl mit vorzeichenlosen als auch mit vorzeichenbehafteten Zahlen schnell und problemlos rechnen zu können, wird eine Ganzzahl speziell codiert.
Codierung von vorzeichenbehafteten Ganzzahlen
Das Ziel der Codierung für vorzeichenbehaftete Ganzzahlen ist, den Wertebereich der Zahl so zu verschieben, dass sowohl positive, als auch negative Werte abgebildet werden können, sich jedoch das Verhalten der für arithmetische Berechnungen benötigten Bit-Operationen im Prozessor nicht verändert.
Das jeweils höchstwertige Bit einer vorzeichenbehafteten Ganzzahl wird als das Vorzeichen interpretiert. Wenn das Bit auf 0 gesetzt ist, so hat die Zahl ein positives Vorzeichen und wenn das Bit auf 1 gesetzt ist, hat die Zahl ein negatives Vorzeichen. Dieses Bit wird auch als das sign
-Bit bezeichnet. Alle restlichen Bits speichern den eigentlichen Zahlenwert.
Positive vorzeichenbehaftete Ganzzahlen werden genau gleich codiert wie vorzeichenlose Ganzzahlen, allerdings ist der Wertebereich nach oben hin beschränkt, so dass das sign-Bit nicht verändert wird. Als Basis dient die Zahl 0, welche binär mit lauter Nullen codiert wird.
0000 0000 0000 0000
0000 0000 0000 0001
0000 0000 0000 0010
...
0111 1111 1111 1101
0111 1111 1111 1110
0111 1111 1111 1111
Solange eine positive Ganzzahl somit den Wertebereich nicht sprengt, ist es unerheblich, ob die Zahl vorzeichenlos oder vorzeichenbehaftet ist, da sie genau gleich codiert wird.
Die Codierung von negativen Ganzzahlen folgt aus der Überlegung, was passiert, wenn von der Zahl 0 die Zahl 1 abgezogen wird. Bei den vorzeichenlosen Ganzzahlen wird der Wertebereich unterschritten (Underflow) und es findet ein sogenannter Wrap-Around
statt, sprich: Alle Bits ändern von lauter Nullen auf lauter Einsen. Genau diese Codierung wird bei vorzeichenbehafteten Ganzzahlen als die Zahl -1 festgelegt. Wird die Subtraktion mit 1 weiter fortgeführt, so finden sich alle weiteren negativen Zahlen.
0000 0000 0000 0000
1111 1111 1111 1111
1111 1111 1111 1110
1111 1111 1111 1101
...
Der Wertebereich der negativen Zahlen ist nach unten hin beschränkt, so dass das sign-Bit nicht verändert wird. Somit ergibt sich als Beispiel für vorzeichenbehaftete Ganzzahlen mit 16 Bit folgende Codierungstabelle:
0111 1111 1111 1111
0111 1111 1111 1110
...
0000 0000 0000 0010
0000 0000 0000 0001
0000 0000 0000 0000
1111 1111 1111 1111
1111 1111 1111 1110
...
1000 0000 0000 0001
1000 0000 0000 0000
Zweierkomplement
Der Begriff Zweierkomplement bezeichnet die Umwandlung von einer positiven Zahl in ihr entsprechendes negatives Pendant, sprich beispielsweise die Umwandlung von 42 in -42. Das Zweierkomplement wird auch mit 2-Komplement
oder im Englischen mit Two's Complement
bezeichnet. Der Name entstammt der Überlegung, dass eine positive Zahl mit n Bits in ihr negatives Pendant umgewandelt werden kann, indem die Zahl von der Zweier
-Potenz 2^n abgezogen wird:
Der Wert 2^n kann jedoch in einer Ganzzahl mit n Bits nicht gespeichert werden. Deswegen wird von diesem Wert 1 abgezogen und abschliessend wieder 1 hinzuaddiert:
Der Wert (2^n)-1 entspricht einer vorzeichenlosen Ganzzahl mit n Bits, welche binär lauter Einsen aufweist. Wenn dieser Wert jedoch als eine vorzeichenbehaftete Ganzzahl interpretiert wird, so entspricht dies dem Wert -1:
1111 1111 1111 1111
1111 1111 1111 1111
Wenn diese Interpretation in die Formel des Zweierkomplements eingefügt wird, so ergibt sich der mathematische Sinn einer negativen Zahl
Two's complement =
Negative number =
Negative number =
Aufgrund dieser Überlegungen kann folgendes Beispiel einfach nachvollzogen werden:
1111 1111 1111 1111
- 0110 0100 1101 0100
-------------------
1001 1011 0010 1011
+ 0000 0000 0000 0001
-------------------
1001 1011 0010 1100
Es ist anzumerken, dass diese Umwandlung genauso funktioniert, wenn eine negative Zahl wieder in ihr positives Pendant umgewandelt werden soll:
1111 1111 1111 1111
- 1001 1011 0010 1100
-------------------
0110 0100 1101 0011
+ 0000 0000 0000 0001
-------------------
0110 0100 1101 0100
In C und C++ führt der Negativ-Operator diese Umwandlung für Ganzzahlen durch. Es ist zu beachten, dass durch die Definition des Zweierkomplement für jeden Ganzzahl-Typ zwei Werte existieren, welche durch den Negativ-Operator unverändert bleiben. Es sind dies der Wert 0 (Null) sowie der minimal mögliche Wert des Ganzzahl-Typs.
Einerkomplement
Bei einem aufmerksamen Studium der oben aufgezeigten Beispiele für das Zweierkomplement fällt auf, dass die Subtraktion der Zahl von -1 schlicht die Bits verdreht, sprich, jede 0 wird zu einer 1 und umgekehrt. Dies ist dasselbe, wie wenn die Zahl mit dem Bitweisen NOT-Operator verknüpft wird.
1111 1111 1111 1111
- 0110 0100 1101 0100
-------------------
1001 1011 0010 1011
Diese Umwandlung wird als das sogenannte Einerkomplement
bezeichnet. Der Name leitet sich ab aus der Tatsache, das die Zahl von lauter Einsen
subtrahiert wird.
Somit können das Einer- und das Zweierkomplement folgendermassen geschrieben und miteinander verknüpft werden:
One's complement =
One's complement =
Two's complement =
Two's complement =
Auf gewissen Systemen wird das Einerkomplement als Codierung für negative Zahlen eingesetzt. Sprich: Eine im Einerkomplement codierte Zahl ist positiv, wenn das Vorzeichen-Bit 0 ist und negativ, wenn das Vorzeichen-Bit 1 ist. Ist die Zahl negativ, so ist ihr Absolutbetrag definiert durch das Einerkomplement der Bitfolge.
Das Einerkomplement als Codierung für negative Ganzzahlen hat den Nachteil, dass negative und positive Wertebereiche bei Addition und Subtraktion nicht fliessend ineinander übergehen. Wird beispielsweise von der Zahl 0 (Null) die Zahl 1 abgezogen, so entsteht beispielsweise bei einem 8-Bit-Integer die Bitfolge 11111111, was dem Wert -0 entspricht.
Sign and magnitude
Der Vollständigkeit halber wird ganz kurz auf eine dritte Codierung von negativen Ganzzahlen eingegangen: Sign and Magnitude
. Diese Codierung verwendet genauso wie das Einer- und Zweierkomplement ein Bit für die Speicherung des Vorzeichens, interpretiert jedoch die restlichen Bits einfach als positive Ganzzahl.
Auch diese Codierung wird vereinzelt auf gewissen Systemen noch eingesetzt, hat jedoch dieselben Nachteile wie das Einerkomplement und bedingt zudem, dass je nach Operation untersschieden werden muss, ob das Vorzeichen-Bit gesetzt ist oder nicht. Sprich: Beispielsweise eine Addition auf negativen Zahlen muss anders behandelt werden, wie auf positiven Zahlen.
Ganzzahlen in C und C++
Bei modernen Systemen kann davon ausgegangen werden, dass negative Zahlen mittels des Zweierkomplements codiert werden.
Die Bit-Grösse der Zahl kann mittels der in der stdint-Bibliothek definierten Typen festgelegt werden, oder auf traditionelle Weise mit den Typen char, short, int, long und long long. Diese haben jedoch je nach System unterschiedliche Anzahl an Bits. Entsprechende Makros für die Ermittlung der auf einem System verwendeten Bit-Grössen sind in der limits-Bibliothek definiert.
Es ist zu beachten, dass C und C++ gemäss dem deklarierten Typ die entsprechenden Assembler-Befehle setzen. Dadurch findet genauso wie in Assembler keinerlei Spezialbehandlung für Over- oder Underflow statt. Dementsprechend können Wrap-Arounds auftreten und auch Umwandlungen zwischen signed und unsigned können zu falsch-Interpretationen des Vorzeichen-Bits führen. Weitere Informationen dazu sind bei den jeweiligen Typen beschrieben, sowie bei der arithmetischen Umwandlung.
Ein Beispiel für eine spezielle Behandlung von vorzeichenbehafteten Ganzzahlen kann beim Shift-Right-Operator nachgelesen werden. Für weitergehende Informationen über die verschiedenen arithmetischen Operationen mit Ganzzahlen wird die Seite Integerarithmetik verwiesen, sowie auf das Beispiel-Programm Zahlensystem-Umrechner.
Nächstes Kapitel: Realzahl, Floating-Point