imported>Daniel5Ko: Die letzte Textänderung von ~2025-111413 wurde verworfen und die Version 247905480 von Daniel5Ko wiederhergestellt. ??

2025-07-05T23:54:35Z

Die letzte Textänderung von ~2025-111413 wurde verworfen und die Version 247905480 von Daniel5Ko wiederhergestellt. ??

Neue Seite

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 ''Hinzuaddieren 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.

== Weblinks ==
* [[John Walker (Programmierer)|John Walker]]: [https://www.fourmilab.ch/documents/univac/minuszero.html ''Minus Zero''.] UNIVAC Memories – Einerkomplement auf [[Universal Automatic Calculator|UNIVAC]] 1100 Computern. fourmilab.ch (englisch)

== Einzelnachweise ==
<references />

[[Kategorie:Computerarithmetik]]
[[Kategorie:Zahlensystem]]

Einerkomplement - Versionsgeschichte

imported>Daniel5Ko: Die letzte Textänderung von ~2025-111413 wurde verworfen und die Version 247905480 von Daniel5Ko wiederhergestellt. ??