|
|
| Zeile 9: |
Zeile 9: |
| ===== Weblinks ===== | | ===== Weblinks ===== |
| # https://de.wikipedia.org/wiki/Einerkomplement | | # https://de.wikipedia.org/wiki/Einerkomplement |
|
| |
| = TMP =
| |
| Das '''Einerkomplement''', auch '''(''b''−1)-Komplement''',<ref>Helmut Herold: ''Grundlagen der Informatik''. Pearson Studium, München 2007, ISBN 978-3-8273-7305-2, S. 59</ref> ist eine arithmetische Operation, die meist im [[Dualsystem]] angewendet wird. Dabei werden alle [[Ziffer]]n bzw. [[Bit]]s einer [[Dualsystem|Binärzahl]] (Dualzahl) invertiert, das heißt: Aus <code>0</code> wird <code>1</code> und umgekehrt. Das hat zur Folge, dass jede Ziffer der Binärzahl und ihre korrespondierende Ziffer des Einerkomplements sich „zu <code>1</code> ergänzen“, was der Operation ihren Namen gibt. Ist also <math>z</math> eine {{nowrap|<math>n</math>-stellige}} Binärzahl, dann ist ihr Einerkomplement
| |
| : <math>(2^n\!-\!1) - z,</math>
| |
| eine [[Subtraktion#Schriftliche Subtraktion|Subtraktion]], bei der keine [[Übertrag|Überträge]] vorkommen. Die Operation wird auch als [[Bitweiser Operator#NICHT|bitweise Negation]] bezeichnet und der Operator in verschiedenen [[Programmiersprache]]n als Tilde <code>~</code> notiert. Dabei wird die Zahl als [[Bitkette]] aufgefasst.
| |
|
| |
| Eine Anwendung des Einerkomplements ist die gleichzeitige Manipulation einzelner Bits in einer Bitkette. Will man zum Beispiel in der Bitkette <code>Zahl</code> alle Bits löschen, die in der Bitkette <code>Maske</code> gesetzt sind, so kann man <code>Zahl</code> mit dem Einerkomplement von <code>Maske</code> bitweise [[Konjunktion (Logik)|UND-verknüpfen]], in [[C (Programmiersprache)|C]]-Syntax <code>Zahl &= ~Maske;</code>
| |
|
| |
| Eine andere Anwendung ist die '''Einerkomplementdarstellung''', ein Verfahren zur [[Dualsystem|binären]] Darstellung negativer [[Ganzzahlen]]. Zwar lässt sie sich leicht beschreiben – das Komplement der Darstellung einer negativen Zahl ist die normale Binärdarstellung ihres Betrags –, aber die Implementation einer [[Arithmetisch-logische Einheit|Recheneinheit]] für so dargestellte Zahlen ist umständlich. Vorteile gegenüber der heute üblichen [[Zweierkomplement]]-Darstellung hat sie nur bei der ohnehin meist langsamen Division, bei der Multiplikation mit doppelt langem Ergebnis sowie bei der Bildung einfacher [[Prüfsumme]]n.
| |
|
| |
| == Einerkomplementdarstellung ==
| |
| {| class="wikitable sortable float-right center" style="width: 20em; margin-left: 1em;"
| |
| |+ Vergleich der Darstellung eines [[Nibble]]s (4 Bit) als vorzeichenloser Wert (0's), als Betrag und Vorzeichen (BuV), im Einerkomplement (1'S) und im [[Zweierkomplement]] (2'S)
| |
| |-
| |
| !colspan="2"| Gespeicherter Wert !!colspan="4"| Dezimale Interpretation<ref>{{Literatur |Autor=Herbert Schneider-Obermann |Titel=Basiswissen der Elektro-, Digital- und Informationstechnik |Auflage=1. |Verlag=Friedr. Vieweg & Sohn Verlag / GWV Fachverlage |Ort=Wiesbaden |Datum=2006 |ISBN=3-528-03979-5}}, Tabelle 2.1: ''Negative Zahlen im Dualsystem'' in Abschnitt 2.1.5 ''Darstellung negativer Zahlen im Dualsystem''</ref>
| |
| |-
| |
| ! Bin !! Hex !! 0's !! BuV || 1'S !! 2'S
| |
| |-
| |
| | 0000 || 0 || 0 || 0 || 0 || 0
| |
| |-
| |
| | 0001 || 1 || 1 || 1 || 1 || 1
| |
| |-
| |
| | 0010 || 2 || 2 || 2 || 2 || 2
| |
| |-
| |
| | 0011 || 3 || 3 || 3 || 3 || 3
| |
| |-
| |
| | 0100 || 4 || 4 || 4 || 4 || 4
| |
| |-
| |
| | 0101 || 5 || 5 || 5 || 5 || 5
| |
| |-
| |
| | 0110 || 6 || 6 || 6 || 6 || 6
| |
| |-
| |
| | 0111 || 7 || 7 || 7 || 7 || 7
| |
| |-
| |
| | 1000 || 8 || 8 || −0 || −7 || −8
| |
| |-
| |
| | 1001 || 9 || 9 || −1 || −6 || −7
| |
| |-
| |
| | 1010 || A || 10 || −2 || −5 || −6
| |
| |-
| |
| | 1011 || B || 11 || −3 || −4 || −5
| |
| |-
| |
| | 1100 || C || 12 || −4 || −3 || −4
| |
| |-
| |
| | 1101 || D || 13 || −5 || −2 || −3
| |
| |-
| |
| | 1110 || E || 14 || −6 || −1 || −2
| |
| |-
| |
| | 1111 || F || 15 || −7 || −0 || −1
| |
| |}
| |
| Binäre Kodierungen vorzeichenbehafteter Ganzzahlen haben meist folgende Eigenschaften:
| |
| * verwendet wird eine konstante Anzahl ''n'' von [[Stellenwertsystem|Stellen]],
| |
| * das höchstwertige Bit ([[Bitwertigkeit|most significant bit]]) zeigt das [[Vorzeichen (Zahl)|Vorzeichen]] an: <code>0</code> für Plus, <code>1</code> für Minus,
| |
| * sie stimmen für positive Zahlen überein mit der vorzeichenlosen Darstellung, in der kleine Zahlen vorne mit Nullen ergänzt werden.
| |
| Unterschiede bestehen bei gesetztem höchstwertigen Bit. In diesem Fall ergibt sich bei der Einerkomplementdarstellung der Betrag durch Komplementbildung. Zum Beispiel erweist sich <code>1010</code> durch die führende <code>1</code> als negativ und der Betrag ist <code>~1010</code>, also <code>0101</code> = 5. Durch diese Definition ergeben sich folgende weitere Eigenschaften der Einerkomplementdarstellung:
| |
| * es existieren für die Zahl 0 zwei Darstellungen, +0 = <code>0000</code> und −0 = <code>1111</code>,
| |
| * positive und negative Zahlen reichen ''symmetrisch'' bis zum gleichen Betrag, hier 7 = <code>0111</code>.
| |
|
| |
| Die Beispiele sind hier für eine Wortbreite von ''n'' = 4 bit angegeben. Für 8 und 16 bit ergeben sich die Maximalbeträge 127 bzw. 32767, allgemein <math>2^{n-1}-1.</math>
| |
|
| |
| == Rechenoperationen und Probleme ==
| |
| Die in Einerkomplementdarstellung einfachste Rechenoperation ist die arithmetische Negation (unärer <code>-</code>-Operator). Es ist lediglich das bitweise Komplement zu bilden. Dadurch lässt sich die Subtraktion (binärer <code>-</code>-Operator) direkt auf die Addition zurückführen: 3 − 4 = 3 + (−4). Für die Durchführung dieser Addition ergibt ein für vorzeichenlose Zahlen konstruiertes [[Addierwerk]] das richtige Ergebnis:
| |
| 1011 (−4)
| |
| + 0011 (+3)
| |
| Überträge 0011
| |
| —————
| |
| = 1110 (−1)
| |
|
| |
| 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 Binärzahl-Addition der beiden Einerkomplementdarstellungen zunächst ein falsches Zwischenergebnis:
| |
|
| |
| −4 + 6 = +2 führt zu
| |
| 1011
| |
| + 0110
| |
| Überträge 1110
| |
| —————
| |
| = 0001 (Zwischenergebnis)
| |
|
| |
| Die <code>0001</code> stünde für +1, nicht für +2. Damit ein korrektes Ergebnis erscheint, muss der am weitesten links stehende Übertrag ausgewertet werden (hier <code>1</code>) 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 <code>0</code>, daher entspricht das Zwischenergebnis dort schon dem Endergebnis.
| |
|
| |
| Ein weiterer Nachteil ist das Entstehen einer [[Redundanz (Informationstheorie)|Redundanz]]: Es existieren für die Null zwei Darstellungen: <code>0000</code> (+0) und <code>1111</code> (−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 2<sup>4</sup> = 16 verschiedenen Bitkombinationen nur 15 verschiedene Zahlen (von −7 bis 7) dargestellt.
| |
|
| |
| Beide geschilderten Probleme werden bei der Kodierung von Zahlen in der [[Zweierkomplement]]darstellung vermieden.
| |
|
| |
| Das ''Hinzu<!-- Pleonasmus, „addieren“ geht nur mit „hinzu“ -->addieren des Übertrags'' verbessert die Empfindlichkeit einer einfachen [[Prüfsumme]] gegen mehrfache Bitfehler. So würde eine Prüfsumme mit der Überträge ignorierenden Modulo-Arithmetik mit einer Wahrscheinlichkeit von 50 % keinen Übertragungsfehler anzeigen, wenn das höchstwertige Bit oft falsch ist, z. B. konstant null. Das [[Transmission Control Protocol|TCP]] verwendet eine Prüfsumme in Einerkomplement-Arithmetik, die diesen Mangel nicht aufweist und deren effiziente Berechnung auf Hardware ohne Einerkomplement-Rechenwerk in <nowiki>RFC 1071</nowiki><ref>{{RFC-Internet |RFC=1071 |Titel=Computing the Internet Checksum |Datum=}}</ref> beschrieben ist.
| |
|
| |
| == Verallgemeinerung auf ''b''-adische Systeme ==
| |
| In einem {{nowrap|''b''-adischen}} System mit dem Standardziffernvorrat <math>\{0,1,\ldots,b\!-\!\!1\}</math> entspricht der binären Invertierung pro Ziffer <math>z</math> die Rechenvorschrift <math>\bar {z}~=~(b\!-\!\!1)-z</math>. Im Dezimalsystem mit {{nowrap|1=''b''=10}} muss also jede Ziffer von 9 abgezogen werden. Einige Autoren sprechen dann vom Neunerkomplement<ref>[https://www.rechnerlexikon.de/artikel/Neunerkomplement ''Neunerkomplement''.] Rechnerlexikon.de; abgerufen am 6. April 2015.</ref> und allgemein vom {{nowrap|(''b''−1)-Komplement.}} Beispielsweise ist das Neunerkomplement der dreistelligen Dezimalzahl <code>456<sub>dez</sub></code>
| |
| : <math>\begin{align}
| |
| \overline {456}_{\mathrm{dez}} & = ((9-4)(9-5)(9-6))_{\mathrm{dez}} \\
| |
| & = 543_{\mathrm{dez}} \\
| |
| & = 999_{\mathrm{dez}} - 456_{\mathrm{dez}}.
| |
| \end{align}</math>
| |
| Ist also <math>x</math> eine {{nowrap|<math>n</math>-stellige}} Dezimalzahl, dann ist ihr Neunerkomplement
| |
| : <math>(10^n\!-\!1) - x,</math>
| |
| eine [[Subtraktion#Schriftliche Subtraktion|Subtraktion]], bei der Überträge nicht vorkommen.
| |
|
| |
|
| [[Kategorie:Computerarithmetik]] | | [[Kategorie:Computerarithmetik]] |
| [[Kategorie:Zahlensystem]] | | [[Kategorie:Zahlensystem]] |
| </noinclude> | | </noinclude> |