wake-up-neo.com

Warum lieber das Zweierkomplement als das Vorzeichen und die Größe für vorzeichenbehaftete Zahlen?

Ich bin nur neugierig, ob es einen Grund gibt, warum zur Darstellung von -1 in der Binärzahl das Zweierkomplement verwendet wird: die Bits spiegeln und 1 addieren?

-1 wird durch 11111111 (Zweierkomplement) und nicht (für mich intuitiver) durch 10000001 dargestellt, was eine binäre 1 mit dem ersten Bit als negativem Flag ist.

Haftungsausschluss: Ich verlasse mich bei meiner Arbeit nicht auf binäre Arithmetik!

190
Ray

Dies geschieht, damit die Addition keine spezielle Logik für den Umgang mit negativen Zahlen benötigt. Check out der Artikel auf Wikipedia .

Angenommen, Sie haben zwei Zahlen, 2 und -1. In Ihrer "intuitiven" Art, Zahlen darzustellen, wären sie 0010 und 1001, bzw. (ich halte mich an 4 Bits für die Größe). In der Art, wie sich die beiden ergänzen, sind sie 0010 und 1111. Angenommen, ich möchte sie hinzufügen.

Die Zweierkomplementaddition ist sehr einfach. Normalerweise addieren Sie Zahlen und jedes Übertragsbit am Ende wird verworfen. Sie werden also wie folgt hinzugefügt:

  0010
+ 1111
=10001
= 0001 (discard the carry)

0001 ist 1, was das erwartete Ergebnis von "2 + (- 1)" ist.

Bei Ihrer "intuitiven" Methode ist das Hinzufügen jedoch komplizierter:

  0010
+ 1001
= 1011

Welches ist -3, richtig? Einfaches Hinzufügen funktioniert in diesem Fall nicht. Sie müssen beachten, dass eine der Zahlen negativ ist und in diesem Fall einen anderen Algorithmus verwenden.

Bei dieser "intuitiven" Speichermethode ist die Subtraktion eine andere Operation als die Addition und erfordert zusätzliche Überprüfungen der Zahlen, bevor sie hinzugefügt werden können. Da Sie die einfachsten Operationen (Addition, Subtraktion usw.) so schnell wie möglich ausführen möchten, müssen Sie Zahlen so speichern, dass Sie die einfachsten Algorithmen verwenden können.

Darüber hinaus gibt es bei der "intuitiven" Speichermethode zwei Nullen:

0000  "zero"
1000  "negative zero"

Die intuitiv die gleiche Zahl sind, aber beim Speichern zwei unterschiedliche Werte haben. Jede Anwendung muss zusätzliche Schritte unternehmen, um sicherzustellen, dass Nicht-Null-Werte auch keine negativen Nullen sind.

Es gibt einen weiteren Vorteil beim Speichern von Ints auf diese Weise. In diesem Fall müssen Sie die Breite des Registers erweitern, in dem der Wert gespeichert wird. Bei einem Zweierkomplement müssen Sie die 4-Bit-Zahl in einem 8-Bit-Register wiederholen höchstwertiges Bit:

    0001 (one, in four bits)
00000001 (one, in eight bits)
    1110 (negative two, in four bits)
11111110 (negative two, in eight bits)

Es geht nur darum, das Vorzeichen des kleineren Wortes zu betrachten und es zu wiederholen, bis es die Breite des größeren Wortes auffüllt.

Mit Ihrer Methode müssten Sie das vorhandene Bit löschen, was eine zusätzliche Operation neben dem Auffüllen ist:

    0001 (one, in four bits)
00000001 (one, in eight bits)
    1010 (negative two, in four bits)
10000010 (negative two, in eight bits)

Sie müssen diese zusätzlichen 4 Bits in beiden Fällen noch festlegen, aber im "intuitiven" Fall müssen Sie auch das 5. Bit löschen. Es ist ein winziger zusätzlicher Schritt in einer der grundlegendsten und häufigsten Operationen, die in jeder Anwendung vorhanden sind.

317
Welbog

Wikipedia sagt alles:

Das Zweierkomplementsystem hat den Vorteil, dass es nicht erforderlich ist, dass die Additions- und Subtraktionsschaltung die Vorzeichen der Operanden überprüft, um zu bestimmen, ob addiert oder subtrahiert werden soll. Diese Eigenschaft macht das System sowohl einfacher zu implementieren als auch in der Lage, Arithmetik mit höherer Genauigkeit zu verarbeiten. Außerdem hat Null nur eine einzige Darstellung, wodurch die Feinheiten der negativen Null vermieden werden, die in Einskomplementsystemen vorhanden sind.

Mit anderen Worten, das Addieren ist dasselbe, egal ob die Zahl negativ ist oder nicht.

18
Yacoby

Auch wenn diese Frage alt ist, lassen Sie mich meine 2 Cent setzen.

Bevor ich dies erkläre, kommen wir zu den Grundlagen zurück. 2 'Komplement ist 1's Komplement + 1. Was ist nun die Ergänzung zu 1 und welche Bedeutung hat sie zusätzlich?.

Die Summe aus einer beliebigen n-Bit-Zahl und ihrem Einskomplement ergibt die höchstmögliche Zahl, die durch diese n-Bits dargestellt werden kann. Beispiel:

 0010 (2 in 4 bit system)
+1101 (1's complement of 2)
___________________________
 1111  (the highest number that we can represent by 4 bits)

Was passiert nun, wenn wir versuchen, dem Ergebnis noch 1 hinzuzufügen? Es kommt zu einem Überlauf.

Das Ergebnis ist 1 0000 was 0 ist (da wir mit 4-Bit-Zahlen arbeiten, (die 1 links ist ein Überlauf)

So ,

Any n-bit number + its 1's complement = max n-bit number
Any n-bit number + its 1'complement + 1 = 0 ( as explained above, overflow will occur as we are adding 1 to max n-bit number)

Jemand beschloss dann, 1s Komplement + 1 als 2'Komplement zu bezeichnen. Die obige Aussage lautet also: Jede n'Bit-Zahl + das Zweierkomplement = 0, was das Zweierkomplement einer Zahl = - (dieser Zahl) bedeutet.

All dies wirft eine weitere Frage auf: Warum können wir nur die (n-1) der n Bits verwenden, um eine positive Zahl darzustellen, und warum stellt das am weitesten links stehende n-te Bit ein Vorzeichen dar (0 am am weitesten links stehenden Bit bedeutet + ve Zahl, und 1 bedeutet -ve Nummer). zB warum verwenden wir nur die ersten 31 Bits eines int in Java), um eine positive Zahl darzustellen, wenn das 32. Bit 1 ist, seine a -ve-Zahl.

 1100 (lets assume 12 in 4 bit system)
+0100(2's complement of 12)
___________________________

1 0000 (Ergebnis ist Null, Übertrag 1 läuft über)

Somit funktioniert das System von (n + 2'Komplement von n) = 0 immer noch. Die einzige Mehrdeutigkeit ist, dass das Zweierkomplement von 12 0100 ist, was mehrdeutig auch +8 darstellt, außer dass das Zweierkomplementsystem -12 darstellt.

Dieses Problem ist gelöst, wenn positive Zahlen immer eine 0 im Bit ganz links haben. In diesem Fall hat das Zweierkomplement immer eine 1 im äußersten linken Bit, und wir werden nicht die Mehrdeutigkeit derselben Menge von Bits haben, die die Zweierkomplementzahl sowie eine + ve Zahl darstellen.

12
Rpant

Zweierkomplement Ermöglicht das normale Addieren und Subtrahieren (so wie Sie bei Zahlen ohne Vorzeichen gewickelt haben). Es verhindert auch -0 (eine separate Möglichkeit, 0 darzustellen, die beim normalen bitweisen Vergleichen von Zahlen nicht gleich 0 wäre).

8
Zifre

dies soll Summen und Differenzen von Zahlen vereinfachen. Eine Summe aus einer negativen und einer positiven Zahl, die in Zweierkomplementen kodiert sind, entspricht einer normalen Summierung.

6
Stefano Verna

Die übliche Implementierung der Operation besteht darin, "die Bits umzudrehen und 1 zu addieren", aber es gibt eine andere Art, sie zu definieren, die wahrscheinlich die Begründung klarer macht. Das 2-Komplement ist die Form, die Sie erhalten, wenn Sie die übliche vorzeichenlose Darstellung verwenden, bei der jedes Bit die nächste Zweierpotenz steuert, und nur den höchstwertigen Term negativ machen.

8-Bit-Wert annehmen a7 ein6 ein5 ein4 ein3 ein2 ein1 ein

Die übliche vorzeichenlose Binärinterpretation lautet:
27*ein7 + 26*ein6 + 25*ein5 + 24*ein4 + 23*ein3 + 22*ein2 + 21*ein1 + 2*ein
[...] 11111111 = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255

Die Komplementinterpretation der beiden lautet:
- 27*ein7 + 26*ein6 + 25*ein5 + 24*ein4 + 23*ein3 + 22*ein2 + 21*ein1 + 2*ein
[...] 11111111 = -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -1

Keines der anderen Bits ändert seine Bedeutung und geht in a über7 ist "Überlauf" und es wird nicht erwartet, dass es funktioniert, so dass so ziemlich alle arithmetischen Operationen ohne Änderung funktionieren (wie andere angemerkt haben). Die Vorzeichengröße überprüft im Allgemeinen das Vorzeichenbit und verwendet eine andere Logik.

5
puetzk

So erweitern Sie die Antworten anderer:

In Zweierkomplement

  • Das Hinzufügen ist der gleiche Mechanismus wie das Hinzufügen von einfachen positiven ganzen Zahlen.
  • Das Subtrahieren ändert sich auch nicht
  • Multiplikation auch!

Division erfordert einen anderen Mechanismus.

All dies ist wahr, weil das Zweierkomplement nur eine normale modulare Arithmetik ist, bei der wir einige Zahlen als negativ betrachten, indem wir das Modulo subtrahieren.

4
yairchu

Das Zweierkomplement ermöglicht die Addition von negativen und positiven Zahlen ohne spezielle Logik.

Wenn Sie versucht haben, 1 und -1 mit Ihrer Methode hinzuzufügen
10000001 (-1)
+ 00000001 (1)
du erhältst
10000010 (-2)

Stattdessen können wir durch die Verwendung des Zweierkomplements hinzufügen

11111111 (-1)
+ 00000001 (1) erhalten Sie
00000000 (0)

Gleiches gilt für die Subtraktion.

Wenn Sie versuchen, 4 von 6 zu subtrahieren (zwei positive Zahlen), können Sie 2 zu 4 ergänzen und die beiden 6 + (-4) = 6 - 4 = 2 addieren

Dies bedeutet, dass das Subtrahieren und Addieren von sowohl positiven als auch negativen Zahlen von derselben Schaltung in der CPU durchgeführt werden kann.

4

Als ich die Antworten auf diese Frage las, stieß ich auf diesen Kommentar [bearbeitet].

2s Komplement von 0100 (4) wird 1100 sein. Jetzt ist 1100 12, wenn ich normal sage. Also, wenn ich normale 1100 sage, dann ist es 12, aber wenn ich 2's Komplement 1100 sage, dann ist es -4? Außerdem wird in Java wenn 1100 (wir nehmen jetzt 4 Bits an) gespeichert, wie bestimmt wird, ob es +12 oder -4 ?? - Hagrawal 2. Juli um 16:53 ist

Meiner Meinung nach ist die in diesem Kommentar gestellte Frage sehr interessant. Daher möchte ich sie zunächst umformulieren und dann eine Antwort und ein Beispiel geben.

FRAGE - Wie kann das System feststellen, wie ein oder mehrere benachbarte Bytes interpretiert werden müssen? Wie kann das System insbesondere feststellen, ob eine gegebene Folge von Bytes eine einfache Binärzahl oder eine Zweierkomplementzahl ist?

ANTWORT - Das System legt fest, wie eine Folge von Bytes durch Typen interpretiert wird. Typen definieren

  • wie viele Bytes müssen berücksichtigt werden
  • wie diese Bytes interpretiert werden müssen

BEISPIEL - Nachfolgend nehmen wir das an

  • char sind 1 Byte lang
  • short sind 2 Bytes lang
  • int 's und float' s sind 4 Bytes lang

Bitte beachten Sie, dass diese Größen für mein System spezifisch sind. Obwohl ziemlich häufig, können sie von System zu System unterschiedlich sein. Wenn Sie neugierig sind, was sich auf Ihrem System befindet, verwenden Sie den Operator sizeof .

Zunächst definieren wir ein Array mit 4 Bytes und initialisieren alle mit der Binärzahl 10111101, entsprechend der Hexadezimalzahl BD.

// BD(hexadecimal) = 10111101 (binary)
unsigned char   l_Just4Bytes[ 4 ]   =   { 0xBD, 0xBD, 0xBD, 0xBD };

Dann lesen wir den Array-Inhalt mit verschiedenen Typen.

unsigned char und signed char

// 10111101 as a PLAIN BINARY number equals 189
printf( "l_Just4Bytes as unsigned char  -> %hi\n", *( ( unsigned char* )l_Just4Bytes ) );

// 10111101 as a 2'S COMPLEMENT number equals -67
printf( "l_Just4Bytes as signed char    -> %i\n", *( ( signed char* )l_Just4Bytes ) );

unsigned short und short

// 1011110110111101 as a PLAIN BINARY number equals 48573
printf( "l_Just4Bytes as unsigned short -> %hu\n", *( ( unsigned short* )l_Just4Bytes ) );

// 1011110110111101 as a 2'S COMPLEMENT number equals -16963
printf( "l_Just4Bytes as short          -> %hi\n", *( ( short* )l_Just4Bytes ) );

unsigned int, int und float

// 10111101101111011011110110111101 as a PLAIN BINARY number equals 3183328701
printf( "l_Just4Bytes as unsigned int   -> %u\n", *( ( unsigned int* )l_Just4Bytes ) );

// 10111101101111011011110110111101 as a 2'S COMPLEMENT number equals -1111638595
printf( "l_Just4Bytes as int            -> %i\n", *( ( int* )l_Just4Bytes ) );

// 10111101101111011011110110111101 as a IEEE 754 SINGLE-PRECISION number equals -0.092647
printf( "l_Just4Bytes as float          -> %f\n", *( ( float* )l_Just4Bytes ) );

Die 4 Bytes in RAM (l_Just4Bytes[ 0..3 ]) immer genau gleich bleiben. Das Einzige, was sich ändert, ist, wie wir sie interpretieren.

Wiederum wir sagen Sie dem System wie, um sie durch Typen zu interpretieren.

Zum Beispiel haben wir oben die folgenden Typen verwendet, um den Inhalt des l_Just4Bytes Array

  • unsigned char: 1 Byte in einfacher Binärdatei
  • signed char: 1 Byte im 2er-Komplement
  • unsigned short: 2 Bytes in einfacher Binärschreibweise
  • short: 2 Bytes im Zweierkomplement
  • unsigned int: 4 Bytes in einfacher Binärschreibweise
  • int: 4 Bytes im Zweierkomplement
  • float: 4 Byte in IEEE 754-Notation mit einfacher Genauigkeit

[BEARBEITEN] Dieser Beitrag wurde nach dem Kommentar von user4581301 bearbeitet. Vielen Dank, dass Sie sich die Zeit genommen haben, diese wenigen hilfreichen Zeilen zu schreiben!

2
mw215

Sie können Professor Jerry Cain von Stanford bei der Erklärung des Zweierkomplements in der zweiten Vorlesung (die Erklärung des Zweierkomplements beginnt gegen 13:00 Uhr) in der Vortragsreihe mit dem Titel Programmierparadigmen beobachten, die auf dem YouTube-Kanal von Standford zu sehen ist. Hier ist der Link zur Vorlesungsreihe: http://www.youtube.com/view_play_list?p=9D558D49CA734A02 .

1
alexs

Ein Hauptvorteil der Zweierkomplementdarstellung, der hier noch nicht erwähnt wurde, besteht darin, dass die unteren Bits einer Zweierkomplementsumme, -differenz oder eines Produkts nur von der Entsprechung abhängen Bits der Operanden. Der Grund, warum der vorzeichenbehaftete 8-Bit-Wert für -1 11111111 Ist, ist das Subtrahieren einer beliebigen Ganzzahl, deren niedrigste 8-Bits 00000001 Von einer beliebigen anderen Ganzzahl sind Die niedrigsten 8 Bits von 0000000 ergeben eine Ganzzahl, deren niedrigste 8 Bits 11111111 sind. Mathematisch wäre der Wert -1 eine unendliche Folge von Einsen, aber alle Werte innerhalb des Bereichs eines bestimmten Ganzzahltyps sind entweder alle Einsen oder alle Nullen nach einem bestimmten Punkt, so dass es für Computer praktisch ist, die Zeichen zu "verlängern" höchstwertiges Bit einer Zahl, als würde es eine unendliche Anzahl von Einsen oder Nullen darstellen.

Das Zweierkomplement ist so gut wie die einzige Darstellung mit vorzeichenbehafteten Zahlen, die gut funktioniert, wenn es um Typen geht, die größer sind als die natürliche Wortgröße einer Binärmaschine, da Code bei der Addition oder Subtraktion den niedrigsten Teil jedes Operanden abrufen und den niedrigsten Teil von berechnen kann das Ergebnis und speichern das, laden dann den nächsten Teil jedes Operanden, berechnen den nächsten Teil des Ergebnisses und speichern das usw. Somit auch ein Prozessor, der alle Additionen und Subtraktionen benötigt, um ein einzelnes 8-Bit-Register zu durchlaufen 32-Bit-Zahlen mit Vorzeichen können relativ effizient verarbeitet werden (natürlich langsamer als mit einem 32-Bit-Register, aber immer noch funktionsfähig).

Bei Verwendung der anderen vom C-Standard zugelassenen vorzeichenbehafteten Darstellungen kann jedes Bit des Ergebnisses von einem beliebigen Bit der Operanden beeinflusst werden. Dies macht es erforderlich, entweder einen vollständigen Wert in Registern auf einmal zu speichern oder Berechnungen mit einem zusätzlichen Wert zu folgen Schritt, bei dem in einigen Fällen jeder Teil des Ergebnisses gelesen, geändert und neu geschrieben werden muss.

0
supercat

Wir führen nur Additionsoperationen sowohl für die Addition als auch für die Subtraktion durch. Wir addieren den zweiten Operanden zum ersten Operanden, um ihn zu addieren. Zur Subtraktion addieren wir das Zweierkomplement des zweiten Operanden zum ersten Operanden.

Bei einer Zweierkomplementdarstellung benötigen wir keine separaten digitalen Komponenten für die Subtraktion - es werden nur Addierer und Komplementierer verwendet.

0
subhakar

Nun, Ihre Absicht ist es nicht wirklich, alle Bits Ihrer Binärzahl umzukehren. Es ist nur ein glücklicher Zufall, dass das Subtrahieren von 1 von 1 zu 0 und das Subtrahieren von 0 von 1 zu 1 führt. Das Umdrehen von Bits führt also effektiv diese Subtraktion aus.

Aber warum stellen Sie fest, dass jede Ziffer von 1 abweicht? Nun, das bist du nicht. Ihre eigentliche Absicht ist es, die Differenz der angegebenen Binärzahl zu einer anderen Binärzahl zu berechnen, die dieselbe Anzahl von Ziffern hat, aber nur Einsen enthält. Wenn Ihre Nummer beispielsweise 10110001 lautet und Sie alle diese Bits umdrehen, berechnen Sie effektiv (11111111 - 10110001).

Dies erklärt den ersten Schritt bei der Berechnung des Zweikomplements. Lassen Sie uns nun den zweiten Schritt - Hinzufügen von 1 - ebenfalls in das Bild aufnehmen.

Addiere 1 zu der obigen binären Gleichung:

11111111 - 10110001 + 1

Was bekommst du? Dies:

100000000 - 10110001

Dies ist die endgültige Gleichung. Und indem Sie diese beiden Schritte ausführen, versuchen Sie, den endgültigen Unterschied zu finden: die Binärzahl, die von einer anderen Binärzahl mit einer zusätzlichen Ziffer subtrahiert wird und Nullen enthält, mit Ausnahme der Bitposition mit der höchsten Bedeutung.

Aber warum sehnen wir uns wirklich nach diesem Unterschied? Nun, von hier an ist es wahrscheinlich besser, wenn Sie den Wikipedia-Artikel lesen.

0

Es ist zu beachten, dass bei einigen frühen Addiermaschinen vor den Tagen der Digitalcomputer eine Subtraktion durchgeführt wurde, indem der Bediener Werte unter Verwendung eines andersfarbigen Satzes von Legenden auf jedem Schlüssel eingab (jeder Schlüssel würde also neun minus der Zahl eingeben, die sein soll) subtrahiert), und drücken Sie eine spezielle Taste würde einen Übertrag in eine Berechnung übernehmen. Auf einer sechsstelligen Maschine würde der Bediener, um 1234 von einem Wert zu subtrahieren, Tasten drücken, die normalerweise "998,765" anzeigen, und eine Taste drücken, um diesen Wert plus eins zur laufenden Berechnung hinzuzufügen. Die Zweierkomplementarithmetik ist einfach das binäre Äquivalent der früheren Zehnerkomplementarithmetik.

0
supercat

Der Vorteil der Subtraktion durch das Komplement-Verfahren ist die Reduzierung der Hardware
Komplexität. Die verschiedenen digitalen Schaltungen müssen nicht addiert und subtrahiert werden. Addition und Subtraktion werden nur vom Addierer ausgeführt.

0
user2640494

Das Zweierkomplement wird verwendet, weil es einfacher in Schaltungen zu implementieren ist und auch keine negative Null zulässt.

Wenn es x Bits gibt, reicht das Zweierkomplement von + (2 ^ x/2 + 1) bis - (2 ^ x/2). Das Einerkomplement reicht von + (2 ^ x/2) bis - (2 ^ x/2), lässt jedoch eine negative Null zu (0000 entspricht 1000 in einem 4-Bit-Einerkomplementsystem).

0
samoz