Zweierkomplement

Das Zweierkomplement (auch 2-Komplement – verallgemeinert b-Komplement (b Basis) –, Zweikomplement, B(inär)-Komplement, Basiskomplement, two’s complement) ist eine Darstellungsweise für 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 Rechenart 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[1]
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 ${\displaystyle n}$ binären Stellen allgemein den Bereich (falls nicht anders definiert):

${\displaystyle -2^{n-1},\dotsc ,0,\dotsc ,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 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:

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)

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	10
1	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.

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	Summe
Bitfolge 00011010	0	0	0	1	1	0	1	0	+26
Bitfolge 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 ${\displaystyle \mathbb {Z} /256\mathbb {Z} }$. 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:

${\displaystyle -3\equiv 253\mod 256}$

${\displaystyle -7\equiv 249\mod 256}$

Multipliziert ergibt sich:

${\displaystyle -3\cdot -7\equiv 253\cdot 249\equiv 62997\equiv 21\mod 256}$

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 0
0:	0 0 0 0 0 0 0 0 0
1 subtrahieren:	0 0 0 0 0 0 0 0 1
Ergebnis:	1 1 1 1 1 1 1 1 1

Es ergibt sich also die Zweierkomplementdarstellung von −1 und auch das Carry Bit 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)

${\displaystyle 255-3+1=1+255-3=256-3}$

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 Carry Bit gesetzt, was eine negative Zahl anzeigt, und die Bitfolge 11111101, dies entspricht dezimal 253.

Weiter oben im Text wurde die Deutung des Carry-Bit als −256 vorgeschlagen. Diese findet sich übrigens auch bei Tietze/Schenck. Tatsächlich darf man im Restklassenring ${\displaystyle \mathbb {Z} /256\mathbb {Z} }$ 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 Carry-Bit 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 ${\displaystyle x_{z}=(x_{n-1},x_{n-2},\dotsc ,x_{1},x_{0})}$ die Binärdarstellung einer ${\displaystyle n}$-stelligen Zahl, so kann diese leicht von ${\displaystyle 2^{n}-1}$ abgezogen werden: ${\displaystyle 2^{n}-1}$ ist gerade ${\displaystyle n}$ mal hintereinander die Ziffer ${\displaystyle 1}$. Bei einer ziffernweisen Subtraktion stehen dort ausschließlich die Differenzen ${\displaystyle 1-1=0}$ oder ${\displaystyle 1-0=1}$. Es werden keine Überträge nötig, jede Ziffer darf isoliert betrachtet werden.

Tatsächlich heißt das aber, dass die Differenzbildung ${\displaystyle (2^{n}-1)-x_{z}}$ der bitweisen Komplementbildung von ${\displaystyle x_{z}}$ entspricht: ${\displaystyle (2^{n}-1)-x_{z}={\overline {x_{z}}}}$, dabei ist ${\displaystyle {\overline {x_{z}}}}$ das bitweise Komplement von ${\displaystyle x_{z}}$.

Im Restklassenring heißt das nichts anderes als:

${\displaystyle (2^{n}-1)-x_{z}\equiv {\overline {x_{z}}}(2^{n})}$

und damit

${\displaystyle -1-x_{z}\equiv {\overline {x_{z}}}(2^{n})}$

und nach Addition von 1 auf beiden Seiten:

${\displaystyle -x_{z}\equiv {\overline {x_{z}}}+1(2^{n})}$

Ganz allgemein lässt sich also das Vorzeichen von ${\displaystyle x_{z}}$ umkehren, indem im ersten Schritt ${\displaystyle x_{z}}$ bitweise zu ${\displaystyle {\overline {x_{z}}}}$ 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

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

* Übertrag

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 letzten 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 umcodieren 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 ${\displaystyle n}$ Stellen, gegeben sind also ${\displaystyle n}$ Bits ${\displaystyle a_{n-1}a_{n-2}a_{n-3}\ldots a_{1}a_{0}}$:

${\displaystyle x_{\text{dezimal}}=-2^{n-1}\cdot a_{n-1}+2^{n-2}\cdot a_{n-2}+2^{n-3}\cdot a_{n-3}+\dotsb +2^{1}\cdot a_{1}+2^{0}\cdot a_{0}}$

Formale Umwandlung aus dem Binärsystem

Ist ${\displaystyle x}$ eine negative Zahl, so errechnet sich ${\displaystyle x}$ in Zweierkomplementdarstellung (${\displaystyle x_{z}}$) mit ${\displaystyle n}$ Stellen wie folgt:

${\displaystyle x_{z}=2^{n}-|x|}$

Dementsprechend gilt auch

${\displaystyle x_{z}+|x|=2^{n}}$

wobei ${\displaystyle |x|}$ der positiven Zahl entspricht und ${\displaystyle 2^{n}}$ bei der Rechnung als Übertrag in der ${\displaystyle (n+1)}$-sten Stelle auftritt.

Formaler Hintergrund zu alternativen Wandlungen

Separate Interpretation des Vorzeichenbits

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

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

Hierbei ist ${\displaystyle 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 ${\displaystyle {\overline {v}}}$ das Komplement von ${\displaystyle v}$ sein soll. Die vierte Zeile folgt dann daraus, dass die Komplementbildung auch als Subtraktion von einem Eins-String der Länge ${\displaystyle n-1}$ (${\displaystyle 2^{n-1}-1}$) mit ${\displaystyle 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 ${\displaystyle n}$-Bit-Zweierkomplementzahl verteilt sind:

${\displaystyle {\begin{aligned}100\ldots 000&\rightarrow -2^{n-1}\\100\ldots 001&\rightarrow -2^{n-1}+1\\&\ \ \vdots \\111\ldots 100&\rightarrow -4\\111\ldots 101&\rightarrow -3\\111\ldots 110&\rightarrow -2\\111\ldots 111&\rightarrow -1\end{aligned}}}$

D. h. durch die Subtraktion der Zahl ${\displaystyle x\geq 1}$ von der Wertebereichsgrenze ${\displaystyle 2^{n}}$ erhält man bei Rechnung im Binärsystem die Codierung von ${\displaystyle -x}$ im Zweierkomplement.

Zweierkomplementdarstellung bei Festkommazahlen

Die Zweierkomplementdarstellung kann auch bei Festkommazahlen angewandt werden, womit beispielsweise gebrochene Zahlen wie ${\displaystyle 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 Zweikomplements 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 Zweierkomplements 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 ${\displaystyle n}$-stellige Zahlen zur Basis ${\displaystyle b}$, dann kann man die natürlichen Zahlen von 0 bis ${\displaystyle b^{n}-1}$ darstellen. Legt man eine Zahl in diesem Bereich als die größte positive Zahl fest, dann kann man jede größere Zahl ${\displaystyle x}$ als Zweierkomplementdarstellung der negativen Zahl ${\displaystyle x-b^{n}}$ auffassen.

Die Rechenoperation der Negation wird analog durchgeführt wie zur Basis 2: Jede Ziffer ${\displaystyle z}$ wird durch ${\displaystyle (b-1)-z}$ ersetzt, und zur so entstehenden Zahl wird 1 addiert.

Für die Basis ${\displaystyle b=5}$ und die Stellenzahl ${\displaystyle 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

• 2er Komplement zu Dezimalzahl, Dezimalzahl zu 2er Komplement – JavaScript Umrechner (beliebige Präzision)

Einzelnachweise

1. Herbert Schneider-Obermann: Basiswissen der Elektro-, Digital- und Informationstechnik. 1. Auflage. Friedr. Vieweg & Sohn Verlag / GWV Fachverlage GmbH, Wiesbaden 2006, ISBN 978-3-528-03979-0., Tabelle 2.1: „Negative Zahlen im Dualsystem“ in Abschnitt 2.1.5 „Darstellung negativer Zahlen im Dualsystem“