Zweierkomplement
aus Wikipedia, der freien Enzyklopädie
Das Zweierkomplement (auch 2-Komplement, Zweikomplement, K2-Zahl, 2K-Zahl) ist eine Möglichkeit, negative Zahlen im Binärsystem darzustellen. Dabei werden keine zusätzlichen Symbole wie + und − benötigt. Dies ist vor allem für Computer wichtig, deren Logik allein auf Bits, welche entweder wahr oder falsch bzw. 1 oder 0 sind, ausgerichtet ist. Das heißt binäre Zahlen sind Folgen von 0 und 1. Das Zweierkomplement ist die vorherrschende Art, mit der negative ganze Zahlen im Computer dargestellt und mit Hilfe des Rechenwerkes Rechenoperationen durchgeführt werden können.
Da bei binären Kodierungen von negativen Zahlen sowohl Vorzeichen als auch die eigentliche Zahl durch Bits dargestellt werden, ist es wichtig zu wissen, welches Bit wofür verwendet wird. Üblicherweise wird dies erreicht, indem sämtliche Zahlen eine konstante Stellenzahl haben und bei Bedarf mit führenden Nullen aufgefüllt werden. Die unten angeführten Beispiele verwenden je sieben Ziffern für die Kodierung der Zahl und eine Ziffer für die Kodierung des Vorzeichens (8 Bits, das heißt 1 Byte).
Inhaltsverzeichnis |
[Bearbeiten] Darstellung und Umwandlung aus dem Dezimalsystem
Das Zweierkomplement benötigt wie das Einerkomplement keine Fallunterscheidung, ob mit negativen oder mit positiven Zahlen gerechnet wird. Das Problem des Einerkomplements, zwei Darstellungen für die Null zu haben, tritt nicht auf. Positive Zahlen werden im Zweierkomplement mit einer führenden 0 (Vorzeichenbit) versehen und ansonsten nicht verändert.
Negative Zahlen werden mit einer führenden 1 als Vorzeichenbit dargestellt und wie folgt kodiert: Sämtliche Ziffern der entsprechenden positiven Zahl werden negiert. Zum Ergebnis wird 1 addiert. (Mathematisch exaktes Verfahren siehe formale Umwandlung)
Beispielhafte Umwandlung der negativen Dezimalzahl -4 ins Zweierkomplement:
- Vorzeichen ignorieren und ins Binärsystem umrechnen: 4(10) = 00000100(2)
- Invertieren, da negativ: 11111011
- Eins addieren, da negativ: 11111011 + 00000001 = 11111100
11111100 = -4(10)
Weitere Beispiele:
+4(10) = 00000100 -4(10) = 11111100 -1(10) = 11111111 127(10) = 01111111 -127(10) = 10000001 -128(10) = 10000000
Durch die im Zweierkomplement verwendete Kodierung wird erreicht, dass nur eine einzige Darstellung der Null existiert.
[Bearbeiten] Umwandlung per Hand
Trick zur schnelleren Umwandlung (einer positiven in eine negative Binärzahl) per Hand: Von rechts angefangen alle 0en und die erste 1 abschreiben und alle danach kommenden Stellen invertieren.
1. Starte bei der rechten Stelle (LSB) 2a. Wenn diese Stelle eine 0 ist, schreib eine 0 und gehe zu Punkt 3 2b. Wenn diese Stelle eine 1 ist, schreib eine 1 und gehe zu Punkt 4 3. Gehe ein Zeichen nach links und wiederhole Punkt 2 4. Invertiere alle restlichen Stellen bis zum MSB
[Bearbeiten] Alternative
Die Zweierkomplementdarstellung kann man sich auch so veranschaulichen. Alle Bits haben die gleiche Wertigkeit wie bei positiver Darstellung. Das MSB (most significant bit) allerdings erhält die negative Wertigkeit. Auf diese Weise lassen sich Zahlen sehr schnell zwischen Dezimal- und Binärsystem umrechnen. Beispiel einer 8-Bit-Binärzahl 100110102 in Zweierkomplementdarstellung:
| Wertigkeit | -128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| Bitfolge | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
also 100110102 = ( − 128) + 16 + 8 + 2 = − 102
[Bearbeiten] Zahlenbereich
Mit n Bits lassen sich Zahlen von − 2n − 1 bis + 2n − 1 − 1 darstellen.
Beispiele:
bei 8 Bit: −128(10) bis +127(10) bei 16 Bit: −32768(10) bis +32767(10) bei 32 Bit: −2147483648(10) bis +2147483647(10) bei 64 Bit: −9223372036854775808(10) bis +9223372036854775807(10) usw.
[Bearbeiten] Rechenoperationen
Addition und Subtraktion benötigen keine Fallunterscheidung. Die Subtraktion wird auf eine Addition zurückgeführt.
Beispiele:
−4 + 3 = −1 führt zu 11111100 + 00000011 = 11111111; +4 − 4 = 0 führt zu 00000100 + 11111100 = 100000000 Durch Abschneiden der 1 (Übertrag in der 9. Stelle) wird daraus 00000000 +4 - 3 = +1 führt zu -4 - 3 = -7 führt zu 00000100 11111100 + 11111101 + 11111101 = 100000001 = 111111001 Auch hier entsteht das richtige Ergebnis durch Abschneiden der 1 in der 9. Stelle
Solange der gültige n-stellige Zahlenbereich (bei 8 Bit also von −128 bis +127) nicht verlassen wird, funktioniert das problemlos und ist bei der Addition von Zahlen mit unterschiedlichem Vorzeichen stets gegeben. Bei gleichem Vorzeichen (z. B. zwei negative Zahlen) kann sich ein Ergebnis außerhalb des gültigen Zahlenbereiches ergeben. Man erkennt es daran, dass bei Anwendung obiger Regeln ein falsches Ergebnis und ein falsches Vorzeichenbit entsteht. Zur Erkennung des Fehlers reicht es also aus, die Vorzeichenbits zu vergleichen.
Beispiel für Zahlenbereichsüberschreitung (Überlauf):
+4 + 127 = +131 führt zu -4 - 127 = -131 führt zu 00000100 11111100 + 01111111 + 10000001 = 10000011 = 101111101
Das linke Ergebnis würden wir als negative Zahl −125 interpretieren, das rechte (nach Abschneiden des Übertrags in der 9. Stelle) als +125! Diese Erscheinung nennt man Überlauf. Häufig wird dies mit dem Übertrag verwechselt, der allerdings das n+1-te (in unseren Beispielen also das 9.) Bit bezeichnet und nur beim Rechnen mit positiven Zahlen auch einen Überlauf signalisiert. Beim Rechnen mit Zweierkomplementzahlen klappt das nicht, wie obige Beispiele zeigen!
[Bearbeiten] Umwandlung ins Dezimalsystem
Wenn man eine Zahl vom Zweierkomplement ins Dezimalsystem umkodieren will, muss man folgendermaßen (umgekehrt der Umwandlung vom Dezimalsystem ins Zweierkomplement) vorgehen:
- Erste Stelle anschauen: wenn Ziffer = 1: Zahl negativ, Ziffer = 0: Zahl positiv
- Zahl ist positiv: Umrechnung vom Binärsystem ins Dezimalsystem ist bereits möglich
- Zahl ist negativ: Man subtrahiert 1 und negiert die einzelnen Ziffern (Dieser Schritt lässt sich für den Menschen vereinfachen: Man negiert zuerst die einzelnen Ziffern und addiert hinterher 1, was zu dem selben Ergebnis führt)
- Die entstandende, entsprechende, positive Zahl im Binärsystem rechnet man ins Dezimalsystem um
- Wenn negativ ein "−" vor die Zahl setzen
Beispiel:
11111101 1 subtrahieren = 11111100 invertiert = 00000011 00000011 im Dezimalsystem = 3 3 negiert = −3 11111101 (Zweierkomplement) = −3 (Dezimalsystem)
Eine andere Vorgehensweise zur Umwandlung einer Zweierkomplementzahl in das Dezimalsystem ist die folgende. Habe die Darstellung der Zahl im Zweierkomplement n Stellen, gegeben sind also n Bits an − 1an − 2an − 3...a1a0:
- xdezimal = − 2n − 1 * an − 1 + 2n − 2 * an − 2 + 2n − 3 * an − 3 + ... + 21 * a1 + 20 * a0
[Bearbeiten] Formale Umwandlung aus dem Binärsystem
Ist x eine negative Zahl, so errechnet sich x im Zweierkomplement(xz) mit n Stellen wie folgt:
- xz = 2n − | x |
Dementsprechend gilt auch
- xz + | x | = 2n
wobei | x | der positiven Zahl entspricht und 2n bei der Rechnung als Übertrag in der n + 1-sten Stelle auftritt.
[Bearbeiten] Zweierkomplement bei Festkommazahlen
Die Zweierkomplementdarstellung kann auch bei Festkommazahlen angewendet werden, womit beispielsweise gebrochene Zahlen wie 
binär darstellbar sind. Festkommazahlen werden unter anderem im Bereich der digitalen Signalverarbeitung verwendet. Festkommanzahlen werden allgemein durch ein Verschieben des Kommapunktes, der sich bei ganzen Zahlen immer rechts hinter der letzten Stelle befindet, gebildet. Dabei wird der Kommapunkt nicht in der Binärdarstellung gespeichert, sondern implizit seine Position als fix angenommen, wovon sich der Name der Festkommadarstellung ableitet.
Somit bleiben die oben genannten Rechenregeln im Prinzip erhalten, lediglich die Werte verändern sich. Zur Bildung einer binären Zweierkomplementärdarstellung müssen sämtliche Binärstellen invertiert werden und anschließend der Wert einer Quantisierungsstufe 2k addiert werden. Dabei gibt k die Position der letzten darstellbaren binären Ziffer an. Bei obigen Ganzzahlen wäre dies die Stelle k=0, womit bei der Bildung des Zweikomplementes bei ganzen Zahlen nach der Invertierung der Wert 20=1 addiert werden muss. Ist der Kommapunkt beispielsweise um 2 Stellen nach links verschoben und umfasst das binäre Wort die beiden Stellen rechts vom Kommapunkt, wäre k=-2 und somit muss zur Bildung des Zweierkomplemtes 2-2=0,25 addiert werden. (Hinweis: Der Kommapunkt kann bei Festkommazahlen auch außerhalb des darstellbaren Wertebereiches liegen.)
Ein Beispiel soll dies verdeutlichen: Eine binäre Zahl mit fünf Bit Wortlänge besitzt drei Vorkommastellen und zwei Nachkommastellen. Damit kann der Wertebereich -4 bis +3,75 in Schritten von 0,25 dargestellt werden. Die Zahl 2,25 entspricht der binären Zahl 010,012. Wird nun das Zweierkomplement davon gebildet, werden alle Stellen der binären Zahl invertiert und 2-2=0,25 addiert was 101,112 = -2,25 ergibt.
[Bearbeiten] Verallgemeinerung auf andere Stellenwertsysteme
Auch in anderen Stellenwertsystemen kann man ganze Zahlen ohne Verwendung eines Minuszeichens darstellen. Man hat hier aber das Problem, dass die Unterscheidung von positiven und negativen Zahlen mehr oder weniger willkürlich getroffen werden muss.
Beschränkt man sich auf n-stellige Zahlen zur Basis b, dann kann man die natürlichen Zahlen von 0 bis bn − 1 darstellen. Legt man eine Zahl in diesem Bereich als die größte positive Zahl fest, dann kann man jede größere Zahl x als Zweierkomplementdarstellung der negativen Zahl x − bn auffassen.
Die Rechenoperation der Negation wird analog durchgeführt wie zur Basis 2: Jede Ziffer z wird durch (b − 1) − z ersetzt, und zur so entstehenden Zahl wird 1 addiert.
Für die Basis b = 5 und die Stellenzahl n = 3 erhält man für −1 diese Darstellung:
- Die Ziffern der 1 sind 001.
- Die Negation der Ziffern ergibt 443.
- Addition von 1 liefert 444.
Damit wird −1 als 444 dargestellt. Die Addition 444 + 001 (zur Basis 5 und Stellenzahl 3) ergibt 000, da der letzte Übertrag wegfällt.
Legen wir in diesem Beispiel die größte positive Zahl als 222 fest (zur Basis 5, dezimal hat diese Zahl den Wert +62), dann ist 223 = −222 die kleinste negative Zahl (dezimal −62). Der Zahlenbereich reicht also von dezimal −62 bis +62.
Zur Basis 10 und Stellenzahl 2 hat man 99 = −01 und 50 = −50, hier hat man also wie zur Basis 2 eine weitere Zahl neben der 0, die mit ihrer Zweierkomplementdarstellung übereinstimmt. Dieses Phänomen tritt mit jeder geraden Basis auf.
Verallgemeinert man diese Schreibweise weiter, indem man unendlich viele Stellen zulässt, erhält man die Möglichkeit, p-adische ganze Zahlen darzustellen.
