4.4 Zweierkomplement

Negative Zahlen ohne separates Minuszeichen

Ein Computer speichert in einem Bitmuster kein typografisches Minuszeichen. Für ganze Zahlen muss daher festgelegt werden, wie negative Werte codiert werden. Das heute übliche Zweierkomplement hat einen entscheidenden Vorteil: Dieselbe binäre Additionsschaltung funktioniert für positive und negative Zahlen.

Definition 4.3 (Zweierkomplementdarstellung). Das \(n\)-Bit-Muster \(x_{n-1}\ldots x_0\) besitzt im Zweierkomplement den Wert

\[ (x_{n-1}\ldots x_0)_{2K} =-x_{n-1}2^{n-1}+\sum_{j=0}^{n-2}x_j2^j. \]

Der Index \(2K\) kennzeichnet die Deutung der Bitfolge im Zweierkomplement.

Das MSB hat damit das negative Gewicht \(-2^{n-1}\); die übrigen Bits behalten ihre positiven Gewichte.

Das negative Gewicht des höchsten Bits verschiebt den darstellbaren Bereich zu negativen Zahlen.

Mit \(n\) Bits sind genau die ganzen Zahlen

\[ -2^{n-1},\ldots,-1,0,1,\ldots,2^{n-1}-1 \]

darstellbar.

Für \(n=8\) reicht der Bereich daher von \(-128\) bis \(127\). Bitmuster mit MSB \(0\) sind nichtnegativ, Bitmuster mit MSB \(1\) sind negativ.

Die Zuordnung zwischen einer Zahl und dem Speicherwert ihres Bitmusters lässt sich für drei Bits vollständig darstellen.

Zahlen minus 4 bis 3 und Speicherwerte 0 bis 7: Negative Zahlen werden auf ihren Wert plus 8 abgebildet, nichtnegative Zahlen auf denselben Wert.

Negative Zahlen ins Zweierkomplement umrechnen

Für \(-a<0\) mit \(1\le a\le 2^{n-1}\) gibt es zwei Methoden. Beide liefern dieselbe Darstellung mit \(n\) Bits:

  1. Über den Speicherwert: Wir berechnen \(2^n-a\) und schreiben das Ergebnis mit genau \(n\) Binärziffern. Diese Bitfolge stellt \(-a\) im Zweierkomplement dar.

  2. Mit der Bitregel: Wir schreiben zunächst \(a\) mit \(n\) Bits. Von rechts übernehmen wir alle Bits bis einschließlich der ersten \(1\) unverändert. Alle Bits links davon werden invertiert: Aus \(0\) wird \(1\) und aus \(1\) wird \(0\).

An derselben Zahl können wir vergleichen, wie beide Methoden zum gleichen Bitmuster führen.

Beispiel: \(-100\) mit beiden Methoden codieren

Wir stellen \(-100\) mit acht Bits im Zweierkomplement dar.

  1. Über den Speicherwert: Wir berechnen \[ 2^8-100=156,\qquad (156)_{10}=(10011100)_2. \] Damit gilt \((-100)_{10}=(10011100)_{2K}\).
  2. Mit der Bitregel: Die positive Gegenzahl besitzt die Darstellung \[ (100)_{10}=(01100100)_2. \] Von rechts übernehmen wir \(\mathtt{100}\) bis einschließlich der ersten \(1\). Die fünf Bits \(\mathtt{01100}\) links davon werden zu \(\mathtt{10011}\) invertiert. Zusammengesetzt ergibt sich erneut \[ (-100)_{10}=(10011100)_{2K}. \]

Bitfolgen im Zweierkomplement lesen

Bei MSB \(0\) hat die Bitfolge denselben Wert wie eine gewöhnliche Binärzahl. Bei MSB \(1\) lesen wir zunächst ihren gewöhnlichen Binärwert und ziehen anschließend \(2^n\) ab.

Beispiel: Ein negatives Bitmuster lesen

Welchen Wert besitzt \((1010110)_{2K}\) bei sieben Bits?

Das MSB ist \(1\). Als gewöhnliche Binärzahl gelesen ergibt die Folge

\[ (1010110)_2=2^6+2^4+2^2+2^1=86. \]

Im Zweierkomplement ziehen wir \(2^7=128\) ab:

\[ (1010110)_{2K}=86-128=(-42)_{10}. \]

Addition im Zweierkomplement

Positive und negative Zahlen lassen sich direkt als Bitmuster addieren. Wir führen dies für \(64+(-100)\) aus.

Beispiel. Mit acht Bits berechnen wir \(64-100=64+(-100)\). Die Summanden sind \((64)_{10}=(01000000)_{2K}\) und \((-100)_{10}=(10011100)_{2K}\):

\[ \begin{array}{c@{}r} &01000000\\ +&10011100\\ \hline &11011100 \end{array} \]

Das Ergebnis ist negativ. Negieren von 11011100 liefert 00100100, also \(36\). Somit gilt \((11011100)_{2K}=(-36)_{10}\).

Ein rechnerisch korrektes Ergebnis kann außerhalb des speicherbaren Bereichs liegen; dafür brauchen wir ein Überlaufkriterium.

Bemerkung: Überlauferkennung bei der Addition

Bei der Addition zweier \(n\)-Bit-Zahlen im Zweierkomplement liegt genau dann ein Überlauf vor, wenn beide Summanden dasselbe Vorzeichen besitzen, das gespeicherte Ergebnis aber das entgegengesetzte Vorzeichen hat.

\[ \begin{array}{c|c|c|c} \operatorname{MSB}(a)&\operatorname{MSB}(b)&\operatorname{MSB}(a+b)&\text{Bewertung}\\ \hline 0&0&1&\text{Überlauf}\\ 1&1&0&\text{Überlauf} \end{array} \]

Ein Übertrag links neben das MSB ist bei Zweierkomplementzahlen allein kein zuverlässiges Überlaufkriterium. Entscheidend sind die Vorzeichen der Summanden und des gespeicherten Ergebnisses.

Zusammenfassung

  • Im Zweierkomplement besitzt das MSB das Gewicht \(-2^{n-1}\).
  • Mit \(n\) Bits reicht der Wertebereich von \(-2^{n-1}\) bis \(2^{n-1}-1\).
  • Für \(-a\) berechnet man \(2^n-a\) oder übernimmt die Bits von rechts bis zur ersten \(1\) und invertiert alle Bits links davon.
  • Bei MSB \(1\) ist der Zweierkomplementwert der gewöhnliche Binärwert minus \(2^n\).
  • Gleiche Vorzeichen der Summanden und ein anderes Vorzeichen des Ergebnisses kennzeichnen einen Überlauf.