Warum ist ein vorzeichenloser Ganzzahlüberlauf als Verhalten definiert, ein vorzeichenbehafteter Ganzzahlüberlauf jedoch nicht?

209

Der vorzeichenlose Ganzzahlüberlauf ist sowohl im C- als auch im C ++ - Standard gut definiert. Zum Beispiel heißt es im C99-Standard ( §6.2.5/9)

Eine Berechnung mit vorzeichenlosen Operanden kann niemals überlaufen, da ein Ergebnis, das nicht durch den resultierenden vorzeichenlosen Ganzzahltyp dargestellt werden kann, modulo um die Zahl reduziert wird, die eins größer ist als der größte Wert, der durch den resultierenden Typ dargestellt werden kann.

Beide Standards geben jedoch an, dass ein vorzeichenbehafteter Ganzzahlüberlauf ein undefiniertes Verhalten ist. Wieder aus dem C99-Standard ( §3.4.3/1)

Ein Beispiel für ein nicht definiertes Verhalten ist das Verhalten beim Ganzzahlüberlauf

Gibt es einen historischen oder (noch besser!) Technischen Grund für diese Diskrepanz?

c++ c undefined-behavior integer-overflow Anthony Vallée-Dubois
quelle
50
Wahrscheinlich, weil es mehr als eine Möglichkeit gibt, vorzeichenbehaftete Ganzzahlen darzustellen. Welcher Weg nicht im Standard angegeben ist, zumindest nicht in C ++.
Juanchopanza
Nützlicher Link: en.wikipedia.org/wiki/Signed_number_representations
Robᵩ
7
Was Juanchopanza sagte, macht Sinn. So wie ich es verstehe, hat der ursprüngliche C-Standard zum großen Teil die bestehende Praxis kodifiziert. Wenn sich alle Implementierungen zu diesem Zeitpunkt darauf geeinigt haben, was ein nicht signierter "Überlauf" tun soll, ist dies ein guter Grund, ihn zu standardisieren. Sie waren sich nicht einig, was ein signierter Überlauf tun sollte, so dass dies nicht in den Standard aufgenommen wurde.
2
@DavidElliman Wraparound ohne Vorzeichen beim Hinzufügen ist ebenfalls leicht zu erkennen ( if (a + b < a)). Der Überlauf bei der Multiplikation ist sowohl für vorzeichenbehaftete als auch für vorzeichenlose Typen schwierig.
5
@ DavidElliman: Es geht nicht nur darum, ob Sie es erkennen können, sondern auch um das Ergebnis. In einer Vorzeichen + Wert-Implementierung, MAX_INT+1 == -0während es sich um ein Zweierkomplement handelt, wäre esINT_MIN
David Rodríguez - Dribeas

Antworten:

163

Der historische Grund ist, dass die meisten C-Implementierungen (Compiler) nur das Überlaufverhalten verwendeten, das mit der verwendeten Ganzzahldarstellung am einfachsten zu implementieren war. C-Implementierungen verwendeten normalerweise dieselbe Darstellung, die von der CPU verwendet wurde - daher folgte das Überlaufverhalten der von der CPU verwendeten Ganzzahldarstellung.

In der Praxis können sich nur die Darstellungen für vorzeichenbehaftete Werte je nach Implementierung unterscheiden: das eigene Komplement, das Zweierkomplement, die Vorzeichengröße. Für einen Typ ohne Vorzeichen gibt es keinen Grund für den Standard, Variationen zuzulassen, da es nur eine offensichtliche binäre Darstellung gibt (der Standard erlaubt nur binäre Darstellung).

Relevante Zitate:

C99 6.2.6.1:3 :

In vorzeichenlosen Bitfeldern gespeicherte Werte und Objekte vom Typ vorzeichenloses Zeichen werden in reiner Binärschreibweise dargestellt.

C99 6.2.6.2:2 :

Wenn das Vorzeichenbit eins ist, muss der Wert auf eine der folgenden Arten geändert werden:

- der entsprechende Wert mit Vorzeichenbit 0 wird negiert ( Vorzeichen und Größe );

- das Vorzeichenbit hat den Wert - (2 N ) ( Zweierkomplement );

- Das Vorzeichenbit hat den Wert - (2 N - 1) ( das eigene Komplement ).

Heutzutage verwenden alle Prozessoren die Zweierkomplementdarstellung, aber der signierte arithmetische Überlauf bleibt undefiniert, und Compilerhersteller möchten, dass er undefiniert bleibt, da sie diese Undefiniertheit verwenden, um bei der Optimierung zu helfen. Siehe zum Beispiel diesen Blog-Beitrag von Ian Lance Taylor oder diese Beschwerde von Agner Fog und die Antworten auf seinen Fehlerbericht.

Pascal Cuoq
quelle
6
Der wichtige Hinweis hierbei ist jedoch, dass es in der modernen Welt keine Architekturen gibt, die etwas anderes als die 2-Komplement-Arithmetik verwenden. Dass die Sprachstandards weiterhin die Implementierung auf beispielsweise einem PDP-1 ermöglichen, ist ein rein historisches Artefakt.
Andy Ross
9
@AndyRoss, aber es gibt immer noch Systeme (OS + Compiler, zugegebenermaßen mit einer alten Geschichte) mit
eigener
3
@Andy Ross würden Sie in Betracht ziehen, dass "keine Architekturen ... mit etwas anderem als dem 2er-Komplement ..." heute die Bandbreite von DSPs und eingebetteten Prozessoren umfasst?
chux
11
@AndyRoss: Während es "keine" Architekturen gibt, die etwas anderes als 2s-Komplement verwenden (für eine Definition von "nein"), gibt es definitiv DSP-Architekturen, die eine gesättigte Arithmetik für vorzeichenbehaftete Ganzzahlen verwenden.
Stephen Canon
10
Die gesättigte vorzeichenbehaftete Arithmetik entspricht definitiv dem Standard. Natürlich müssen die Umbruchanweisungen für vorzeichenlose Arithmetik verwendet werden, aber der Compiler verfügt immer über die Informationen, um zu wissen, ob vorzeichenlose oder vorzeichenbehaftete Arithmetik ausgeführt wird, sodass er die Anweisungen mit Sicherheit entsprechend auswählen kann.
Café
15

Abgesehen von Pascals guter Antwort (die sicher die Hauptmotivation ist) ist es auch möglich, dass einige Prozessoren eine Ausnahme beim Überlauf von vorzeichenbehafteten Ganzzahlen verursachen, was natürlich zu Problemen führen würde, wenn der Compiler "ein anderes Verhalten veranlassen" müsste ( Verwenden Sie z. B. zusätzliche Anweisungen, um einen möglichen Überlauf zu überprüfen und in diesem Fall anders zu berechnen.

Es ist auch erwähnenswert, dass "undefiniertes Verhalten" nicht "nicht funktioniert" bedeutet. Dies bedeutet, dass die Implementierung in dieser Situation tun kann, was sie will. Dies beinhaltet "das Richtige tun" sowie "die Polizei rufen" oder "abstürzen". Die meisten Compiler wählen, wenn möglich, "das Richtige tun", vorausgesetzt, dies ist relativ einfach zu definieren (in diesem Fall). Wenn Sie jedoch Überläufe in den Berechnungen haben, ist es wichtig zu verstehen, was dies tatsächlich zur Folge hat und dass der Compiler möglicherweise etwas anderes als das tut, was Sie erwarten (und dass dies sehr stark von der Compilerversion, den Optimierungseinstellungen usw. abhängen kann). .

Mats Petersson
quelle
23
Compiler möchten jedoch nicht, dass Sie sich darauf verlassen, dass sie das Richtige tun, und die meisten von ihnen zeigen dies, sobald Sie int f(int x) { return x+1>x; }mit der Optimierung kompilieren . GCC und ICC optimieren mit Standardoptionen die oben genannten Optionen auf return 1;.
Pascal Cuoq
1
Ein Beispielprogramm, das intje nach Optimierungsstufe unterschiedliche Ergebnisse bei Überlauf liefert , finden Sie unter ideone.com/cki8nM. Ich denke, dies zeigt, dass Ihre Antwort schlechte Ratschläge gibt.
Magnus Hoff
Ich habe diesen Teil ein wenig geändert.
Mats Petersson
Wenn ein C ein Mittel zum Deklarieren einer Ganzzahl "Wrapping Signed Two's Complement" bereitstellen soll, sollte keine Plattform, auf der C überhaupt ausgeführt werden kann, große Probleme haben, sie zumindest mäßig effizient zu unterstützen. Der zusätzliche Overhead würde ausreichen, damit Code keinen solchen Typ verwenden sollte, wenn kein Umbruchverhalten erforderlich ist. Die meisten Operationen für Zweierkomplement-Ganzzahlen sind jedoch mit denen für vorzeichenlose Ganzzahlen identisch, mit Ausnahme von Vergleichen und Heraufstufungen.
Supercat
1
Negative Werte müssen vorhanden sein und "funktionieren", damit der Compiler korrekt funktioniert. Es ist natürlich durchaus möglich, das Fehlen vorzeichenbehafteter Werte innerhalb eines Prozessors zu umgehen und vorzeichenlose Werte entweder als Ein-Komplement oder als Zweier-Komplement zu verwenden, je nachdem, was am meisten dazu beiträgt Sinn basierend auf dem Befehlssatz. Dies ist normalerweise erheblich langsamer als die Hardwareunterstützung, unterscheidet sich jedoch nicht von Prozessoren, die kein Gleitkomma in der Hardware oder ähnlichem unterstützen. Es wird lediglich viel zusätzlicher Code hinzugefügt.
Mats Petersson
10

Bitte beachten Sie zunächst, dass C11 3.4.3 wie alle Beispiele und Fußnoten kein normativer Text ist und daher nicht für das Zitieren relevant ist!

Der relevante Text, der besagt, dass der Überlauf von Ganzzahlen und Gleitkommazahlen ein undefiniertes Verhalten ist, lautet wie folgt:

C11 6.5 / 5

Wenn während der Auswertung eines Ausdrucks eine Ausnahmebedingung auftritt (dh wenn das Ergebnis nicht mathematisch definiert ist oder nicht im Bereich der darstellbaren Werte für seinen Typ liegt), ist das Verhalten undefiniert.

Eine Erläuterung zum Verhalten vorzeichenloser Ganzzahltypen finden Sie hier:

C11 6.2.5 / 9

Der Bereich nichtnegativer Werte eines vorzeichenbehafteten Ganzzahltyps ist ein Unterbereich des entsprechenden vorzeichenlosen Ganzzahltyps, und die Darstellung desselben Werts in jedem Typ ist dieselbe. Eine Berechnung mit vorzeichenlosen Operanden kann niemals überlaufen, da ein Ergebnis, das nicht durch den resultierenden vorzeichenlosen Ganzzahltyp dargestellt werden kann, modulo um die Zahl reduziert wird, die eins größer ist als der größte Wert, der durch den resultierenden Typ dargestellt werden kann.

Dies macht vorzeichenlose Ganzzahltypen zu einem Sonderfall.

Beachten Sie auch, dass es eine Ausnahme gibt, wenn ein Typ in einen signierten Typ konvertiert wird und der alte Wert nicht mehr dargestellt werden kann. Das Verhalten ist dann lediglich implementierungsdefiniert, obwohl ein Signal ausgelöst werden kann.

C11 6.3.1.3

6.3.1.3 Ganzzahlen mit und ohne Vorzeichen

Wenn ein Wert mit einem ganzzahligen Typ in einen anderen ganzzahligen Typ als _Bool konvertiert wird und der Wert durch den neuen Typ dargestellt werden kann, bleibt er unverändert.

Wenn der neue Typ nicht signiert ist, wird der Wert konvertiert, indem wiederholt ein Wert mehr als der Maximalwert addiert oder subtrahiert wird, der im neuen Typ dargestellt werden kann, bis der Wert im Bereich des neuen Typs liegt.

Andernfalls wird der neue Typ signiert und der Wert kann nicht darin dargestellt werden. Entweder ist das Ergebnis implementierungsdefiniert oder es wird ein implementierungsdefiniertes Signal ausgelöst.

Lundin
quelle
6

Zusätzlich zu den anderen Themen erwähnt, ohne Vorzeichen Mathe Windung, die macht die unsigned Integer - Typen verhalten sich als abstrakte algebraischen Gruppen (das bedeutet unter anderem, für jedes Paar von Werten Xund Ywird es einen anderen Wert existieren , Zso dass X+ZWille, wenn sie richtig gegossen gleich ). Wenn vorzeichenlose Werte lediglich Speicherorttypen und keine Zwischenausdruckstypen waren (z. B. wenn es kein vorzeichenloses Äquivalent des größten Ganzzahltyps gab und arithmetische Operationen für vorzeichenlose Typen sich so verhielten, als würden sie zuerst in größere vorzeichenbehaftete Typen konvertiert, dann dort Ein definiertes Umhüllungsverhalten wäre nicht so wichtig, aber es ist schwierig, Berechnungen in einem Typ durchzuführen, der beispielsweise keine additive Inverse aufweist.Y und Y-Zwird, wenn richtig besetzt, gleichX

Dies hilft in Situationen, in denen das Umlaufverhalten tatsächlich nützlich ist - beispielsweise bei TCP-Sequenznummern oder bestimmten Algorithmen wie der Hash-Berechnung. Dies kann auch in Situationen hilfreich sein, in denen ein Überlauf erkannt werden muss, da das Durchführen von Berechnungen und das Überprüfen, ob sie übergelaufen sind, häufig einfacher ist als das vorherige Überprüfen, ob sie überlaufen würden, insbesondere wenn die Berechnungen den größten verfügbaren Ganzzahltyp beinhalten.

Superkatze
quelle
Ich folge nicht ganz - warum hilft es, eine additive Inverse zu haben? Ich kann mir keine Situation
vorstellen,
@sleske: Wenn ein Energiezähler die Dezimalzahl für die Lesbarkeit verwendet und 0003 anzeigt und der vorherige Wert 9995 betrug, bedeutet dies, dass -9992 Energieeinheiten oder 0008 Energieeinheiten verwendet wurden? Mit 0003-9995 Ausbeute 0008 ist es einfach, das letztere Ergebnis zu berechnen. Wenn es -9992 ergibt, wäre es etwas umständlicher.
Wenn Sie es jedoch auch nicht ausführen
@sleske: Es ist sowohl für Menschen als auch für Compiler sehr nützlich, die assoziativen, verteilenden und kommutativen Gesetze der Arithmetik anwenden zu können, um Ausdrücke neu zu schreiben und zu vereinfachen. zum Beispiel, wenn der Ausdruck a+b-cin einer Schleife berechnet wird, sondern bund ckonstant sind innerhalb dieser Schleife, kann es hilfreich seine Berechnung zu bewegen (b-c)außerhalb der Schleife, aber das tut unter anderem erfordern würde , die (b-c)einen Wert , der, wenn hinzugefügt a, ergibt a+b-c, was wiederum erfordert, cdass ein Additiv invers ist.
Supercat
: Danke für die Erklärungen. Wenn ich es richtig verstehe, gehen alle Ihre Beispiele davon aus, dass Sie den Überlauf tatsächlich handhaben möchten. In den meisten Fällen ist der Überlauf unerwünscht, und Sie möchten ihn verhindern, da das Ergebnis einer Berechnung mit Überlauf nicht hilfreich ist. Beispielsweise möchten Sie für den Energiezähler wahrscheinlich einen Typ verwenden, bei dem kein Überlauf auftritt.
Sleske
1
... so dass (a+b)-cequals a+(b-c)ob der arithmetischen Wert b-cinnerhalb des Typs darstellbarer ist, wird die Substitution unabhängig von dem möglichen Wertebereich gültig sein (b-c).
Supercat
1

Vielleicht liegt ein weiterer Grund dafür, warum vorzeichenlose Arithmetik definiert wird, darin, dass vorzeichenlose Zahlen Ganzzahlen modulo 2 ^ n bilden, wobei n die Breite der vorzeichenlosen Zahl ist. Vorzeichenlose Zahlen sind einfach Ganzzahlen, die durch Binärziffern anstelle von Dezimalstellen dargestellt werden. Das Ausführen der Standardoperationen in einem Modulsystem ist gut verstanden.

Das Zitat des OP bezieht sich auf diese Tatsache, hebt aber auch die Tatsache hervor, dass es nur eine eindeutige, logische Möglichkeit gibt, vorzeichenlose Ganzzahlen binär darzustellen. Im Gegensatz dazu werden vorzeichenbehaftete Zahlen am häufigsten mit dem Zweierkomplement dargestellt, es sind jedoch auch andere Auswahlmöglichkeiten möglich, wie im Standard (Abschnitt 6.2.6.2) beschrieben.

Durch die Zweierkomplementdarstellung können bestimmte Operationen im Binärformat sinnvoller sein. Das Inkrementieren negativer Zahlen ist beispielsweise dasselbe wie bei positiven Zahlen (unter Überlaufbedingungen zu erwarten). Einige Vorgänge auf Maschinenebene können für vorzeichenbehaftete und vorzeichenlose Nummern identisch sein. Bei der Interpretation des Ergebnisses dieser Operationen sind einige Fälle jedoch nicht sinnvoll - positiver und negativer Überlauf. Darüber hinaus unterscheiden sich die Überlaufergebnisse in Abhängigkeit von der zugrunde liegenden vorzeichenbehafteten Darstellung.

yth
quelle
Damit eine Struktur ein Feld ist, muss jedes Element der Struktur außer der additiven Identität eine multiplikative Inverse haben. Eine Struktur von ganzzahligen kongruenten Mod N ist nur dann ein Feld, wenn N eins oder eine Primzahl ist [ein Degnerationsfeld, wenn N == 1]. Gibt es etwas, das ich in meiner Antwort vermisst habe?
Supercat
Du hast recht. Die Hauptleistungsmodule haben mich verwirrt. Ursprüngliche Antwort bearbeitet.
yth
Extra hier verwirrend ist , dass es ist ein Bereich um 2 ^ n, es ist einfach nicht ring isomorph die ganzen Zahlen 2 Modulo ^ n.
Kevin Ventullo
Und 2 ^ 31-1 ist ein Mersenne Prime (aber 2 ^ 63-1 ist kein Prime). Damit war meine ursprüngliche Idee ruiniert. Auch die Ganzzahlgrößen waren früher unterschiedlich. Meine Idee war also bestenfalls revisionistisch.
yth
Die Tatsache, dass vorzeichenlose Ganzzahlen einen Ring (kein Feld) bilden, den Teil niedriger Ordnung nehmen, ergibt ebenfalls einen Ring, und das Ausführen von Operationen für den gesamten Wert und das anschließende Abschneiden verhält sich meiner Meinung nach gleichbedeutend mit dem Ausführen der Operationen nur für den unteren Teil mit ziemlicher Sicherheit Überlegungen.
Supercat