Matthias Wimmer, Munich

Feeds

Search

Navigation

Über Matthias Wimmer

Links

Calendar

Freitag, 2000-02-11

Darstellung negativer Dualzahlen: Einer- und Zweierkomplement

Darstellung von ganzen Zahlen

In einer vorgegebenen Anzahl von Bits (meist 8 Bit, 16 Bit, 32 Bit) kann eine ganze Zahl in verschiedenen Weisen dargestellt werden. Drei davon haben wir davon in der Zentralübung kennengelernt. Es ist aus der Darstellung selbst (und damit dem Inhalt der Speicherzelle, des Registers oder wo auch immer die Zahl gerade steht) nicht ersichtlich welche Darstellung gewählt wurde.
Je nach gewählter Darstellung kann mit der vorgegebenen Anzahl von Bits ein verschiedener Wertebereich dargestellt werden.

Die nachfolgende Tabelle stellt für die kennengelernten Kodierungen dar, welches die größte und welches die kleinste darstellbare Zahl ist, wenn n Stellen (Bits) für die Zahl zur Verfügung stehen.

Darstellung kleinste Zahl größte Zahl
"normal" (vorzeichenlos) 0 2n-1
Einerkomplement -(2n-1-1) 2n-1-1
Zweierkomplement -(2n-1) 2n-1-1

Für gebräuchliche Stellenzahlen ergiben sich folgende Wertebereiche:

Stellenzahl Werteb. vorzeichenlos Werteb. Einerkompl. Werteb. Zweierkompl.
8 Stellen = 8 Bit = 1 Byte 0 ... 255 -127 ... 127 -128 ... 127
16 Stellen = 16 Bit = 1 Word 0 ... 65535 -32767 ... 32767 -32768 ... 32767
32 Stellen = 32 Bit = 1 Long Word 0 ... 4294967295 -214748363 ... 214748363 -214748364 ... 214748363

Vorzeichenlose Darstellung

Jede Stelle hat einen Stellenwert von 2n (n ... Nummer der Stelle von rechts an bei 0 beginnen gezählt).

Beispiel: 001001102 = 0*27 + 0*26 + 1*25 + 0*24 + 0*23 + 1*22 + 1*21 + 0*20 = 3810

Diese Darstellung ist die Darstellung, wie sie in Mathe schon häufiger gelehrt wurde, auch heute erst wieder in der HM1-Vorlesung.

Negative Zahlen: 1. Möglichkeit, das Einerkomplement

Diese Darstellung war wohl für die meisten von uns neu. Wir definieren hier, dass das Bit (die Binärstelle), die am weitesten links steht (das MSB, "Most Significant Bit") das Vorzeichen angibt. Eine Null hier kennzeichnet eine positive Zahl, eine Eins kennzeichnet eine negative Zahl.

Für Zahlen, deren linkestes Bit eine Null ist, ist diese Zahlendarstellung identisch mit der vorzeichenlosen Darstellung von oben. Ist das linkeste Bit dagegen eine Eins, so stellt die gleiche Ziffernfolge eine andere Zahl dar! (Vorzeichenlos wäre es eine (positive) Zahl in der oberen Hälfte des Wertebereichs, als Einerkomplement ist es eine negative Zahl.)

Um die Darstellung einer negativen Zahl im Einerkomplement zu erhalten, muss man sich die Binärdarstellung der dazugehörigen positiven Zahl überlegen und danach auf jeder "1" eine "0" und aus jeder "0" eine "1" machen. (Achtung! Dies geht nur, wenn wir eine vorgegebene Anzahl von Stellen haben, da wir auch führende Nullen der positiven Zahl zu einer "1" wandeln müssen.)

Beispiel (vom Übungsblatt): Um die Darstellung der Zahl -3810 im Einerkomplement zu finden, müssen wir uns erst die Darstellung von +3810 ausdenken. Wenn wir 8 Stellen für die Zahldarstellung wählen erhalten wir die Darstellung 001001102 für +38.
Die Darstellung von -38 im Einerkomplement ergibt sich nun durch Vertauschung von "0" und "1" (sogenannte "invertierung"): -3810 = 110110012.

Achtung! 110110012 stellt als Einerkomplement die Zahl -3810 dar, betrachten wir diese Bitfolge jedoch als vorzeichenlose Zahl, so stellt sie dagegen die Zahl 21710 dar.

Bei dieser Darstellung ergibt sich die Besonderheit, dass sowohl "alle Bits Null" als auch "alle Bits Eins" die Zahl "Null" darstellt. Nur das Vorzeichen ist verschieden, was bei "Null" jedoch ohne Bedeutung ist. Damit würde man (der Computer) wenn er +0 (lauter Nullen) mit -0 (lauter Einsen) vergleicht (uns diesen Fall nicht gesondert behandelt) die beiden (eigentlich identischen Zahlen) als verschieden betrachten. Deswegen wird die Einerkomplementdarstellung nicht wirklich benutzt, sondern man arbeitet in der Praxis mit der Zweierkomplementdarstellung (s.o.), bei der dieses Problem nicht auftritt.

Negative Zahlen: 2. Möglichkeit, das Zweierkomplement

Auch beim Zweierkomplement definiert man, dass das linkeste Bit wie beim Einerkomplement das Vorzeichen angibt. Wieder gilt für den Fall, dass dieses linkeste Bit eine "Null" ist, dass die Zahl identisch ist mit der Zahl der vorzeichenlosen Darstellung bei der gleichen Bitfolge. Ist das am weitesten links stehende Bit eine "0", so ist es also egal, ob wir die Zahl vorzeichenlos, als Einerkomplement oder als Zweierkomplement betrachten, da die Darstellungen identisch sind.
Für negative Zahlen (linkestes Bit eine "1") ist die Zahlendarstellung jedoch weder mit der vorzeichenlosen (hier gibt es ja gar keine negativen Zahlen) noch mit dem Einerkomplement identisch.
Wir erhalten die Zweierkomplementdarstellung von negativen Zahlen dadurch, dass wir zuerst das Einerkomplement bilden, dann jedoch noch binär eine Eins addieren.

Die folgende Tabelle stellt verschiedene Zahlen in den drei obigen Darstellungsvarianten dar (wir nehmen 8 Stellen für die Darstellung an):

Ziffernfolge Vorzeichenlos Einerkomplement Zweierkomplement
001001102 +3810 +3810 +3810
000000002 010 (+)010 010
111111112 25510 (-)010 -110
110110012 +21710 -3810 -3910
110100002 +20810 -4710 -4810
101010102 +17010 -8510 -8610

Der entscheidende Vorteil dieser Zweierkomplementdarstellung ist aber nicht, dass es nur eine mögliche Darstellung von "0" gibt (nämlich lauter Nullen, lauter Einsen stellen nun nichtmehr "-0" sondern "-1" dar), sondern dass der Computer mit den Zahlen rechnen kann als seien es vorzeichenlose positive Zahlen. Zur Veranschaulichung ein Beispiel:

Ziffernfolge vorzeichenlos interpretiert als 2er-Kompl. interpret.
001001102
+ 101010102
-----------
110100002
3810
+ 17010
------
20810
+3810
+ -8610
------
-4810

Man sieht daran, dass bei der Zweierkomplementdarstellung es dem Computer, der eine Summe bildet egal sein kann, dass es sich um eine Zweierkomplementdarstellung handelt. Er führt die gleiche Rechnung wie bei vorzeichenlosen Binärzahlen aus. Es ist wiederum einfach unsere Interpretation, ob wir die Zahl als vorzeichenlos oder als Zweierkomplement betrachten.
Haben wir die beiden Summanden zuvor vorzeichenlos betrachtet, so müssen wir auch die Summe als vorzeichenlos betrachten. Haben wir die beiden Summanden als Zweierkomplement betrachtet, so müssen wir auch die Summe als Zweierkomplement betrachten. Die Berechnung stimmt in beiden Fällen (solange wir den Wertebereich der angegebenen Stellenzahl nicht verlassen).

Carry-In und Carry-Out

Da das Ergebnis bei der Addition nur korrekt ist, wenn wir den Wertebereich nicht verlassen (unabhängig ob wir nun mit vorzeichenlosen Zahlen arbeiten oder nicht), müssen wir möglichst einfach erkennen können, ob ein Überlauf (= Verlassen des Wertebereiches) stattgefunden hat oder nicht.
Bei vorzeichenlosen Zahlen passiert eben dieser Überlauf, d.h. das Verlassen des Wertebereiches, wenn wir beim addieren der am weitesten links stehenden Stelle nochmals einen Übertrag haben. (Begründung: Wir müssten ja eigentlich nochmals eine Eins vor die Ziffernfolge des Ergebnisses schreiben, allerdings war in der fest vorgegebenen Anzahl von Stellen kein Platz mehr für diese Eins.) Dieser übertrag von der höchsten Stelle heraus in eine Stelle außerhalb ver vorgegebenen Stellenzahl heißt "Carry-Out".
Betrachten wir die dargestellten Zahlen jedoch nicht als vorzeichenlose Zahlen, sondern als Zweierkomplement, so haben wir durch Experiment festgestellt, dass ein Carry-Out noch keine Überschreitung des Wertebereiches darstellen muss (z.B. (-1)+(-1) = 111111112 + 111111112 = 111111102 = (-2) verursacht ein Carry-Out, ist jedoch korrekt und innerhalb des Wertebereiches).
Um das Verlassen des Wertebereiches zu erkennen, wenn wir die Zahl als Zweierkomplement betrachten, müssen wir zusätzlich das "Carry-In" definieren. Das Carry-In ist ein ggf. auftretender Übertrag von der zweiten Stelle von links in die am weitesten links stehende Stelle. (Carry-In: "in die linkeste Stelle hinein" / Carry-Out: "aus der linkesten Stelle heraus").
Ohne Beweis aber durch Experiment haben wir nun gesehen, dass der Wertebereich beim Zweierkomplement immer dann verlassen wird, wenn das Carry-In ungleich dem Carry-Out ist.

Nachtrag über den Zusammenhang zwischen Carry-In und -Out und den Prozessorflags des 80x86.

(Keine Gewähr für die Richtigkeit der Angaben.)

Metadata

Ping: https://matthias.wimmer.name/mawis/entry/Zweierkomplement

Title: Darstellung negativer Dualzahlen: Einer- und Zweierkomplement

ID: https://matthias.wimmer.name/mawis/entry/Zweierkomplement

Subject: cs

Description: Darstellung negativer Dualzahlen: Einer- und Zweierkomplement

Creator: Matthias Wimmer

Date: 2000-02-11 00:00:00.0'

Kommentare:

Senden Sie einen Kommentar:
  • HTML Syntax: Ausgeschaltet