Das Zweierkomplement und der Grund dafür

In diesem Artikel soll es um die Details gehen, wie man ganze Zahlen (sowohl positiv also auch negativ) binär darstellt.

Binäre Zahlen bestehen nur aus 1 und 0, dass sollte allgemein bekannt sein. Das erste Bit einer Zahl wird auch als most significant bit (msb) bzw. das Letzte least significant bit (lsb) bezeichnet.

Natürliche Zahlen

Stellen wir zuerst nur positive Zahlen binär dar. Das ist relativ einfach, denn die Wertigkeit der Bits steigt, je weiter man nach Links geht.
Sehen wir uns als Beispiel die Zahlen $5_{10}$ und $12_{10}$ an (N ist die Nummer des Bits):

Dezimal Binär
+5 0 1 0 1
+12 1 1 0 0

N 4 3 2 1
Wertigkeit 2^3 2^2 2^1 2^0

Die Wertigkeit eines Bits ist also immer die
2 hoch die Bitnummer – 1, mathematisch ausgedrückt: $2^{N-1}$ . Wenn wir jetzt den Wert einer binären Zahl im Dezimalsystem ausrechnen wollen, multiplizieren wir einfach den binären Wert mit der jeweiligen Wertigkeit:
$0101_2 = 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 5_{10}$
$1100_2 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0 = 12_{10}$

Der Wertebereich für positive Binärzahlen sieht also folgendermaßen aus: $2^N-1$
N ist die Anzahl der Bits, dh. mit einer 4Bit Zahl können wir max. bis $2^4-1 = 15_{10}$ zählen, weil die 0 als erster Wert zählt (also können wir von $0 - 15$ zählen).

Die mathematische Formel um den Wert einer nur-positiven Binärzahl auszurechen:
$A: \{a_{n-1}, a_{n-2}, ..., a_1, a_0\}$
$A = \sum_{i=0}^{n-1} a_i 2^i$

Darstellung mit Vorzeichen und Betrag

Im Dezimalsystem ist eine negative Zahl das gleiche wie eine Positive bloß mit einem Minus vor der Zahl und natürlich dem (negativem) Wert. Im Binärsystem könnte (und kann) man das ähnlich regeln. Gehen wir von einer Zahl mit fixer Länge von 4Bit und dem Wert $5_{10}$ aus. Wenn wir diese Zahl negativ darstellen wollen, könnten wir einfach das msb reservieren. Ist es 1, interpretieren wir den Wert der Zahl als negativ; ist es 0 ist die Zahl positiv:

Dezimal Binär
+5 = 0101
-5 = 1101

Damit ändert sich aber der Wertebereich der Zahl, denn es steht ein Bit weniger zur freien Verfügung:
$[-(2^{N-1}-1) ; 2^{N-1}-1]$

Das Problem dieser Darstellungsform ist, dass es 2 Möglichkeiten gibt, eine $0_{10}$ darzustellen:

Dezimal Binär
+0 = 0000
-0 = 1000

Auch deshalb funktioniert die gewohnte (und einfache) Addition nicht mehr. Dieses Problem in einem Mikrochip zu umgehen ist sehr aufwendig und bei weitem nicht so schnell wie wenn man binäre Zahlen als Zweierkomplement kodieren würde; das ist der Grund warum sich – zumindest im IT Bereich – das Zweierkomplement durchgesetzt hat.

Die mathematische Formel um den Wert auszurechen:
$A: \{a_{n-1}, a_{n-2}, ..., a_1, a_0\}$
$A = (-1)^{a_{n-1}} \sum_{i=0}^{n-2} a_i 2^i$

Das legendäre Zweierkomplement

Das Zweierkomplement behebt alle diese Probleme. Ich persönlich finde das Zweierkomplement genial, es ergibt eine gleichmäßige Linie – ohne Ecken und Kanten (oder Workarounds) – und macht sich im weiterem Verlauf sehr bezahlt.

Zur besseren Visualisierung möchte ich einfach mal alle Werte einer 4Bit Zahl vorgeben:

Dezimal Binär
+7 = 0111
+6 = 0110
+5 = 0101
+4 = 0100
+3 = 0011
+2 = 0010
+1 = 0001
----------------
+0 = 0000
----------------
-1 = 1111
-2 = 1110
-3 = 1101
-4 = 1100
-5 = 1011
-6 = 1010
-7 = 1001
-8 = 1000

Das msb zeigt nach wie vor an, ob die Zahl negativ oder positiv ist. Im positiven Bereich ist alles gleich geblieben, allerdings hat sich einiges im negativen Bereich geändert.

Der Wertebereich sieht demnach folgendermaßen aus:
$[-(2^{N-1}) ; 2^{N-1}-1]$

Die mathematische Formel um den Wert eines Zweierkomplements auszurechen:
$A: \{a_{n-1}, a_{n-2}, ..., a_1, a_0\}$
$A = a_{n-1}(-2^{n-1}) + \sum_{i=0}^{n-2} a_i 2^i$

Von der Zahl zum Zweierkomplement

Will man eine positive Zahl im Zweierkomplement darstellen muss man nur darauf achten dass das msb 0 ist. Bei einer negativen Zahl muss es demnach 1 sein. Danach rechnet man den Wertebereich (ohne msb) aus und subtrahiert die darzustellende Zahl vom Wertebereich. Das Ergebnis muss nun einfach binär an das msb angehangen werden.
Beispiel mit einer 5Bit Zahl -5 darstellen:
$2^4 - 5 = 16 - 5 = 11_{10} = 1011_2$
Schlussendlich noch das msb anhängen, das 1 sein muss, weil es sich um eine negative Zahl handelt. -5 lautet also als Zweierkomplement 11011.

Es gibt noch eine andere und vor allem schnellere Methode um den Wert auszurechnen. Dazu muss man alle Bits invertieren und 1 zum Ergebnis addieren. Danach hat man eine positive Zahl mit dem Betragswert der negativen Zahl. Das Verfahren funktioniert in beide Richtungen, also vom positivem zum negativem Wert als auch vom negativem zum positivem Wert.
Beispiel mit der Zahl $11011_2$ :

Invertieren: 11011 -> 00100
1 addieren: 00100 -> 00101 (= $5_{10}$ )

Eine kleine Anmerkung gibt es allerdings noch: Wenn man (wie gewohnt) eine positive und negative Zahl als Zweierkomplement addiert, kann es vorkommen dass man bei der Addition des msb noch einen Übertrag erhält. Diesen kann man einfach ignorieren!

0101
+ 1110
------
0011

Eigentlich müsste das Ergebnis 10011 lauten, aber da die Zahl aus nur 4 Bits besteht kann man das 5. (bzw. das neue msb) ignorieren.

Schlagworte: Addition, Darstellung, lsb, msb, negativ, positiv, Zahlen, Zweierkomplement

Dieser Beitrag wurde vor am Samstag, 17. Oktober 2009 um 21:40 Uhr veröffentlicht und unter TGdI1+2 gespeichert. Sie können Kommentare zu diesem Eintrag über den RSS-2.0-Feed verfolgen. Sie können einen Kommentar hinterlassen oder einen Trackback von Ihrer Website hierher setzen.

brianp.de