Zahlendarstellungen mit Vorzeichen - Signed number representations

Beim Rechnen werden vorzeichenbehaftete Zahlendarstellungen benötigt, um negative Zahlen in binären Zahlensystemen zu codieren .

In der Mathematik werden negative Zahlen in jeder Basis dargestellt, indem ihnen ein Minuszeichen ("−") vorangestellt wird. In Computerhardware werden Zahlen jedoch nur als Bitfolgen ohne zusätzliche Symbole dargestellt. Die vier bekanntesten Verfahren zum Erweitern des binären Zahlensystems zur Darstellung von Zahlen mit Vorzeichen sind: Vorzeichen und Betrag , Einerkomplement , Zweierkomplement und Offset-Binär . Einige der alternativen Methoden verwenden implizite anstelle von expliziten Vorzeichen, z. B. negative Binärzeichen mit der Basis −2 . Entsprechende Methoden können für andere Grundlagen entwickelt werden , seien es positive, negative, gebrochene oder andere Ausarbeitungen zu solchen Themen.

Es gibt kein definitives Kriterium, nach dem eine der Darstellungen allgemein überlegen ist. Für Ganzzahlen ist die in den meisten aktuellen Computergeräten verwendete Darstellung das Zweierkomplement, obwohl die Mainframes der Unisys ClearPath Dorado-Serie das Einerkomplement verwenden.

Geschichte

Die Anfänge des Digital Computing waren geprägt von vielen konkurrierenden Ideen sowohl in der Hardwaretechnologie als auch in der Mathematiktechnologie (Nummerierungssysteme). Eine der großen Debatten war das Format der negativen Zahlen, einige der Top-Experten der Ära hatten sehr starke und unterschiedliche Meinungen. Ein Lager unterstützte das Zweier-Komplement , das heute vorherrschende System. Ein anderes Lager unterstützte das Einerkomplement, bei dem jeder positive Wert in sein negatives Äquivalent umgewandelt wird, indem alle Bits in einem Wort invertiert werden. Eine dritte Gruppe unterstützte "Vorzeichen und Größe" (Vorzeichen-Betrag), wobei ein Wert einfach durch Umschalten des Vorzeichen-Bits (höherer Ordnung) des Wortes von positiv auf negativ geändert wird.

Es gab Argumente für und gegen jedes der Systeme. Vorzeichen und Größe ermöglichten eine einfachere Verfolgung von Speicherabbildern (ein üblicher Prozess in den 1960er Jahren), da kleine numerische Werte weniger 1 Bit verwenden. Intern führten diese Systeme eine Komplement-Mathematik durch, so dass Zahlen bei der Übertragung von einem Register an die mathematische Einheit in Einser-Komplementwerte umgewandelt und dann wieder in Vorzeichen-Größe umgewandelt werden mussten, wenn das Ergebnis zurück an das Register übertragen wurde. Die Elektronik benötigte mehr Gates als die anderen Systeme – ein zentrales Anliegen, wenn die Kosten und das Gehäuse von diskreten Transistoren kritisch waren. IBM war einer der frühen Befürworter von Sign-Magnitude, wobei die Computer der Serien 704 , 709 und 709x vielleicht die bekanntesten Systeme sind, die es verwenden.

Das Einser-Komplement ermöglichte etwas einfachere Hardware-Designs, da die Werte bei der Übergabe an und von der mathematischen Einheit nicht konvertiert werden mussten. Aber es teilte auch eine unerwünschte Eigenschaft mit Vorzeichen-Größe – die Fähigkeit, negative Null (−0) darzustellen . Eine negative Null verhält sich genau wie eine positive Null; Bei Verwendung als Operand in einer beliebigen Berechnung ist das Ergebnis gleich, egal ob ein Operand positiv oder negativ Null ist. Der Nachteil besteht jedoch darin, dass die Existenz von zwei Formen mit dem gleichen Wert zwei statt eines einzigen Vergleichs erfordert, wenn auf Gleichheit mit Null geprüft wird. Die Subtraktion des Einerkomplements kann auch zu einem End-Around-Borrow führen (unten beschrieben). Es kann argumentiert werden, dass dies die Additions-/Subtraktionslogik komplizierter oder einfacher macht, da eine Subtraktion einfach das Invertieren der Bits des zweiten Operanden erfordert, wenn er an den Addierer übergeben wird. Die PDP-1 , CDC 160-Serie , CDC 3000- Serie, CDC 6000-Serie , UNIVAC 1100- Serie und der LINC- Computer verwenden die Einser-Komplement-Darstellung.

Das Zweier-Komplement ist am einfachsten in Hardware zu implementieren, was der ultimative Grund für seine weit verbreitete Popularität sein könnte. Prozessoren auf den frühen Mainframes bestanden oft aus Tausenden von Transistoren – der Wegfall einer erheblichen Anzahl von Transistoren war eine erhebliche Kosteneinsparung. Großrechner wie das IBM System/360 , die GE-600-Serie und die PDP-6 und PDP-10 verwenden das Zweierkomplement, ebenso wie Minicomputer wie die PDP-5 und PDP-8 und die PDP-11 und VAX . Die Architekten der frühen CPUs auf Basis integrierter Schaltkreise ( Intel 8080 usw.) entschieden sich für die Zweierkomplement-Mathematik. Als sich die IC-Technologie weiterentwickelte, übernahmen praktisch alle die Zweier-Komplement-Technologie. x86- , m68k- , Power ISA- , MIPS- , SPARC- , ARM- , Itanium- , PA-RISC- und DEC-Alpha- Prozessoren sind allesamt zweierlei.

Vorzeichenbehaftete Größendarstellung

Diese Darstellung wird auch als "Vorzeichen-Größe"- oder "Vorzeichen- und Betrags"-Darstellung bezeichnet. Bei diesem Ansatz wird das Vorzeichen einer Zahl durch ein Vorzeichenbit dargestellt : Setzen dieses Bits (oft das höchstwertige Bit ) auf 0 für eine positive Zahl oder positive Null und Setzen auf 1 für eine negative Zahl oder negative Null. Die verbleibenden Bits in der Zahl geben die Größe (oder den Absolutwert ) an. In einem 8-Bit- Byte stellen beispielsweise nur sieben Bits die Größe dar, die von 0000000 (0) bis 1111111 (127) reichen kann. Somit können Zahlen im Bereich von -127 ₁₀ bis +127 ₁₀ dargestellt werden, sobald das Vorzeichenbit (das achte Bit) hinzugefügt wird. Zum Beispiel, -43 ₁₀ in einem Acht-Bit - Byte codiert ist 1 0101011 während 43 ₁₀ ist 0 0101011. Mit unterzeichnet Größendarstellung mehr Konsequenzen haben , die sie komplizierter zu implementieren macht:

Es gibt zwei Möglichkeiten, Null darzustellen, 00000000 (0) und 10000000 ( −0 ).
Addition und Subtraktion erfordern je nach Vorzeichenbit ein unterschiedliches Verhalten, während das Einerkomplement das Vorzeichenbit ignorieren und nur einen End-Around-Carry ausführen kann und das Zweierkomplement das Vorzeichenbit ignorieren und vom Überlaufverhalten abhängen kann.
Der Vergleich erfordert auch die Überprüfung des Vorzeichenbits, während man im Zweierkomplement einfach die beiden Zahlen subtrahieren und prüfen kann, ob das Ergebnis positiv oder negativ ist.
Die minimale negative Zahl ist −127 statt −128 beim Zweierkomplement.

Dieser Ansatz ist direkt vergleichbar mit der üblichen Art, ein Zeichen zu zeigen (ein „+“ oder „–“ neben der Größe der Zahl zu platzieren). Einige frühe Binärcomputer (z. B. IBM 7090 ) verwenden diese Darstellung, vielleicht wegen ihrer natürlichen Beziehung zur allgemeinen Verwendung. Vorzeichenbehafteter Betrag ist die gebräuchlichste Art, den Signifikanten in Gleitkommawerten darzustellen.

Einser-Komplement

Acht-Bit-Einser-Komplement
Binärwert	Einser-Komplement-Interpretation	Unsignierte Interpretation
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

Alternativ kann ein als Einerkomplement bekanntes System verwendet werden, um negative Zahlen darzustellen. Die Einerkomplementform einer negativen Binärzahl ist das bitweise darauf angewendete NICHT , dh das "Komplement" ihres positiven Gegenstücks. Wie die Vorzeichen- und Betragsdarstellung hat das Einerkomplement zwei Darstellungen von 0: 00000000 (+0) und 11111111 ( −0 ).

Als Beispiel wird die Einerkomplementform von 00101011 (43 ₁₀ ) zu 11010100 (–43 ₁₀ ). Der Bereich der vorzeichenbehafteten Zahlen im Einerkomplement wird durch −(2 ^{N −1} − 1) bis (2 ^{N −1} − 1) und ±0 dargestellt. Ein herkömmliches Acht-Bit-Byte ist –127 ₁₀ bis +127 _10, wobei Null entweder 00000000 (+0) oder 11111111 (–0) ist.

Um zwei in diesem System dargestellte Zahlen zu addieren, führt man eine konventionelle binäre Addition durch, aber es ist dann notwendig, einen End-Around-Carry durchzuführen , dh jeden resultierenden Übertrag zurück in die resultierende Summe zu addieren . Um zu sehen, warum dies notwendig ist, betrachten Sie das folgende Beispiel, das den Fall der Addition von −1 (11111110) zu +2 (00000010) zeigt:

    binary    decimal
   11111110     −1
+  00000010     +2
───────────     ──
 1 00000000      0   ← Not the correct answer
          1     +1   ← Add carry
───────────     ──
   00000001      1   ← Correct answer

Im vorherigen Beispiel ergibt die erste binäre Addition 00000000, was falsch ist. Das korrekte Ergebnis (00000001) erscheint nur, wenn der Übertrag wieder hinzugefügt wird.

Eine Anmerkung zur Terminologie: Das System wird als "Einser-Komplement" bezeichnet, weil die Negation eines positiven Wertes x (dargestellt als bitweises NOT von x ) auch durch Subtraktion von x von der Einser-Komplement-Darstellung von Null gebildet werden kann, d.h eine lange Folge von Einsen (−0). Die Zweierkomplementarithmetik hingegen bildet die Negation von x durch Subtraktion von x von einer einzelnen großen Zweierpotenz, die zu +0 kongruent ist . Daher unterscheiden sich Einser-Komplement- und Zweier-Komplement-Darstellungen desselben negativen Werts um eins.

Beachten Sie, dass die Einerkomplement-Darstellung einer negativen Zahl aus der Vorzeichen-Größen-Darstellung lediglich durch bitweises Komplementieren des Betrags (Invertieren aller Bits nach dem ersten) erhalten werden kann. Beispielsweise kann die Dezimalzahl −125 mit ihrer Vorzeichen-Größen-Darstellung 11111101 im Einerkomplement als 10000010 dargestellt werden.

Zweierkomplement

Acht-Bit-Zweierkomplement
Binärwert	Zweierkomplement-Interpretation	Unsignierte Interpretation
00000000	0	0
00000001	1	1
⋮	⋮	⋮
01111110	126	126
01111111	127	127
10000000	-128	128
10000001	−127	129
10000010	-126	130
⋮	⋮	⋮
11111110	-2	254
11111111	-1	255

Die Probleme mehrfacher Darstellungen von 0 und die Notwendigkeit des End-Around-Carrys werden durch ein System namens Zweierkomplement umgangen . Im Zweierkomplement werden negative Zahlen durch das Bitmuster dargestellt, das um eins größer ist (im Sinne ohne Vorzeichen) als das Einerkomplement des positiven Wertes.

Beim Zweierkomplement gibt es nur eine Null, dargestellt als 00000000. Das Negieren einer Zahl (ob negativ oder positiv) erfolgt durch Invertieren aller Bits und anschließendes Addieren von Eins zu diesem Ergebnis. Dies spiegelt tatsächlich die Ringstruktur auf allen ganzen Zahlen modulo 2 ^N : wider . Die Addition eines Paares von Ganzzahlen mit Zweierkomplement ist das gleiche wie die Addition eines Paares von vorzeichenlosen Zahlen (mit Ausnahme der Erkennung von Überlauf , falls dies erfolgt); das gleiche gilt für die Subtraktion und sogar für N niedrigstwertige Bits eines Produkts (Multiplikationswert). Zum Beispiel ergibt eine Zweier-Komplement-Addition von 127 und –128 das gleiche binäre Bitmuster wie eine vorzeichenlose Addition von 127 und 128, wie aus der 8-Bit-Zweier-Komplement-Tabelle ersichtlich ist. $\mathbb{Z}/2^{N}\mathbb{Z}$

Eine einfachere Methode, um die Negation einer Zahl im Zweierkomplement zu erhalten, ist wie folgt:

	Beispiel 1	Beispiel 2
1. Von rechts beginnend die erste "1" finden	0010100 1	00101 1 00
2. Invertieren Sie alle Bits links von dieser "1"	1101011 1	11010 100

Methode zwei:

Invertieren Sie alle Bits durch die Zahl
Füge eins hinzu

Beispiel: für +2, das ist 00000010 in binärer Form (das Zeichen ~ ist der bitweise NOT- Operator von C , also bedeutet ~X "alle Bits in X invertieren"):

~00000010 → 11111101
11111101 + 1 → 11111110 (−2 im Zweierkomplement)

Offset binär

Acht-Bit-Überschuss-128
Binärwert	Übermaß-128 Interpretation	Unsignierte Interpretation
00000000	-128	0
00000001	−127	1
⋮	⋮	⋮
01111111	-1	127
10000000	0	128
10000001	1	129
⋮	⋮	⋮
11111111	+127	255

Bei Offset-Binär (auch als Exzess- K oder Bias- Darstellung bezeichnet) wird eine vorzeichenbehaftete Zahl n durch das Bitmuster dargestellt, das der vorzeichenlosen Zahl n + K entspricht , wobei K der Biasing-Wert oder Offset ist . Somit wird 0 durch K repräsentiert , und –K wird durch ein Bitmuster nur aus Nullen repräsentiert. Dies kann als leichte Modifikation und Verallgemeinerung des oben erwähnten Zweier-Komplements gesehen werden, das praktisch die Exzess-(2 ^{N –1} ) -Darstellung mit negiertem höchstwertigem Bit ist .

Voreingenommene Darstellungen werden heute hauptsächlich für den Exponenten von Gleitkommazahlen verwendet . Der Gleitkomma-Standard IEEE 754 definiert das Exponentenfeld einer Zahl mit einfacher Genauigkeit (32 Bit) als ein 8-Bit- Exzess-127- Feld. Das Exponentenfeld mit doppelter Genauigkeit (64 Bit) ist ein 11-Bit- Exzess-1023- Feld; siehe Exponenten-Bias . Es wurde auch für binär codierte Dezimalzahlen als Exzess-3 verwendet .

Basis -2

Bei herkömmlichen Systemen Binärzahl, die Base oder radix , 2 ist ; somit repräsentiert das ganz rechte Bit 2 ⁰ , das nächste Bit repräsentiert 2 ¹ , das nächste Bit 2 ² und so weiter. Es ist aber auch ein binäres Zahlensystem zur Basis -2 möglich. Das ganz rechte Bit repräsentiert (−2) ⁰ = +1 , das nächste Bit repräsentiert (−2) ¹ = −2 , das nächste Bit (−2) ² = +4 und so weiter, mit wechselndem Vorzeichen. Die Zahlen, die mit vier Bits dargestellt werden können, sind in der folgenden Vergleichstabelle aufgeführt.

Der darstellbare Zahlenbereich ist asymmetrisch. Wenn das Wort eine gerade Anzahl von Bits hat, ist die größte negative Zahl, die dargestellt werden kann, doppelt so groß wie die größte positive Zahl, die dargestellt werden kann, und umgekehrt, wenn das Wort eine ungerade Anzahl von Bits hat.

Vergleichstabelle

Die folgende Tabelle zeigt die positiven und negativen ganzen Zahlen, die mit vier Bits dargestellt werden können.

Vier-Bit-Ganzzahldarstellungen
Dezimal	Ohne Vorzeichen	Vorzeichen und Größe	Einser-Komplement	Zweierkomplement	Überschuss-8 (voreingenommen)	Basis -2
+16	N / A	N / A	N / A	N / A	N / A	N / A
+15	1111	N / A	N / A	N / A	N / A	N / A
+14	1110	N / A	N / A	N / A	N / A	N / A
+13	1101	N / A	N / A	N / A	N / A	N / A
+12	1100	N / A	N / A	N / A	N / A	N / A
+11	1011	N / A	N / A	N / A	N / A	N / A
+10	1010	N / A	N / A	N / A	N / A	N / A
+9	1001	N / A	N / A	N / A	N / A	N / A
+8	1000	N / A	N / A	N / A	N / A	N / A
+7	0111	0111	0111	0111	1111	N / A
+6	0110	0110	0110	0110	1110	N / A
+5	0101	0101	0101	0101	1101	0101
+4	0100	0100	0100	0100	1100	0100
+3	0011	0011	0011	0011	1011	0111
+2	0010	0010	0010	0010	1010	0110
+1	0001	0001	0001	0001	1001	0001
+0	0000	0000	0000	0000	1000	0000
-0	0000	1000	1111	0000	1000	0000
-1	N / A	1001	1110	1111	0111	0011
-2	N / A	1010	1101	1110	0110	0010
-3	N / A	1011	1100	1101	0101	1101
-4	N / A	1100	1011	1100	0100	1100
-5	N / A	1101	1010	1011	0011	1111
-6	N / A	1110	1001	1010	0010	1110
-7	N / A	1111	1000	1001	0001	1001
-8	N / A	N / A	N / A	1000	0000	1000
-9	N / A	N / A	N / A	N / A	N / A	1011
-10	N / A	N / A	N / A	N / A	N / A	1010
-11	N / A	N / A	N / A	N / A	N / A	N / A

Dieselbe Tabelle, wie aus "Angesichts dieser binären Bits, was ist die Zahl, wie sie vom Darstellungssystem interpretiert wird":

Binär	Ohne Vorzeichen	Vorzeichen und Größe	Einser-Komplement	Zweierkomplement	Überschuss-8	Basis -2
0000	0	0	0	0	-8	0
0001	1	1	1	1	-7	1
0010	2	2	2	2	-6	-2
0011	3	3	3	3	-5	-1
0100	4	4	4	4	-4	4
0101	5	5	5	5	-3	5
0110	6	6	6	6	-2	2
0111	7	7	7	7	-1	3
1000	8	-0	-7	-8	0	-8
1001	9	-1	-6	-7	1	-7
1010	10	-2	-5	-6	2	-10
1011	11	-3	-4	-5	3	-9
1100	12	-4	-3	-4	4	-4
1101	13	-5	-2	-3	5	-3
1110	14	-6	-1	-2	6	-6
1111	fünfzehn	-7	-0	-1	7	-5

Andere Systeme

Die "Zick-Zack-Codierung" von Google Protocol Buffers ist ein System, das dem Vorzeichen und der Größe ähnelt, verwendet jedoch das niedrigstwertige Bit zur Darstellung des Vorzeichens und hat eine einzelne Darstellung von Null. Dies ermöglicht die effiziente Verwendung einer Quantitätscodierung variabler Länge , die für nicht negative (vorzeichenlose) ganze Zahlen gedacht ist, für vorzeichenbehaftete ganze Zahlen.

Eine ähnliche Methode wird in den Videokompressionsstandards H.264/MPEG-4 AVC und H.265 High Efficiency Video Coding verwendet, um die Exponential-Golomb-Codierung auf negative Zahlen zu erweitern. In dieser Erweiterung ist das niedrigstwertige Bit fast ein Vorzeichenbit; Null hat das gleiche niedrigstwertige Bit (0) wie alle negativen Zahlen. Diese Wahl führt dazu, dass die größte darstellbare positive Zahl um eins höher ist als die negative Zahl mit der größten Größe, anders als bei der Zweierkomplement- oder der Protokollpuffer-Zick-Zack-Codierung.

Ein anderer Ansatz besteht darin, jeder Ziffer ein Vorzeichen zu geben , was die Vorzeichen -Ziffer-Darstellung ergibt . Zum Beispiel befürwortete John Colson 1726 die Reduzierung von Ausdrücken auf "kleine Zahlen", die Ziffern 1, 2, 3, 4 und 5. Im Jahr 1840 drückte Augustin Cauchy auch die Bevorzugung solcher modifizierten Dezimalzahlen aus, um Fehler bei der Berechnung zu reduzieren.

Siehe auch

Verweise

Ivan Flores, Die Logik der Computerarithmetik , Prentice-Hall (1963)
Israel Koren, Computerarithmetische Algorithmen , AK Peters (2002), ISBN 1-56881-160-8

Languages

In other projects