Warum sind vorzeichenlose Nummern implementiert?

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.