„Einerkomplement“ – Versionsunterschied
[gesichtete Version] | [ungesichtete Version] |
Sitic (Diskussion | Beiträge) erg. & interwikilinks entfernt, sind in wikidata |
|||
Zeile 4: | Zeile 4: | ||
== Motivation == |
== Motivation == |
||
'''Hier ergibt 1111 1111 = -1!''' |
|||
{|class="wikitable" style="float:right; width: 20em; margin-left: 1em; text-align:center" |
{|class="wikitable" style="float:right; width: 20em; margin-left: 1em; text-align:center" |
||
|+ 8-Bit Einerkomplement |
|+ 8-Bit Einerkomplement |
Version vom 18. Oktober 2013, 11:11 Uhr
Das Einerkomplement, auch (B-1)-Komplement[1], ist eine arithmetische Operation auf Dualzahlen. Dabei werden alle Ziffern bzw. Bits invertiert, das heißt aus 0 wird 1 und umgekehrt. Dieses wird auch als arithmetische Nicht-Verknüpfung bezeichnet. In den Programmiersprachen C, C++, C#, Perl, PHP oder Java wird diese Operation mit dem Symbol ~
dargestellt. Das Einerkomplement ist insbesondere dann von Bedeutung, wenn man einzelne Bits manipulieren will. Will man zum Beispiel in dem Wert alle Bits löschen, die im Wert gesetzt sind, so muss man mit dem Einerkomplement von bitweise und-verknüpfen.
Eine Anwendungsmöglichkeit für das Einerkomplement ist die Einerkomplementdarstellung, ein Verfahren, um negative Zahlen im Binärsystem darzustellen, ohne auf zusätzliche Symbole wie + und − angewiesen zu sein. Dies ist vor allem für Computer wichtig, deren Logik allein auf Bits ausgerichtet ist, das heißt, Folgen von 0 und 1. Die Einerkomplementdarstellung von Ganzzahlen zieht in den meisten Fällen erhebliche Probleme in der Implementierung einer Recheneinheit nach sich, weswegen sie nur noch selten verwendet wird. Geringe Vorteile hat sie nur bei der ohnehin meist langsamen Division sowie bei erweiterten Multiplikationen mit doppeltlangem Ergebnis.
Motivation
Hier ergibt 1111 1111 = -1!
Binärwert | Interpretation als Einerkomplement | Interpretation als vorzeichenlose Zahl |
---|---|---|
00000000 | +0 | 0 |
00000001 | 1 | 1 |
... | ... | ... |
01111101 | 125 | 125 |
01111110 | 126 | 126 |
01111111 | 127 | 127 |
10000000 | −127 | 128 |
10000001 | −126 | 129 |
10000010 | −125 | 130 |
... | ... | ... |
11111101 | −2 | 253 |
11111110 | −1 | 254 |
11111111 | −0 | 255 |
Da bei binären Kodierungen von negativen Zahlen sowohl Vorzeichen als auch die eigentliche Zahl durch Bits dargestellt werden, ist es wichtig zu wissen, welches Bit wofür verwendet wird. Im Binärsystem wird dies normalerweise erreicht, indem sämtliche Zahlen eine konstante Stellenzahl haben und bei Bedarf mit führenden Nullen aufgefüllt werden. Bei der Einerkomplementdarstellung wird das erste Bit eines n-Bit-Datenworts zur Kodierung des Vorzeichens verwendet und die n−1 folgenden zur Kodierung der Zahl. Dabei werden positiven Zahlen führende Nullen, negativen hingegen führende Einsen hinzugefügt.
Verwendet man die Einerkomplementdarstellung zur Kodierung von Zahlen, so haben positive Zahlen immer eine führende 0
zur Kodierung des Plus. Negative Zahlen werden durch Negation des kompletten Bitmusters der entsprechenden positiven Zahl dargestellt und beginnen deshalb mit einer 1
zur Kodierung des Minus. Das erste Bit ist also für das Vorzeichen reserviert. Es sollte nie eine Einerkomplementdarstellung mit einer vorzeichenlosen Dualzahl verwechselt werden; beispielsweise repräsentiert 1010
im ersten Fall −5, während im letzteren Fall +10 gemeint ist.
Das größte Problem der Einerkomplementdarstellung (und gleichzeitig der Hauptunterschied zur verwandten Zweierkomplementdarstellung) ist, dass für die Zahl 0 zwei Darstellungen existieren: einmal mit negativem und einmal mit positiven Vorzeichen. Der Wertebereich der Einerkomplementdarstellung umfasst bei n binären Stellen allgemein den symmetrischen Bereich
Beispiele:
bei 8 Bit: −127(10) bis +127(10) bei 16 Bit: −32767(10) bis +32767(10) bei 32 Bit: −2147483647(10) bis +2147483647(10) bei 64 Bit: −9223372036854775807(10) bis +9223372036854775807(10)
Rechenoperationen und Probleme
Die unten angeführten Beispiele verwenden je drei Ziffern für die Kodierung des Betrags und eine Ziffer für die Kodierung des Vorzeichens (das Beispiel ist also eine 4-Bit- bzw. 1-Nibble-(Halbbyte)-Darstellung). Darstellbare Zahlen bei einer Wortlänge von 4 Bit:
0000
= +0101111
= −0100001
= +1101110
= −1100010
= +2101101
= −2100011
= +3101100
= −3100100
= +4101011
= −4100101
= +5101010
= −5100110
= +6101001
= −6100111
= +7101000
= −710
Durch die Negation kann eine Fallunterscheidung für positive und negative Zahlen entfallen: Um −4 + 3 = −1 darzustellen, müssen nur die entsprechenden Zahlen addiert werden. Die Addition erfolgt durch Addition der Einerkomplementdarstellungen als vorzeichenlose Dualzahlen.
Beispiel:
−4 + 3 = −1 führt zu 1011 + 0011 Übertrag 0011 ————— = 1110
Nachteil der Einerkomplementdarstellung ist die Behandlung des Falls, wenn bei einer Operation die Null durchschritten wird. Beispiel: Beim Berechnen von −4 + 6 = +2 erscheint nach einer einfachen Dualzahl-Addition der beiden Einerkomplementdarstellungen zunächst ein falsches Zwischenergebnis:
−4 + 6 = +2 führt zu 1011 + 0110 Übertrag 1110 ————— = 0001 (Zwischenergebnis)
Die 0001
stünde für +1, nicht für +2. Damit ein korrektes Ergebnis erscheint, muss der am weitesten links stehende Übertrag ausgewertet werden (hier 1
) und ggf. das Ergebnis um 1 erhöht werden. Mit anderen Worten muss der Übertrag noch zum Zwischenergebnis hinzuaddiert werden:
0001 (Zwischenergebnis) + 1 (Übertrag der vorhergehenden Operation) ————— = 0010
Beim ersten Beispiel oben ist der Übertrag 0
, daher entspricht das Zwischenergebnis dort schon dem Endergebnis.
Ein weiterer Nachteil ist das Entstehen einer Redundanz: Es existieren für die Null zwei Darstellungen: 0000
(+0) und 1111
(−0), siehe vorzeichenbehaftete Null. Zum einen wird bei einer begrenzten Anzahl von Bits nicht die maximale Ausdehnung des Betrags der darstellbaren Zahlen ausgenutzt. Der darstellbare Zahlenraum verringert sich um 1; da die Null zweimal vorhanden ist, fällt ein Datenwort für den Zahlenraum weg. Die Darstellung jeder anderen Zahl bleibt aber eindeutig. Im Beispiel hier mit 4 Bits werden mit den 24 = 16 verschiedenen Bitkombinationen nur 15 verschiedene Zahlen (von −7 bis 7) dargestellt.
Beide geschilderten Probleme werden bei der Kodierung von Zahlen in der Zweierkomplementdarstellung, die auf der Einerkomplementdarstellung aufbaut, vermieden.
Weiterführende Informationen
- John Walker: Minus Zero, UNIVAC Memories – Einerkomplement auf UNIVAC 1100 Computern (englisch)
Einzelnachweise
- ↑ Helmut Herold: Grundlagen der Informatik. Pearson Studium, München 2007, ISBN 978-3-8273-7305-2, S. 59