Warum sind vorzeichenlose Nummern implementiert?

12

Ich kann nicht herausfinden, warum Mikroprozessorsysteme vorzeichenlose Zahlen implementieren. Ich schätze, die Kosten sind nur doppelt so hoch wie die Anzahl der bedingten Verzweigungen, da mehr als, weniger als, etc. einen anderen Algorithmus als signiert benötigen. Gibt es dennoch Algorithmen, für die vorzeichenlose Zahlen einen signifikanten Vorteil darstellen?

Meine Frage ist zum Teil, warum sie im Befehlssatz enthalten sein müssen, anstatt von einem Compiler unterstützt zu werden.

jtw
quelle
27
Grundsätzlich sind die vorzeichenlosen Zahlen der Standard, vorzeichenbehaftete sind implementiert, um negative Zahlen zu liefern.
Pieter B
37
Viele Daten der Welt sind nicht numerisch. Nicht numerische Daten können mit vorzeichenlosen Typen leicht bearbeitet werden. Dass Java keine vorzeichenlosen numerischen Typen hat, ist ein Fehler, der viele Fehler in Dingen verursacht, die nicht numerische Daten manipulieren müssen (z. B. Komprimierung usw.).
Erik Eidt
6
@jtw Erik sagt, es gibt keine negativen Pixelfarben oder negativen Zeichen. Es wäre also verschwenderisch, dafür signierte Ganzzahlen zu verwenden. Sie würden die Hälfte des Adressraums aufgeben.
Martin Maat
26
Ich bin mir nicht sicher, ob ich alleine hier bin, aber ich finde es überraschend selten, dass ich beim Entwickeln von Anwendungen signierte Ganzzahlen benötige . Fast immer benötige ich entweder eine (vorzeichenlose) natürliche Zahl (normalerweise eine positive Größe) oder eine vorzeichenbehaftete Gleitkommazahl. Ausnahmen sind Dinge wie Währung, aber diese sind sehr selten. Für mich sind Ganzzahlen ohne Vorzeichen die Norm und Ganzzahlen mit Vorzeichen die Ausnahme!
Thomas
11
Aus Sicht der CPU sind so gut wie alle Zahlen ohne Vorzeichen. Einige Befehle können die Bits als vorzeichenbehaftet interpretieren (z. B. Arithmetik-Rechtsverschiebung), aber das Zweierkomplement lässt die CPU vorzeichenbehaftete Ganzzahlen als vorzeichenlose Ganzzahlen behandeln, was bedeutet, dass die CPU keine (oder nur sehr wenige) speziellen Schaltkreise benötigt, um beide zu unterstützen .
Cornstalks

Antworten:

39

Zahlen ohne Vorzeichen sind eine Interpretation einer Folge von Bits. Es ist auch die einfachste und am häufigsten verwendete Interpretation innerhalb der CPU, da Adressen und Operationscodes einfach Bits sind. Speicher- / Stapeladressierung und Arithmetik sind die Grundlagen der Mikroprozessor-Verarbeitung. Eine weitere häufige Interpretation von Bits ist das Aufrücken der Abstraktionspyramide als Zeichen (ASCII, Unicode, EBCDIC). Dann gibt es andere Interpretationen wie IEEE-Gleitkomma, RGBA für Grafiken und so weiter. Keine dieser Zahlen ist einfach vorzeichenbehaftet (IEEE FP ist nicht einfach und die Arithmetik mit diesen ist sehr kompliziert).

Außerdem ist es mit vorzeichenloser Arithmetik ziemlich einfach (wenn nicht am effizientesten), die anderen zu implementieren. Das Gegenteil ist nicht wahr.

Kristian H
quelle
3
EBCDIC hat nur ein "Ich".
Ruslan
4
@ Ruslan - aber es ist ausgesprochen wie es zwei hat. <g>
Pete Becker
5
@PeteBecker nein ist es nicht. EBCDIC wird eb- see-dick ausgesprochen .
Mike Nakis
19

Der Hauptteil der Hardwarekosten für Vergleichsoperationen ist die Subtraktion. Die Ausgabe der durch den Vergleich verwendeten Subtraktion besteht im wesentlichen aus drei Zustandsbits:

  • ob alle Bits Null sind (dh die gleiche Bedingung),
  • das Vorzeichen des Ergebnisses
  • das Übertragsbit der Subtraktion (dh das 33. höherwertige Bit auf einem 32-Bit-Computer)

Mit der richtigen Kombination des Testens dieser drei Bits nach der Subtraktionsoperation können wir alle vorzeichenbehafteten relationalen Operationen sowie alle vorzeichenlosen relationalen Operationen bestimmen (diese Bits bestimmen auch, wie ein Überlauf erkannt wird, vorzeichenbehaftet gegenüber vorzeichenlos). Dieselbe grundlegende ALU-Hardware kann gemeinsam genutzt werden, um alle diese Vergleiche durchzuführen (ganz zu schweigen von der Subtraktionsanweisung), bis die endgültige Überprüfung dieser drei Zustandsbits erfolgt, die sich gemäß dem gewünschten relationalen Vergleich unterscheidet. Es ist also nicht viel zusätzliche Hardware.

Die einzigen tatsächlichen Kosten sind die Notwendigkeit der Codierung zusätzlicher Vergleichsmodi in der Befehlssatzarchitektur, die die Befehlsdichte geringfügig verringern können. Dennoch ist es ziemlich normal, dass die Hardware viele Anweisungen enthält, die von keiner bestimmten Sprache verwendet werden.

Erik Eidt
quelle
1
Der Vergleich von Zahlen ohne Vorzeichen erfordert keine Subtraktion. Dies kann durch bitweisen Vergleich von links nach rechts erreicht werden.
Jonathan Rosenne
10
@ JonathanRosenne Aber so setzen Prozessoren das nicht um. Im Gegenteil, es ist fast undenkbar, dass ein Prozessor mit Zweierkomplement in seiner ALU keine Subtraktion (mit oder ohne Übertrag / Ausleihe) implementiert. Der unmittelbare Gedanke eines Designers ist, diese notwendige ALU zu verwenden, um einen anderen Vogel mit dem gleichen Stein zu töten, zum Vergleich. Der Vergleich wird dann einfach zu einer Subtraktion, bei der das Ergebnis nicht in die Registerdatei zurückgeschrieben wird.
Iwillnotexist Idonotexist
4
+1: Dies ist die richtige Antwort auf die gestellte Frage. Zusammenfassend: Die Implementierung nicht signierter Vorgänge ist fast kostenlos, wenn Sie bereits signierte Vorgänge implementiert haben .
Periata Breatta
10
@PeriataBreatta Es funktioniert auch umgekehrt. Vorzeichenlose und vorzeichenlose Nummern in modernen CPUs sind nahezu identisch. Dies ist der Hauptpunkt, den das OP nicht erkannt hat. Sogar die Vergleichsbefehle sind für signierte und nicht signierte gleich - das ist einer der Gründe, warum die Zweierkomplemente die signierten Ganzzahlkriege gewonnen haben :)
Luaan,
3
@svidgen> wie andere antworten sagten, funktioniert es umgekehrt. Vorrangiges Anliegen sind vorzeichenlose Zahlen, die grundsätzlich für alles verwendet werden (Speicheradresse, Io / Ports, Zeichendarstellung,…). Signierte Nummern sind erst dann billig, wenn Sie sie nicht mehr signiert haben. Sie sind in seltenen Fällen nützlich, wenn sie erwünscht sind.
Spektren
14

Denn wenn Sie etwas zählen müssen, das immer aktuell ist >= 0, würden Sie Ihren Zählraum unnötigerweise mit vorzeichenbehafteten ganzen Zahlen halbieren.

Berücksichtigen Sie die automatisch inkrementierte INT PK, die Sie möglicherweise in Ihre Datenbanktabellen einfügen. Wenn Sie dort eine Ganzzahl mit Vorzeichen verwenden, speichert Ihre Tabelle HALB so viele Datensätze wie möglich für dieselbe Feldgröße, ohne dass dies von Vorteil ist.

Oder die Oktette einer RGBa-Farbe. Wir wollen nicht unangenehm anfangen, dieses natürlich positive Zahlenkonzept mit einer negativen Zahl zu zählen. Eine signierte Zahl würde entweder das mentale Modell brechen oder unseren Raum halbieren. Eine vorzeichenlose Ganzzahl entspricht nicht nur dem Konzept, sondern bietet die doppelte Auflösung.

Aus der Hardware-Perspektive sind vorzeichenlose ganze Zahlen einfach. Sie sind wahrscheinlich die am einfachsten zu berechnende Bitstruktur. Und ohne Zweifel könnten wir die Hardware vereinfachen, indem wir Integer-Typen (oder sogar Gleitkommazahlen!) In einem Compiler simulieren. Also, warum sind beide nicht signierte und signierte ganze Zahlen in implementiert Hardware?

Nun ... Leistung!

Die Implementierung von Ganzzahlen mit Vorzeichen in Hardware ist effizienter als in Software. Die Hardware kann angewiesen werden, in einem einzigen Befehl eine beliebige Ganzzahl zu berechnen. Und das ist sehr gut , denn die Hardware zerschmettert Bits mehr oder weniger parallel. Wenn Sie versuchen, dies in Software zu simulieren, erfordert der Integer-Typ, den Sie für die "Simulation" auswählen, zweifellos viele Anweisungen und ist spürbar langsamer.

Svidgen
quelle
2
In diesem Sinne können Sie sich bei der Überprüfung der Array-Grenzen eine Operation sparen. Wenn Sie eine Ganzzahl ohne Vorzeichen verwenden, müssen Sie nur überprüfen, ob der angegebene Index kleiner als die Arraygröße ist (da er nicht negativ sein kann).
Riwalk
2
@ dan04 Das kann es sicherlich ... Aber wenn Sie ein Auto-Inkrementing-Int ab 0 oder 1 verwenden, was ziemlich üblich ist, haben Sie die Verwendung der Hälfte Ihrer verfügbaren Zahlen ausgeschlossen. Und während Sie denkbarerweise bei -2 ^ 31 (oder was auch immer) anfangen könnten, haben Sie einen potenziellen "Rand" -Fall in der Mitte Ihres ID-Bereichs.
Svidgen
1
Das Halbieren Ihres Feldes ist jedoch ein schwaches Argument. Wenn für Ihre App mehr als 2 Milliarden Euro erforderlich sind, sind wahrscheinlich auch mehr als 4 Milliarden Euro erforderlich.
corsiKa
1
@corsiKa: Wenn es aus diesem Grund mehr als 4 erfordert, sind wahrscheinlich 8, dann 16 usw. erforderlich. Wo endet es?
Whatsisname
1
@whatsisname Im Allgemeinen verwenden Sie Ganzzahltypen mit 8, 16, 32 oder 64 Bit. Es ist in den meisten Fällen unwichtig, zu sagen, dass vorzeichenlos besser ist, weil Sie alle 32 Bits anstelle des begrenzten Bereichs von 31 Bits positiven Ganzzahlraums in einem vorzeichenbehafteten Byte erhalten.
corsiKa
9

Ihre Frage besteht aus zwei Teilen:

  1. Was ist der Zweck von vorzeichenlosen ganzen Zahlen?

  2. Sind vorzeichenlose ganze Zahlen die Mühe wert?

1. Was ist der Zweck von vorzeichenlosen ganzen Zahlen?

Zahlen ohne Vorzeichen stellen ganz einfach eine Klasse von Größen dar, für die negative Werte bedeutungslos sind. Sicher könnte man sagen, dass die Antwort auf die Frage "Wie viele Äpfel habe ich?" Wenn Sie jemandem ein paar Äpfel schulden, könnte dies eine negative Zahl sein, aber was ist mit der Frage "Wie viel Speicher habe ich?" - Sie können nicht über eine negative Speichergröße verfügen. Ganzzahlen ohne Vorzeichen eignen sich also sehr gut zur Darstellung solcher Größen, und sie haben den Vorteil, dass sie den doppelten Bereich positiver Werte darstellen können, als dies bei Ganzzahlen mit Vorzeichen der Fall ist. Der maximale Wert, den Sie mit einer 16-Bit-Ganzzahl mit Vorzeichen darstellen können, ist 32767, während er mit einer 16-Bit-Ganzzahl ohne Vorzeichen 65535 ist.

2. Sind vorzeichenlose ganze Zahlen die Mühe wert?

Ganzzahlen ohne Vorzeichen sind eigentlich kein Problem, also sind sie es wert. Sie sehen, sie erfordern keine zusätzlichen "Algorithmen"; Die Schaltungsanordnung, die erforderlich ist, um sie zu implementieren, ist eine Teilmenge der Schaltungsanordnung, die zum Implementieren von Ganzzahlen mit Vorzeichen erforderlich ist.

Eine CPU hat keinen Multiplikator für vorzeichenbehaftete Ganzzahlen und keinen anderen Multiplikator für vorzeichenlose; Es gibt nur einen Multiplikator, der je nach Art der Operation leicht unterschiedlich funktioniert. Die Unterstützung der vorzeichenbehafteten Multiplikation erfordert ein kleines bisschen mehr Schaltkreise als die nicht vorzeichenbehaftete. Da diese jedoch ohnehin unterstützt werden muss, ist die vorzeichenlose Multiplikation praktisch kostenlos und im Lieferumfang enthalten.

Was Addition und Subtraktion betrifft, gibt es überhaupt keinen Unterschied in der Schaltung. Wenn Sie die so genannte Zweierkomplementdarstellung von ganzen Zahlen nachlesen, werden Sie feststellen, dass sie so clever gestaltet ist, dass diese Operationen unabhängig von der Art der ganzen Zahlen auf die gleiche Weise ausgeführt werden können.

Der Vergleich funktioniert auf die gleiche Weise, da es sich nur um das Subtrahieren und Verwerfen des Ergebnisses handelt. Der einzige Unterschied besteht in den Anweisungen für bedingte Verzweigungen (Sprünge) vorhergehende (Vergleichs-) Anweisung. In dieser Antwort: /programming//a/9617990/773113 finden Sie eine Erklärung, wie sie auf der Intel x86-Architektur funktionieren. Was passiert, ist, dass die Bezeichnung eines bedingten Sprungbefehls als vorzeichenbehaftet oder vorzeichenlos davon abhängt, welche Flags geprüft werden.

Mike Nakis
quelle
1
Meine Frage ging von all dem aus. Mit Algorithmus meinte ich, dass die Regel für weniger als größer als usw. unterschiedlich war. Die Kosten, die ich sehe, sind viele zusätzliche Anweisungen. Wenn High-Level-Programme Daten als Muster von Bits sehen
möchten,
3
@jtw - aber der Punkt ist, dass diese zusätzlichen Anweisungen den Anweisungen, die für vorzeichenbehaftete Nummern erforderlich sind, tatsächlich sehr ähnlich sind und fast alle für sie erforderlichen Schaltungen gemeinsam genutzt werden können . Die zusätzlichen Kosten für die Implementierung beider Typen betragen nahezu null.
Periata Breatta
1
Ja, das beantwortet meine Frage. Das Hinzufügen der zusätzlichen Verzweigungsanweisungen ist mit geringen Kosten verbunden und in der Praxis oft nützlich
jtw
1
„Unsigned Operationen erfordern einige zusätzliche Handhabung , wenn es um Teilung kommt und Multiplikation“ Ich glaube , Sie , dass nach hinten haben. Multiplikation und Division sind mit vorzeichenlosen Werten einfacher. Die zusätzliche Behandlung ist erforderlich, um mit vorzeichenbehafteten Operanden umzugehen.
Cody Grey
@CodyGray Ich wusste, dass jemand auftauchen würde, um dies zu sagen. Sie haben natürlich recht. Dies ist die Begründung für meine Aussage, die ich der Kürze halber ursprünglich weggelassen habe: Eine CPU könnte unmöglich nur vorzeichenlose Multiplikation und Division anbieten, weil die signierten Versionen so nützlich sind. Tatsächlich sind vorzeichenbehaftete Multiplikation und Division ein Muss. Nicht signierte sind optional. Wenn also nicht signiert wird auch angeboten, kann dies als erforderlich eine kleine bisschen mehr Schaltungen zu sehen.
Mike Nakis
7

Mikroprozessoren sind von Natur aus nicht signiert. Die signierten Zahlen sind das, was implementiert wird, nicht umgekehrt.

Computer können und funktionieren auch ohne vorzeichenbehaftete Zahlen, aber wir Menschen, die negative Zahlen brauchen, haben die Signatur erfunden.

Pieter B
quelle
4
Viele Mikroprozessoren haben sowohl signierte als auch nicht signierte Anweisungen für verschiedene Operationen.
Whatsisname
1
@whatsisname: Es ist das Gegenteil: Viele Mikroprozessoren haben nur vorzeichenlose Anweisungen. Ein paar haben unterzeichnet Anweisungen. Dies liegt daran, dass bei der 2s-Komplement-Arithmetik der Bitwert unabhängig vom Wetter derselbe ist, ob die Nummer mit oder ohne Vorzeichen versehen ist, und wie die Nummer gelesen wird, ist nur eine Frage der Interpretation - daher ist es einfacher, sie als Compiler-Feature zu implementieren. Im Allgemeinen haben nur alte Mikros, die davon ausgehen, dass Programmierer keine Compiler verwenden, ausgefallene signierte Anweisungen, um Assembler-Code lesbar zu machen.
Slebetman
3

Weil sie ein Bit mehr haben, das für die Speicherung leicht verfügbar ist, und Sie sich nicht um negative Zahlen sorgen müssen. Es gibt nicht viel mehr als das.

Wenn Sie nun ein Beispiel benötigen, wo Sie dieses zusätzliche Bit benötigen würden , gibt es viel zu finden, wenn Sie schauen.

Mein Lieblingsbeispiel sind Bitboards in Schach-Engines. Auf einem Schachbrett befinden sich 64 Felder, wodurch unsigned longeine Vielzahl von Algorithmen, die sich mit der Generierung von Zügen befassen, optimal gespeichert werden können. In Anbetracht der Tatsache, dass Sie Binäroperationen (wie auch Schichtoperationen !!) ausführen müssen, ist es einfach zu verstehen, warum es einfacher ist, sich keine Gedanken darüber zu machen, welche besonderen Dinge passieren, wenn das MSB gesetzt ist. Es kann mit long mit Vorzeichen durchgeführt werden , aber es ist viel einfacher, unsigned zu verwenden.

riwalk
quelle
3

Mit einem rein mathematischen Hintergrund ist dies eine etwas mathematischere Einstellung für alle Interessierten.

Wenn wir mit einer 8-Bit-Ganzzahl mit und ohne Vorzeichen beginnen, haben wir im Grunde genommen die Ganzzahlen modulo 256, was Addition und Multiplikation betrifft, vorausgesetzt, das Zweierkomplement wird zur Darstellung negativer Ganzzahlen verwendet (und so macht es jeder moderne Prozessor). .

Wo sich die Dinge unterscheiden, gibt es zwei Stellen: eine ist Vergleichsoperationen. In gewisser Weise werden die Ganzzahlen modulo 256 am besten als ein Kreis von Zahlen betrachtet (wie dies die Ganzzahlen modulo 12 auf einem altmodischen analogen Zifferblatt tun). Um numerische Vergleiche (ist x <y) sinnvoll zu machen, mussten wir entscheiden, welche Zahlen kleiner als andere sind. Aus der Sicht des Mathematikers wollen wir die ganzen Zahlen modulo 256 irgendwie in die Menge aller ganzen Zahlen einbetten. Es liegt auf der Hand, die 8-Bit-Ganzzahl, deren Binärdarstellung aus Nullen besteht, auf die Ganzzahl 0 abzubilden. Wir können dann mit dem Abbilden anderer fortfahren, so dass '0 + 1' (das Ergebnis des Nullstellens eines Registers, sagen wir ax, und des Inkrementierens um eins, über 'inc ax') auf die Ganzzahl 1 geht und so weiter. Wir können dasselbe mit -1 machen, zum Beispiel '0-1' der ganzen Zahl -1 zuordnen und '0-1-1' auf die ganze Zahl -2. Wir müssen sicherstellen, dass diese Einbettung eine Funktion ist, und können daher keine einzelne 8-Bit-Ganzzahl auf zwei Ganzzahlen abbilden. Dies bedeutet, dass, wenn wir alle Zahlen in die Menge der Ganzzahlen abbilden, 0 zusammen mit einigen Ganzzahlen kleiner als 0 und einigen größer als 0 vorhanden sein wird bis zu welchem ​​Minimum Sie wollen, von 0 bis -255). Dann können Sie 'x <y' als '0 <y - x' definieren.

Es gibt zwei häufige Anwendungsfälle, für die Hardware-Unterstützung sinnvoll ist: einer mit einer Ganzzahl ungleich Null, die größer als 0 ist, und einer mit einer Aufteilung von ungefähr 50/50 um 0. Alle anderen Möglichkeiten lassen sich leicht durch Übersetzen von Zahlen mit einem zusätzlichen 'add' emulieren und sub 'vor Operationen, und die Notwendigkeit für diese ist so selten, als ich mir kein explizites Beispiel in moderner Software vorstellen kann (da Sie nur mit einer größeren Mantisse arbeiten können, sagen wir 16 Bits).

Das andere Problem ist das Abbilden einer 8-Bit-Ganzzahl in den Raum von 16-Bit-Ganzzahlen. Geht -1 zu -1? Dies ist, was Sie wollen, wenn 0xFF -1 darstellen soll. In diesem Fall ist es sinnvoll, das Vorzeichen zu erweitern, damit 0xFF zu 0xFFFF wird. Wenn dagegen 0xFF für 255 stehen soll, soll es auf 255 und damit auf 0x00FF und nicht auf 0xFFFF abgebildet werden.

Dies ist auch der Unterschied zwischen der Verschiebung und der arithmetischen Verschiebung.

Letztendlich kommt es jedoch darauf an, dass ints in Software keine ganzen Zahlen sind, sondern Darstellungen in binärer Form, und nur einige können dargestellt werden. Beim Entwerfen von Hardware müssen Entscheidungen getroffen werden, welche Aufgaben in der Hardware von Haus aus zu erledigen sind. Da mit dem 2er-Komplement die Additions- und Multiplikationsoperationen identisch sind, ist es sinnvoll, negative ganze Zahlen auf diese Weise darzustellen. Dann ist es nur eine Frage der Operationen, die davon abhängen, welche ganzen Zahlen Ihre binären Darstellungen darstellen sollen.

John Allsup
quelle
Ich mag den mathematischen Ansatz, aber anstatt nur an die Heraufstufung auf eine bestimmte größere Größe zu denken, halte ich es für sinnvoller, Operationen mit Binärzahlen unendlicher Länge zu verallgemeinern. Subtrahieren Sie 1 von jeder Zahl, deren ganz rechts liegende k Ziffern 0 sind, und die ganz rechts liegenden k Ziffern des Ergebnisses sind 1, und Sie können durch Induktion beweisen, dass jedes Bit 1 wäre, wenn Sie eine Mathematik mit einer unendlichen Anzahl von Bits ausführen Mathe, man ignoriert alle bis auf die unteren Bits einer Zahl.
Supercat
2

Untersuchen wir die Implementierungskosten für das Hinzufügen von Ganzzahlen ohne Vorzeichen zu einem CPU-Entwurf mit vorhandenen Ganzzahlen mit Vorzeichen.

Eine typische CPU benötigt die folgenden arithmetischen Anweisungen:

  • ADD (fügt zwei Werte hinzu und setzt ein Flag, wenn die Operation überläuft)
  • SUB (subtrahiert einen Wert von einem anderen und setzt verschiedene Flags - wir werden diese unten diskutieren)
  • CMP (im Wesentlichen "SUB und das Ergebnis verwerfen, nur die Flags behalten")
  • LSH (Linksverschiebung, Flag auf Überlauf setzen)
  • RSH (Rechtsverschiebung, setze ein Flag, wenn eine 1 rausgeschoben wird)
  • Varianten aller obigen Befehle, die das Tragen / Ausleihen von Flags handhaben, wodurch Sie die Befehle bequem miteinander verketten können, um größere Typen als die CPU-Register zu bearbeiten
  • MUL (Multiplizieren, Setzen von Flags usw. - nicht universell verfügbar)
  • DIV (Teilen, Setzen von Flags usw. - dies fehlt vielen CPU-Architekturen)
  • Wechseln Sie von einem kleineren Integer-Typ (z. B. 16 Bit) zu einem größeren (z. B. 32 Bit). Für vorzeichenbehaftete Ganzzahlen wird dies normalerweise als MOVSX bezeichnet (Verschieben mit Vorzeichenerweiterung).

Es braucht auch logische Anweisungen:

  • Verzweigen Sie auf Null
  • Verzweigen Sie sich auf größer
  • Verzweigen Sie sich auf weniger
  • Bei Überlauf abzweigen
  • Negierte Versionen von allen oben genannten

Um die obigen Verzweigungen bei Ganzzahlvergleichen mit Vorzeichen durchzuführen, ist es am einfachsten, den SUB-Befehl die folgenden Flags setzen zu lassen:

  • Null. Wird gesetzt, wenn die Subtraktion zu einem Wert von Null geführt hat.
  • Überlauf. Stellen Sie ein, ob die Subtraktion einen Wert vom höchstwertigen Bit ausgeliehen hat.
  • Zeichen. Auf das Vorzeichenbit des Ergebnisses setzen.

Dann werden die arithmetischen Zweige wie folgt implementiert:

  • Verzweigen auf Null: wenn das Null-Flag gesetzt ist
  • Verzweigen auf weniger: Wenn sich das Vorzeichen-Flag vom Überlauf-Flag unterscheidet
  • Verzweigen auf größer: Wenn das Vorzeichen-Flag dem Überlauf-Flag entspricht und das Null-Flag gelöscht ist.

Die Verneinung dieser sollte offensichtlich daraus folgen, wie diese umgesetzt werden.

Ihr vorhandenes Design implementiert also all diese bereits für vorzeichenbehaftete ganze Zahlen. Betrachten wir nun, was wir tun müssen, um vorzeichenlose Ganzzahlen hinzuzufügen:

  • ADD - Die Implementierung von ADD ist identisch.
  • SUB - wir müssen ein zusätzliches Flag hinzufügen: Das Übertrags-Flag wird gesetzt, wenn ein Wert von außerhalb des höchstwertigen Bits des Registers ausgeliehen wird.
  • CMP - ändert sich nicht
  • LSH - ändert sich nicht
  • RSH - Die rechte Verschiebung für vorzeichenbehaftete Werte behält den Wert des höchstwertigen Bits bei. Für vorzeichenlose Werte sollten wir sie stattdessen auf Null setzen.
  • MUL - Wenn Ihre Ausgabegröße mit der Eingabe identisch ist, ist keine spezielle Behandlung erforderlich (x86 hat eine spezielle Behandlung, aber nur, weil es in ein Registerpaar ausgegeben wurde) ein offensichtlicherer Kandidat, auf einen Prozessor zu verzichten als nicht signierte Typen)
  • DIV - keine Änderungen erforderlich
  • Bewegen Sie sich von einem kleineren Typ zu einem größeren Typ - müssen Sie MOVZX hinzufügen, bewegen Sie sich mit Null-Ausdehnung. Beachten Sie, dass MOVZX sehr einfach zu implementieren ist.
  • Verzweigen auf Null - unverändert
  • Verzweigen auf weniger - Sprünge bei gesetztem Carry Flag.
  • Verzweigen auf Größer - Springt, wenn das Übertragsflag und die Null beide gelöscht sind.

Es ist zu beachten, dass die Modifikationen in jedem Fall sehr einfach sind und einfach implementiert werden können, indem ein kleiner Abschnitt der Schaltung ein- oder ausgeschaltet wird oder indem ein neues Flagregister hinzugefügt wird, das durch einen Wert gesteuert werden kann, der als Teil von berechnet werden muss die Implementierung der Anweisung trotzdem.

Daher sind die Kosten für das Hinzufügen von Anweisungen ohne Vorzeichen sehr gering . Warum sollte es getan werden? , beachten Sie, dass Speicheradressen (und Offsets in Arrays) sind von Natur Werte ohne Vorzeichen. Da Programme viel Zeit damit verbringen, Speicheradressen zu manipulieren, erleichtert ein Typ, der sie korrekt verarbeitet, das Schreiben der Programme.

Periata Breatta
quelle
danke, dies beantwortet meine
frage
1
Eine vorzeichenlose Multiplikation mit doppelter Größe ist bei der Ausführung von Multipräzisionsarithmetik unerlässlich und eignet sich wahrscheinlich für eine Verbesserung der Gesamtgeschwindigkeit um mehr als das Zweifache, wenn eine RSA-Verschlüsselung durchgeführt wird. Außerdem unterscheidet sich die Unterteilung in den Fällen mit und ohne Vorzeichen. Da die Unterteilung jedoch einfacher und selten genug und langsam genug ist, um ein paar Anweisungen hinzuzufügen, ist es am einfachsten, nur eine Unterteilung ohne Vorzeichen zu implementieren und wickeln Sie es dann mit einer Zeichenbehandlungslogik.
Supercat
2

Zahlen ohne Vorzeichen existieren hauptsächlich, um Situationen zu bewältigen, in denen ein umschließender algebraischer Ring benötigt wird (für einen 16-Bit-Typ ohne Vorzeichen wäre dies der Ring aus ganzen Zahlen, der mit dem Mod 65536 kongruent ist). Nehmen Sie einen Wert, addieren Sie einen Betrag, der kleiner als der Modul ist, und die Differenz zwischen den beiden Werten ist der Betrag, der addiert wurde. Wenn ein Verbrauchszähler am Monatsanfang 9995 anzeigt und 23 Einheiten verwendet, zeigt der Zähler am Monatsende 0018 an. Wenn Sie einen algebraischen Ringtyp verwenden, müssen Sie nichts Besonderes tun, um den Überlauf zu beheben. Wenn Sie 9995 von 0018 subtrahieren, erhalten Sie 0023, genau die Anzahl der Einheiten, die verwendet wurden.

Auf dem PDP-11, der Maschine, für die C zum ersten Mal implementiert wurde, gab es keine vorzeichenlosen Ganzzahltypen, aber vorzeichenbehaftete Typen konnten für modulare Arithmetik verwendet werden, die zwischen 32767 und -32768 statt zwischen 65535 und 0 umschlossen war Plattformen haben die Dinge jedoch nicht sauber verpackt; Anstatt zu verlangen, dass Implementierungen die im PDP-11 verwendeten Zweierkomplement-Ganzzahlen emulieren, fügte die Sprache stattdessen vorzeichenlose Typen hinzu, die sich meist als algebraische Ringe verhalten mussten, und erlaubte vorzeichenbehafteten Ganzzahltypen, sich im Falle eines Überlaufs auf andere Weise zu verhalten.

In den frühen Tagen von C gab es viele Mengen, die 32767 (der gemeinsame INT_MAX) überschreiten konnten, aber nicht 65535 (der gemeinsame UINT_MAX). Es wurde daher üblich, vorzeichenlose Typen zu verwenden, um solche Mengen zu speichern (z. B. size_t). Leider gibt es in der Sprache keine Unterscheidung zwischen Typen, die sich wie Zahlen mit einem zusätzlichen positiven Bereich verhalten sollten, und Typen, die sich wie algebraische Ringe verhalten sollten. Stattdessen verhält sich ein Typ, der kleiner als "int" ist, aufgrund der Sprache wie eine Zahl, während sich ein Typ in voller Größe wie ein algebraischer Ring verhält. Folglich rufen Sie die Funktion wie folgt auf:

uint32_t mul(uint16_t a, uint16_t b) { return a*b; }

with (65535, 65535) hat ein definiertes Verhalten auf Systemen mit int16 Bit (dh Rückgabe 1), ein anderes Verhalten mit int33 Bit oder mehr (Rückgabe 0xFFFE0001) und undefiniertes Verhalten auf Systemen mit "int" zwischen [beachten Sie, dass gcc in der Regel wird arithmetisch korrekte Ergebnisse mit Ergebnissen zwischen INT_MAX + 1u und UINT_MAX liefert, aber manchmal Code für die obige Funktion generiert, der mit solchen Werten fehlschlägt!]. Nicht sehr hilfreich.

Das Fehlen von Typen, die sich konsistent wie Zahlen oder konsistent wie ein algebraischer Ring verhalten, ändert jedoch nichts an der Tatsache, dass algebraische Ringtypen für manche Arten der Programmierung fast unverzichtbar sind.

Superkatze
quelle