Zweierkomplement

Das Zweierkomplement (auch 2-Komplement – verallgemeinert b-Komplement (b Basis) –, Zweikomplement, B(inär)-Komplement, Basiskomplement, two's complement) ist eine Möglichkeit, negative Zahlen im Dualsystem 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 positive und negative Zahlen im Computer dargestellt und für Rechenoperationen mit Hilfe des Rechenwerks erschlossen werden.

Motivation

8-Bit Zweierkomplement

Binärwert	Interpretation als Zweierkomplement	Interpretation als vorzeichenlose Zahl
00000000	0	0
00000001	1	1
...	...	...
01111110	126	126
01111111	127	127
10000000	−128	128
10000001	−127	129
10000010	−126	130
...	...	...
11111110	−2	254
11111111	−1	255

Da bei binären Kodierungen von negativen Zahlen, welche nicht im Zweierkomplementformat vorliegen, sowohl das Vorzeichen als auch der Betrag durch getrennte Bits dargestellt werden, 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ätzliche Steuerlogiken notwendig sind.

Da in der Zweierkomplementdarstellung der Wert 0 den positiven Zahlen zugerechnet wird, umfasst der Wertebereich bei n binären Stellen allgemein den Bereich (falls nicht anders definiert):

$-2^{n-1} , \ldots , 0, \ldots , 2^{n-1}-1$

Beispiele:

bei 8 Bit:                  −128(10)  bis                 +127(10)
bei 16 Bit:               −32768(10)  bis               +32767(10)
bei 32 Bit:          −2147483648(10)  bis          [phone](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 kodiert: 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:

1. Vorzeichen ignorieren und ins Binärsystem umrechnen: 4₍₁₀₎ = 00000100₍₂₎
2. Invertieren: Not[00000100] = 11111011
3. Eins addieren: 11111011 + 00000001 = 11111100

11111100(2) = −4(10)

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.

1. Fange bei der rechten Stelle (niedrigstwertiges Bit) an.
2. 1. Wenn diese Stelle eine 0 ist, schreibe eine 0 und gehe zu Punkt 3;
   2. Wenn diese Stelle eine 1 ist, schreibe eine 1 und gehe zu Punkt 4.
3. Gehe ein Zeichen nach links und wiederhole Punkt 2.
4. 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	Dezimal
Bitfolge	0	0	0	1	1	0	1	0	= 26
Bitfolge	1	0	0	1	1	0	1	0	= −102

00011010(2) = 16 + 8 + 2 = 26
10011010(2) = (−128) + 16 + 8 + 2 = −102

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 von der Zahl direkt jenseits des Wertebereichs subtrahieren. Beispielsweise überdecken vorzeichenlose 8-Bit-Zahlen den Wertebereich 0–255, die direkt folgende Zahl ist die 256. Eine –1 muss man nur von 256 abziehen und erhält den Wert 255 ( = 1111 1111b), wie gewünscht. Analog führt eine –128 zum Wert 128.

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 führt zu 
  11111100 
+ 00000011 
= 11111111;

 +4 +(− 4) = 0:
           00000100
        +  11111100  
          ---------
        = 100000000

Die vorderste Eins, in diesem Beispiel die 9. Stelle, wird verworfen.

+4 − 3 = +1 führt zu             −4 − 3 = −7 führt zu    
   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

Können die beiden Summanden beliebige Werte annehmen, ist für eine korrekte Addition in Zweierkomplementdarstellung eine Vorzeichenerweiterung nötig. Dabei wird von beiden Summanden zunächst die oberste Stelle dupliziert und somit die Stellenanzahl um eins vergrößert. In diesen Beispielen die 8. Stelle, welche auf die 9. Stelle kopiert wird. Anschließend wird die Addition wie oben, aber mit 9 Stellen, durchgeführt. Das Addierwerk muss dazu immer eine Stelle mehr umfassen.

Unterscheiden sich in der berechneten Summe dann die höchstwertige und die Stelle darunter voneinander, ist das Ergebnis nicht mehr im Wertebereich der Summanden darstellbar – es ist ein Überlauf aufgetreten. Je nach Anwendungsfall wird dann mit dem um ein Bit breiteren und korrekten Ergebnis weitergerechnet oder ein Fehlerabbruch ist die Folge.

Beispiel: Die Addition der beiden positiven Zahlen 50 und 80 ergibt 130 und überschreitet damit den Wertebereich. Die Zahl passt zwar noch in eine 8-Bit-Variable, aber das 8. Bit ist jetzt gesetzt, so dass die Zahl fälschlicherweise negativ erscheint. Manche Mikroprozessoren wie der 6502 melden ein solches Ereignis mit einem eigenen Statusbit, hier dem Overflow-Bit O, das der Programmierer nach vorzeichenbehafteten Rechenoperationen abfragt und entsprechend reagieren kann.

Beispiel für Vorzeichenerweiterung, die 9. Stelle der Vorzeichenerweiterung ist zur Verdeutlichung in Klammern geschrieben:

+4 + 127 = +131 führt zu          −4 − 127 = −131 führt zu
   (0)00000100                       (1)11111100
+  (0)01111111                     + (1)10000001
   -----------                       -----------
Ü  (0)11111000                     Ü (1)00000000
   -----------                       -----------
=  (0)10000011                     = (1)01111101

In beiden Fällen unterscheiden sich die 8. und 9. Stelle voneinander, eine Reduktion auf 8 Bit würde zu einem Fehler führen. Zur Verdeutlichung und Vergleich die obigen beiden Beispiele mit Vorzeichenerweiterung:

+4 − 3 = +1 führt zu             −4 − 3 = −7 führt zu    
   (0)00000100                        (1)11111100 
+  (1)11111101                      + (1)11111101
   -----------                        -----------
Ü  (1)11111000                      Ü (1)11111000
   -----------                        -----------
=  (0)00000001                      = (1)11111001

in beiden Fällen unterscheiden sich die 8. und 9. Stelle der Summe nicht, die beiden Ergebnisse können somit korrekt wieder auf 8 Stellen reduziert werden. Generell kann die Stellenanzahl in der Zweierkomplementdarstellung, von oben beginnend, so lange und ohne Verfälschung des Wertes reduziert werden, bis sich die beiden obersten Stellen im Wert voneinander unterscheiden. Das verdeutlicht den Umstand, dass bei der Zweierkomplementdarstellung von Zahlen keine fixe Stelle für die Codierung des Vorzeichens existiert.

Multiplikation

Auch die Multiplikation ist in der Zweierkomplementdarstellung im Rahmen von Multiplizierwerken möglich und stellt insbesondere in der digitalen Signalverarbeitung eine Grundfunktion dar. Für die schaltungstechnische Realisierung von Multiplizierwerken gibt es verschiedene Möglichkeiten. Bei einem Parallelmultiplizierer wird das Produkt durch eine Vorzeichenerweiterung, Stellenverschiebung und anschließende Addition gebildet. Die einzelnen Faktoren müssen dabei immer auf die Produktlänge vorzeichenerweitert werden. Neben den Parallelmultiplizierern existieren auch effizientere Implementierungsvarianten der Multiplikation, welche auf dem Booth-Algorithmus oder dem Bit-Pair-Verfahren basieren.

Bei zwei Faktoren zu je 4 Bit Länge ist das Produkt 8 Bit lang. Oder allgemein: Für zwei n Bit bzw. m Bit breite Faktoren ist das Produkt n+m Bit lang und alle Faktoren müssen vor der Berechnung mittels Parallelmultiplizierer auf diese Länge vorzeichenrichtig erweitert werden. An der Operation −7 · −3 in Zweierkomplementdarstellung, deren Faktoren sich mit je 4 Bit darstellen lassen, soll das verdeutlicht werden:

   11111001   (entspricht dezimal der Zahl −7, mit Vorzeichenerweiterung)
 · 11111101   (entspricht dezimal der Zahl −3, mit Vorzeichenerweiterung)
 ==========
 + 11111001   (1001 · 1, um null Stellen nach links verschoben und mit Vorzeichenerweiterung)
 + 00000000   (1001 · 0, um eine Stelle  nach links verschoben und mit Vorzeichenerweiterung)
 + 11100100   (1001 · 1, um zwei Stellen nach links verschoben und mit Vorzeichenerweiterung)
 + 11001000   (1001 · 1, um drei Stellen nach links verschoben und mit Vorzeichenerweiterung)
 + 10010000   (1001 · 1, um vier Stellen nach links)
 + 00100000   (1001 · 1, um fünf Stellen nach links, obere Bits hinausgeschoben)
 + 01000000   (1001 · 1, um sechs Stellen nach links, obere Bits hinausgeschoben)
 + 10000000   (1001 · 1, um sieben Stellen nach links, obere Bits hinausgeschoben)
 ==========
   00010101   (entspricht dezimal +21)

Wegen der Vorzeichenerweiterung lässt sich die Anzahl der Summanden reduzieren. Der Grund liegt darin, dass die nach oben vorzeichenerweiterten Bits der einzelnen Faktoren im Zweierkomplement immer identische Werte aufweisen. In diesem Beispiel liefert die Summe über die letzten fünf Zeilen immer den negierten Wert der vierten Zeile, womit sich die Berechnung in diesem Fall auf die Summation von drei Zeilen und der Subtraktion der letzten Zeile und somit auf die Hälfte des obigen Aufwandes reduziert:

       1001   (entspricht dezimal der Zahl −7)
     · 1101   (entspricht dezimal der Zahl −3)
     ======
 + 11111001   (1001 · 1, um null Stellen nach links verschoben und mit Vorzeichenerweiterung)
 + 00000000   (1001 · 0, um eine Stelle  nach links verschoben und mit Vorzeichenerweiterung)
 + 11100100   (1001 · 1, um zwei Stellen nach links verschoben und mit Vorzeichenerweiterung)
 − 11001000   (1001 · 1, um drei Stellen nach links verschoben und mit Vorzeichenerweiterung)
 ==========
   00010101   (entspricht dezimal +21)

Die Subtraktion in der letzte Zeile gilt unabhängig von den Vorzeichen der beiden Faktoren auch bei anderer Stellenanzahl und es muss keine Vorzeichenunterscheidung bei den Faktoren bzw. eine Vorzeichenkorrektur bei dem berechneten Produkt vorgenommen werden. Diese Subtraktion kann in schaltungstechnischen Realisierungen entweder durch Volladdierer, welche in den Subtraktionsmodus umgeschaltet werden können, erfolgen oder durch eine Invertierung der letzten Zeile und der zusätzlichen Addition von +1, analog wie bei der Bildung des Zweierkomplements.

Zur Verdeutlichung dieses optimierten Verfahrens eine Multiplikation mit unterschiedlichen Vorzeichen (−7) · 3 in Zweierkomplementdarstellung:

       1001   (entspricht dezimal der Zahl −7)
     · 0011   (entspricht dezimal der Zahl 3)
     ======
 + 11111001   (1001 · 1)
 + 11110010   (1001 · 1)
 + 00000000   (1001 · 0)
 − 00000000   (1001 · 0)
 ==========
   11101011   (entspricht dezimal −21)

Umwandlung ins Dezimalsystem

Wenn man eine Zahl von der Zweierkomplementdarstellung ins Dezimalsystem umkodieren will, muss man folgendermaßen (umgekehrt entsprechend der Umwandlung vom Dezimalsystem in die Zweierkomplementdarstellung) vorgehen:

1. Erste Stelle anschauen: wenn Ziffer = 1: Zahl negativ, Ziffer = 0: Zahl positiv.
2. Zahl ist positiv: Umrechnung vom Binärsystem ins Dezimalsystem ist bereits möglich;
3. 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 zum selben Ergebnis führt.)
4. Die entstandene, entsprechend positive Zahl im Binärsystem rechnet man ins Dezimalsystem um.
5. Wenn negativ, ein "−" vor die Zahl setzen.

Beispiel:

11111101 
1 subtrahieren  = 11111100
invertiert = 00000011
00000011 im Dezimalsystem = 3
3 negativ = −3

11111101 (Zweierkomplementdarstellung) = −3 (Dezimalsystem)

Eine andere Vorgehensweise zur Umwandlung einer Zahl in Zweierkomplementdarstellung in das Dezimalsystem ist die folgende: Habe die Zahl in Zweierkomplementdarstellung n Stellen, gegeben sind also n Bits a_{n − 1}a_{n − 2}a_{n − 3}...a₁a₀:

x_dezimal = − 2^{n − 1} * a_{n − 1} + 2^{n − 2} * a_{n − 2} + 2^{n − 3} * a_{n − 3} + ... + 2¹ * a₁ + 2⁰ * a₀

Formale Umwandlung aus dem Binärsystem

Ist x eine negative Zahl, so errechnet sich x in Zweierkomplementdarstellung (x_z) mit n Stellen wie folgt:

x_z = 2ⁿ − | x |

Dementsprechend gilt auch

x_z + | x | = 2ⁿ

wobei | x | der positiven Zahl entspricht und 2ⁿ bei der Rechnung als Übertrag in der (n + 1)-sten Stelle auftritt.

Formaler Hintergrund zu alternativen Wandlungen

Separate Interpretation des Vorzeichenbits

Folgende Umformungen zeigen, dass diese alternative Wandlung korrekt ist. Ist $x_z = ( x_{n-1}, x_{n-2}, \dots, x_1, x_0 )$ die Zweierkomplementdarstellung einer n-stelligen negativen Zahl x und $v = ( x_{n-2}, \dots, x_1, x_0 )$ der Suffix von x_z, so errechnet sich der Wert x wie folgt:

$\begin{align}x &= f_{ZK}\left( x_z \right) \\ &= f_{ZK}\left( (1 \cdot 2^{n-1} + v) \right) \\ &= - (\overline{v} + 1) \\ &= - ((2^{n-1} - 1) - v + 1) \\ &= v - 2^{n-1} \end{align}$

Hierbei ist f_ZK die Interpretationsfunktion, die den Zahlenwert einer Zweierkomplementzahl ermittelt. Die zweite Zeile ergibt sich aus der Definition einer negativen Zweierkomplementzahl und die dritte aus der Konversion in die positive Darstellung der Zweierkomplementzahl, wobei $\overline{v}$ das Komplement von v sein soll. Die vierte Zeile folgt dann daraus, dass die Komplementbildung auch als Subtraktion von einem Eins-String der Länge n − 1 (2^{n − 1} − 1) mit v dargestellt werden kann. Die letzte Zeile entspricht exakt der alternativen Wandlungsvorschrift und zeigt daher deren Korrektheit.

Subtraktion von der Wertebereichsgrenze

Die Korrektheit dieses Verfahrens ist leicht einsichtig, wenn man in Betracht zieht, in welcher Reihenfolge die Zahlenwerte im Raum der Bitstrings bei einer n-Bit-Zweierkomplementzahl verteilt sind:

$100 \dots 000 \rightarrow -2^{n-1}$

$100 \dots 001 \rightarrow -2^{n-1} + 1$

  $\dots$

$111 \dots 100 \rightarrow -4$

$111 \dots 101 \rightarrow -3$

$111 \dots 110 \rightarrow -2$

$111 \dots 111 \rightarrow -1$

D. h. durch die Subtraktion der Zahl $x \geq 1$ von der Wertebereichsgrenze 2ⁿ erhält man bei Rechnung im Binärsystem die Codierung von − x im Zweierkomplement.

Zweierkomplementdarstellung bei Festkommazahlen

Die Zweierkomplementdarstellung kann auch bei Festkommazahlen angewandt werden, womit beispielsweise gebrochene Zahlen wie $x=\tfrac{1}{4}$ binär dargestellt werden können. Festkommazahlen werden unter anderem im Bereich der digitalen Signalverarbeitung verwendet. Festkommazahlen werden allgemein durch ein Verschieben des Kommapunkts, 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 und anschließend der Wert einer Quantisierungsstufe 2^k addiert werden. Dabei gibt k die Position der letzten darstellbaren binären Ziffer an. Bei obigen Ganzzahlen wäre das die Stelle k=0, womit bei der Bildung des Zweikomplementes bei ganzen Zahlen nach der Invertierung der Wert 2⁰=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⁻²=0,25 addiert werden. (Hinweis: Der Kommapunkt kann bei Festkommazahlen auch außerhalb des darstellbaren Wertebereiches liegen.)

Ein Beispiel soll das 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,01₂. Wird nun das Zweierkomplement davon gebildet, werden alle Stellen der binären Zahl invertiert und 2⁻²=0,25 addiert, was 101,11₂ = −2,25 ergibt.

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 vereinbart sein kann.

Beschränkt man sich auf n-stellige Zahlen zur Basis b, dann kann man die natürlichen Zahlen von 0 bis bⁿ − 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 − bⁿ 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.

Siehe auch

• Einerkomplement

Literatur

• Ulrich Tietze, Christoph Schenk: Halbleiter-Schaltungstechnik. 12 Auflage. Springer, Berlin 2002, ISBN 3-540-42849-6.

Weblinks

• Ein Java-Applet zum Üben der binären Addition, dort das Register "konegative Zahlen" (benötigt Java)