Einerkomplement
aus Wikipedia, der freien Enzyklopädie
Das Einerkomplement 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 NOT-Operation 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 X alle Bits löschen, die im Wert Y gesetzt sind, so muss man X mit dem Einerkomplement von Y logisch UND-verknüpfen.
Eine Anwendungsmöglichkeit für das Einerkomplement ist, 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.
Da bei binären Codierungen 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 erreicht, indem sämtliche Zahlen eine konstante Stellenzahl haben und bei Bedarf mit führenden Nullen aufgefüllt werden. Beim Einerkomplement wird das erste Bit zur Codierung des Vorzeichens verwendet und die n-1 folgenden zur Codierung der Zahl. Dabei werden bei positiven Zahlen führende Nullen und bei negativen Zahlen führende Einsen hinzugefügt. Die unten angeführten Beispiele verwenden je 7 Ziffern für die Codierung des Betrags und eine Ziffer für die Kodierung des Vorzeichens (das Beispiel ist also eine 8-bit- bzw. 1-Byte-Darstellung).
Verwendet man das Einerkomplement zur Codierung von Zahlen, so haben positive Zahlen immer eine führende 0 zur Codierung des Plus. Negative Zahlen werden durch Invertierung der entsprechenden positiven Zahl dargestellt und beginnen deshalb mit einer 1 zur Codierung des Minus.
Die Einerkomplement-Darstellung von Ganzzahlen zieht in den meisten Fällen erhebliche Probleme in der Implementierung einer Recheneinheit nach sich, deswegen wird sie nur noch selten verwendet. Geringe Vorteile hat sie nur bei der ohnehin meist langsamen Division sowie bei erweiterten Multiplikationen mit doppeltlangem Ergebnis.
Beispiel:
+410 = 00000100 −410 = 11111011 −110 = 11111110
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.
Beispiel:
−4 + 3 = −1 führt zu
11111011
+ 00000011
Übertrag 00000011
---------
= 11111110
Nachteil des Einerkomplements ist das Entstehen einer Redundanz: es existieren für die Null zwei Darstellungen: 00000000 (+0) und 11111111 (-0). 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 eine für den Zahlenraum weg) und verschiebt sich von [0 bis N] nach [- 0/2 N bis 0/2 N]. Die Darstellung jeder Zahl bleibt aber eineindeutig, da das 1. Bit ständig für das Vorzeichen reserviert ist. Dabei sollte man nie das Einerkomplement mit den Dualzahlen verwechseln, da sonst 1010 nicht -5 sondern die +10 darstellt. Das Problem der doppelten Darstellung der Null wird bei der Kodierung von Zahlen im Zweierkomplement, das auf dem Einerkomplement aufbaut, vermieden.
Darstellbare Zahlen:
0000 = +0 1111 = -0 0001 = +1 1110 = -1 0010 = +2 1101 = -2 0011 = +3 1100 = -3 0100 = +4 1011 = -4 0101 = +5 1010 = -5 0110 = +6 1001 = -6 0111 = +7 1000 = -7
Beispiel Codierung positive Zahl mittels Horner-Schema:
610 6/2 = 3 Rest 0 (Least-Significant-Bit - LSB) 3/2 = 1 Rest 1 1/2 = 0 Rest 1 (Most-Significant-Bit - MSB) es ergibt sich die Zahl 110= 0000.0110
Beispiel Codierung negative Zahl:
1. Invertierung der positiven
110->001
2. führende Einsen hinzufügen
1111.1001
Beispiel Addition:
+4 +(− 4) = 0 führt zu
00000100
+ 11111011
Übertrag 00000000
---------
= 11111111
Der Übertrag wird bei der Addition und Subtraktion auf die 1 weiter links stehende Ziffer addiert.
Beispiel Addition:
+10 +(- 3) = 7 führt zu
00001010
+ 11111100
Übertrag 11111000
---------
= 100000110 -> 9 belegte Stellen bei 8 möglichen -> End-Around-Carry tritt auf
Carry 1
---------
= 00000111
Tritt ein Übertrag am Most-Significant-Bit (dem 1.) auf, so wird der Übertrag als End-Around-Carry zum Least-Significant-Bit (dem letzten) addiert.
Aber auch weiterhin können Fehler bei der Addition auftreten.
Beispiel Überlauf:
0111 (+7)
+ 0111 (+7)
Übertrag 0111
-----
= 1110 (-1)
Erhält man die 1 als MSB bei Addition zweier positiver Zahlen, so tritt ein Überlauf auf.
Beispiel Überlauf
1011 (-5)
+ 1011 (-5)
Übertrag 1011
-----
= 0110
Carry 1
= 0111 (+7)
Beispiel kein Überlauf
1110 (-1)
+ 1110 (-1)
Übertrag 1110
-----
= 1100
Carry 1
= 1101 (-2)
Erhält man die 0 als MSB bei Addition zweier negativer Zahlen, so tritt ein Überlauf auf.
Sind beide Zahlen verschieden Vorzeichens, so tritt kein Überlauf ein.
