Das Zweierkomplement (auch 2-Komplement – verallgemeinert b-Komplement (b Basis) –, Zweikomplement, B(inär)-Komplement, Basiskomplement, two’s complement) ist eine Darstellungsweise für positive und negative Integer-Zahlen im Dualsystem, die keine zusätzlichen Zeichen wie + und − benötigt. Dies ist in der Digitaltechnik (insbesondere in Computern) von Bedeutung, da das Zweierkomplement es erlaubt, die Subtraktion auf die Addition zurückzuführen und im Rahmen eines Addierwerks durchzuführen. Das Zweierkomplement setzt ein beschränktes, vordefiniertes Format (Bit-Länge) für die Darstellung von Binärzahlen voraus, da die Vereinbarung eine feste Bedeutung für das höchstwertige Datenbit verlangt.
Das Zweierkomplement kann als eine Interpretationsweise formatierter binärer Bitfolgen gesehen werden, welche für negative Werte von Integer-Variablen auftritt, für die ein in positiv und negativ geteilter Wertebereich definiert ist. Dies sind die sogenannten "signed integer" im Gegensatz zu den "unsigned integer" in Programmiersprachen. Für letztere tritt ein Zweierkomplement nicht auf.
Motivation + Vergleich der Darstellung eines Nibbles (4 Bit) als vorzeichenloser Wert (0's), als Vorzeichen und Betrag (V&B), im Einer- (1's) und im Zweierkomplement (2's)Gespeicherter Wert Dezimale Interpretation, Tabelle 2.1: „Negative Zahlen im Dualsystem“ in Abschnitt 2.1.5 „Darstellung negativer Zahlen im Dualsystem“ Bin Hex 0's V&B 1's 2's 0000 0 0 0 0 0 0001 1 1 1 1 1 0010 2 2 2 2 2 0011 3 3 3 3 3 0100 4 4 4 4 4 0101 5 5 5 5 5 0110 6 6 6 6 6 0111 7 7 7 7 7 1000 8 8 −0 −7 −8 1001 9 9 −1 −6 −7 1010 A 10 −2 −5 −6 1011 B 11 −3 −4 −5 1100 C 12 −4 −3 −4 1101 D 13 −5 −2 −3 1110 E 14 −6 −1 −2 1111 F 15 −7 −0 −1 Bei binären Codierungen von negativen Zahlen, welche nicht im Zweierkomplementformat vorliegen, werden sowohl das Vorzeichen als auch der Betrag durch getrennte Bits dargestellt, daher ist es wichtig zu wissen, welches Bit wofür verwendet wird. Üblicherweise wird das erreicht, indem sämtliche Zahlen eine konstante Stellenzahl haben und bei Bedarf mit führenden Nullen aufgefüllt werden, und einem davon getrennten Bit, welches das Vorzeichen codiert. Für die Verarbeitung sind dann entsprechende Steuerlogiken notwendig, welche die unterschiedlichen Bits und deren Bedeutung bewerten.
Bei der Codierung in der Zweierkomplementdarstellung ist dagegen die explizite Unterscheidung zwischen einem ausgezeichneten Vorzeichenbit und den Bits, die den Betrag beschreiben, nicht notwendig. Negative Zahlen sind daran zu erkennen, dass das höchstwertige Bit den Wert 1 hat. Bei 0 liegt eine positive Zahl oder der Wert 0 vor. Der Vorteil dieses Zahlenformates besteht darin, dass für Verarbeitung in digitalen Schaltungen keine zusätzlichen Steuerlogiken notwendig sind.
Da in der Zweierkomplementdarstellung der Wert 0 den positiven Zahlen zugerechnet wird, umfasst der Wertebereich bei binären Stellen allgemein den Bereich (falls nicht anders definiert):
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)
Darstellung und Umwandlung aus dem Dezimalsystem Die Zweierkomplementdarstellung benötigt, anders als die Einerkomplementdarstellung, keine Fallunterscheidung, ob mit negativen oder mit positiven Zahlen gerechnet wird. Das Problem der Einerkomplementdarstellung, zwei Darstellungen für die Null zu haben, tritt nicht auf. Positive Zahlen werden in der Zweierkomplementdarstellung mit einer führenden 0 (Vorzeichenbit) versehen und ansonsten nicht verändert.
Negative Zahlen werden wie folgt aus einer positiven Zahl codiert: Sämtliche binären Stellen werden negiert und zu dem Ergebnis der Wert 1 addiert. (Mathematisch exaktes Verfahren siehe formale Umwandlung.)
Beispielhafte Umwandlung der negativen Dezimalzahl −4 in die Zweierkomplementdarstellung unter Verwendung von 8 binären Stellen: Vorzeichen ignorieren und ins Binärsystem umrechnen: 4(10) = 00000100(2) Invertieren: Not[00000100] = 11111011 Eins addieren: 11111011 + 00000001 = 11111100
11111100(2) = −4(10)
Name Der Name Zweierkomplement ergibt sich daraus, dass sich bei einstelligen Binärzahlen mit Übertrag Zahl und Gegenzahl immer zu 2, also 0 + Übertrag, ergänzen (Die Funktionen 1e(x) und 2e(x) bezeichnen das Einer- und Zweierkomplement von x):
x 1e(x) 2e(x) x+2e(x)0 1 10 101 0 1 10
Das muss auch so sein, da das Zweierkomplement um 1 größer ist als das Einerkomplement.
Umwandlung per Hand Trick zur schnelleren Umwandlung (einer negativen in eine positive Binärzahl oder umgekehrt) von Hand: Von rechts angefangen, alle Nullen und die erste Eins abschreiben und alle nachfolgenden Stellen invertieren.
Fange bei der rechten Stelle (niedrigstwertiges Bit) an.
Wenn diese Stelle eine 0 ist, schreibe eine 0 und gehe zu Punkt 3; Wenn diese Stelle eine 1 ist, schreibe eine 1 und gehe zu Punkt 4. Gehe ein Zeichen nach links und wiederhole Punkt 2. Invertiere alle restlichen Stellen bis zum höchstwertigen Bit.
Alternativen
Separate Interpretation des Vorzeichenbits
Die Zweierkomplementdarstellung kann man sich auch so veranschaulichen: Alle Bits haben die gleiche Wertigkeit wie bei positiver Darstellung. Das MSB (most significant bit = höchstwertige bit) allerdings erhält die negative Wertigkeit. Durch Subtraktion dieses Bits lassen sich Zahlen sehr schnell umwandeln. Beispiel mit 8-Bit-Binärzahlen in Zweierkomplementdarstellung:
Wertigkeit −128 64 32 16 8 4 2 1 SummeBitfolge 00011010 0 0 0 1 1 0 1 0 +26Bitfolge 11100110 1 1 1 0 0 1 1 0 −26
00011010(2) = 16 + 8 + 2 = 26 11100110(2) = −128 + 64 + 32 + 4 + 2 = −26
In einem nachfolgenden Abschnitt wird die Korrektheit dieses Verfahrens erläutert.
Subtraktion von der Wertebereichsgrenze
Als weitere Methode kann man die Zahl, wenn sie negativ ist, einfach zu der Zahl direkt jenseits des Wertebereichs addieren. Beispielsweise überdecken vorzeichenlose 8-Bit-Zahlen den Wertebereich 0–255, die direkt folgende Zahl ist die 256. Eine −1 muss man nur zu 256 addieren und erhält den Wert 255 (= 1111 1111b), wie gewünscht. Analog führt eine −128 zum Wert 128.
Interpretation im Restklassenring
Für das Verständnis des Zweierkomplements ist es hilfreich, sich zu vergegenwärtigen, dass gängige Mikroprozessoren in Restklassenringen rechnen. Tatsächlich geht es gar nicht darum, positive und negative Zahlen unterschiedlich zu behandeln, vielmehr geht es um eine Vereinbarung, welche Repräsentanten gewählt werden, um eine bestimmte Restklasse zu beschreiben.
Die vier Grundrechenarten im Dualsystem sind für positive und negative Zahlen völlig gleich.
Im Kontext der vorherigen Beispiele kann man die Rechnung (−7) · (−3) auf einem Rechner mit 8 Bit Wortbreite betrachten. Bei 8 Bit Wortbreite ist der darstellbare Zahlbereich 0 bis 255, und selbst das ist schon eine Auswahl von Repräsentanten, denn es geht eigentlich um Klassen des Restklassenringes . Und an dieser Stelle kann man die Zahlen von 0 bis 255 als Repräsentanten wählen, oder aber, völlig äquivalent, die Zahlen −128 bis 127. Beim Rechnen im Zweierkomplement werden Zahlen, genau genommen, gar nicht „umgewandelt“, vielmehr werden zum Rechnen geeignete Repräsentanten der beteiligten Restklassen gewählt.
Im Beispiel können für −3 und −7 die Repräsentanten 253 und 249 gewählt werden:
Multipliziert ergibt sich:
Bei der „Umwandlung“ von positiven zu negativen Zahlen, es handelt sich tatsächlich nur um eine geschickte Auswahl von Repräsentanten der beteiligten Restklassen, fällt der besondere Charme des Zweierkomplements ins Auge: −1 ist nichts anderes als das Ergebnis der Rechnung 0 minus 1 gerechnet in den Grundrechenarten des Dualsystems. Es wird lediglich zu den 8 Bit eines Registers, wie sie in diesem Beispiel verwendet werden, ein Carrybit hinzugefügt.
Bitstelle: C 7 6 5 4 3 2 1 00: 0 0 0 0 0 0 0 0 01 subtrahieren: 0 0 0 0 0 0 0 0 1Ergebnis: 1 1 1 1 1 1 1 1 1
Es ergibt sich also die Zweierkomplementdarstellung von −1 und auch das Carrybit ist korrekt gesetzt.
Man kann nun die Umwandlung von Zahlen ins Zweierkomplement im Restklassenring deuten. Wenn z. B. die Darstellung von −3 gesucht wird, liegt −3 in derselben Kongruenzklasse wie 253. Es reicht also aus, zu −3 den Wert 256 zu addieren, um einen brauchbaren Repräsentanten zu erhalten.
Zählt man nun die Bitstellen der Bits 0 bis 7 zusammen, ist dies 255. Nimmt man also 3 als „positive“ Dezimalzahl und invertiert diese bitweise, ergibt sich der „Ergänzungswert“ zu 255, also 255 − 3. Und wenn das Ergebnis inkrementiert wird, ist dies (wegen Kommutativ- und Assoziativgesetz der Addition)
Das ganze bitweise:
Bitstelle: C 7 6 5 4 3 2 1 0 +3: 0 0 0 0 0 0 0 1 1 ~= 1 1 1 1 1 1 1 0 0 ++ 1 1 1 1 1 1 1 0 1
Am Ende ist also das Carrybit gesetzt, was eine negative Zahl anzeigt, und die Bitfolge 11111101, dies entspricht dezimal 253.
Weiter oben im Text wurde die Deutung des Carrybit als −256 vorgeschlagen. Diese findet sich übrigens auch bei Tietze/Schenck. Tatsächlich darf man im Restklassenring auf eine Zahl beliebig oft 256 addieren oder 256 subtrahieren. Die Kongruenzklasse wird nicht verlassen. Dies gilt ebenfalls für ganzzahlige Vielfache von 256. Wenn also das Carrybit als −256 interpretiert wird, und 1 1 1 1 1 1 1 0 1 folglich als −256 + 253 = −3, hat man eigentlich nur die Formel 253 = −3 + 256 anders hingeschrieben.
Vorzeichenwechsel im Restklassenring Die Interpretation im Restklassenring des Zweierkomplements lässt auch folgende Darstellung eines Vorzeichenwechsels zu:
Ist die Binärdarstellung einer -stelligen Zahl, so kann diese leicht von abgezogen werden: ist gerade mal hintereinander die Ziffer . Bei einer ziffernweisen Subtraktion stehen dort ausschließlich die Differenzen oder . Es werden keine Überträge nötig, jede Ziffer darf isoliert betrachtet werden.
Tatsächlich heißt das aber, dass die Differenzbildung der bitweisen Komplementbildung von entspricht: , dabei ist das bitweise Komplement von .
Im Restklassenring heißt das nichts anderes als:
und damit
und nach Addition von 1 auf beiden Seiten:
Ganz allgemein lässt sich also das Vorzeichen von umkehren, indem im ersten Schritt bitweise zu invertiert und im zweiten Schritt 1 addiert wird.
Dies entspricht genau der „alternativen Faustregel“, die im Abschnitt Umwandlung per Hand beschrieben wird. Und es funktioniert in beide Richtungen, egal ob eine Dezimalzahl erst ins Binärsystem umgewandelt werden soll, um dann das Vorzeichen umzukehren, oder ob bei einer negativen Zahl erst das Vorzeichen umgekehrt wird, um dann die gewonnene positive Zahl ins Dezimalsystem umzuwandeln.
Rechenoperationen Addition und Subtraktion Addition und Subtraktion benötigen keine Fallunterscheidung. Die Subtraktion wird auf eine Addition zurückgeführt.
Beispiele an 8 Bit langen Zahlen ohne Vorzeichenerweiterung:
−4 + 3 = −1 entspricht: 11111100 + 00000011 = 11111111
+4 +(− 4) = 0 entspricht: 00000100 + 11111100 = 100000000
Die vorderste Eins, in diesem Beispiel die 9. Stelle, wird ignoriert.
+4 − 3 = +1 entspricht: −4 − 3 = −7 entspricht: 00000100 11111100 + 11111101 + 11111101 = 100000001 = 111111001
Auch hier wird das korrekte Ergebnis durch Weglassen der 9. Stelle, in diesen Fällen 1, gebildet.
Solange der gültige n-stellige Zahlenbereich, bei 8 Bit breiten Zahlen der Wertebereich der Summe von −128 bis +127, nicht verlassen wird, funktioniert dieses Vorgehen ohne Vorzeichenerweiterung problemlos. Liegt dagegen der Wertebereich der Summe außerhalb des Intervalls, kommt es zu einem Überlauf, welcher in diesem Zusammenhang häufig und fälschlich mit dem Übertrag verwechselt wird. Die Abhilfe ist eine Vorzeichenerweiterung vor der Rechenoperation.
Vorzeichenerweiterung