Ist die Subtraktion von Ganzzahlen ohne Vorzeichen als Verhalten definiert?

100

Ich bin auf Code von jemandem gestoßen, der zu glauben scheint, dass es ein Problem gibt, eine vorzeichenlose Ganzzahl von einer anderen Ganzzahl des gleichen Typs zu subtrahieren, wenn das Ergebnis negativ wäre. Dieser Code wäre also falsch, selbst wenn er auf den meisten Architekturen funktioniert.

unsigned int To, Tf;

To = getcounter();
while (1) {
    Tf = getcounter();
    if ((Tf-To) >= TIME_LIMIT) {
        break;
    } 
}

Dies ist das einzige vage relevante Zitat aus dem C-Standard, das ich finden konnte.

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.

Ich nehme an, man könnte dieses Zitat so verstehen, dass wenn der richtige Operand größer ist, die Operation so angepasst wird, dass sie im Kontext von Modulo-abgeschnittenen Zahlen sinnvoll ist.

dh

0x0000 - 0x0001 == 0x 1 0000 - 0x0001 == 0xFFFF

im Gegensatz zur Verwendung der implementierungsabhängigen vorzeichenbehafteten Semantik:

0x0000 - 0x0001 == (ohne Vorzeichen) (0 + -1) == (0xFFFF, aber auch 0xFFFE oder 0x8001)

Welche oder welche Interpretation ist richtig? Ist es überhaupt definiert?

c standards unsigned integer-arithmetic LihO
quelle
3
Die Wortwahl im Standard ist unglücklich. Dass es „niemals überlaufen kann“ bedeutet, dass es sich nicht um eine Fehlersituation handelt. Verwenden Sie die Terminologie im Standard, anstatt den Wert "wraps" zu überschreiten.
Danorton

Antworten:

107

Das Ergebnis einer Subtraktion, die eine negative Zahl in einem vorzeichenlosen Typ erzeugt, ist genau definiert:

  1. [...] 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. (ISO / IEC 9899: 1999 (E) §6.2.5 / 9)

Wie Sie sehen können, (unsigned)0 - (unsigned)1entspricht -1 modulo UINT_MAX + 1 oder mit anderen Worten UINT_MAX.

Beachten Sie, dass, obwohl es heißt "Eine Berechnung mit vorzeichenlosen Operanden kann niemals überlaufen", was Sie zu der Annahme führen könnte, dass sie nur für das Überschreiten der Obergrenze gilt, dies als Motivation für den tatsächlich verbindlichen Teil des Satzes dargestellt wird: "a Das Ergebnis, das nicht durch den resultierenden vorzeichenlosen Ganzzahltyp dargestellt werden kann, wird modulo um die Zahl reduziert, die eins größer ist als der größte Wert, der durch den resultierenden Typ dargestellt werden kann. " Dieser Satz ist nicht auf den Überlauf der Obergrenze des Typs beschränkt und gilt gleichermaßen für Werte, die zu niedrig sind, um dargestellt zu werden.

bdonlan
quelle
2
Danke dir! Ich sehe jetzt die Interpretation, die mir gefehlt hat. Ich denke, sie hätten einen klareren Wortlaut wählen können.
4
Ich fühle mich jetzt so viel besser, wenn ich weiß, dass wenn eine vorzeichenlose Addition auf Null rollt und Chaos verursacht, dies daran liegt, dass uintimmer der mathematische Ring der ganzen Zahlen 0durch UINT_MAXdie Operationen der Addition und Multiplikation modulo dargestellt werden sollte UINT_MAX+1, und nicht daran eines Überlaufs. Es stellt sich jedoch die Frage, warum die Sprache, wenn Ringe ein so grundlegender Datentyp sind, keine allgemeinere Unterstützung für Ringe anderer Größen bietet.
Theodore Murdock
2
@ TheodoreMurdock Ich denke, die Antwort auf diese Frage ist einfach. Soweit ich das beurteilen kann, ist die Tatsache, dass es sich um einen Ring handelt, eine Konsequenz und keine Ursache. Die eigentliche Anforderung besteht darin, dass vorzeichenlose Typen alle ihre Bits an der Wertdarstellung beteiligen müssen. Daraus ergibt sich natürlich ein ringartiges Verhalten. Wenn Sie ein solches Verhalten von anderen Typen erwarten, führen Sie Ihre Arithmetik durch und wenden Sie anschließend den erforderlichen Modul an. das verwendet grundlegende Operatoren.
underscore_d
@underscore_d Natürlich ... es ist klar, warum sie die Designentscheidung getroffen haben. Es ist nur amüsant, dass sie die Spezifikation grob als "Es gibt kein arithmetisches Über- / Unterlaufen, weil der Datentyp als Ring angegeben ist" geschrieben haben, als ob diese Designauswahl bedeutete, dass Programmierer Über- und Unterschreiten nicht sorgfältig vermeiden müssen -flow oder lassen ihre Programme spektakulär scheitern.
Theodore Murdock
119

Wenn Sie mit vorzeichenlosen Typen arbeiten, findet eine modulare Arithmetik (auch als "Wrap Around" -Verhalten bezeichnet) statt. Um diese modulare Arithmetik zu verstehen , schauen Sie sich einfach diese Uhren an:

Geben Sie hier die Bildbeschreibung ein

9 + 4 = 1 ( 13 mod 12 ), also in die andere Richtung: 1 - 4 = 9 ( -3 mod 12 ). Das gleiche Prinzip wird bei der Arbeit mit vorzeichenlosen Typen angewendet. Wenn der Ergebnistyp ist unsigned, findet eine modulare Arithmetik statt.

Betrachten Sie nun die folgenden Vorgänge, in denen das Ergebnis als gespeichert wird unsigned int:

unsigned int five = 5, seven = 7;
unsigned int a = five - seven;      // a = (-2 % 2^32) = 4294967294 

int one = 1, six = 6;
unsigned int b = one - six;         // b = (-5 % 2^32) = 4294967291

Wenn Sie sicherstellen möchten, dass das Ergebnis vorliegt signed, speichern Sie es in einer signedVariablen oder wandeln Sie es in um signed. Wenn Sie den Unterschied zwischen Zahlen ermitteln und sicherstellen möchten, dass die modulare Arithmetik nicht angewendet wird, sollten Sie abs()die in stdlib.hfolgenden Definitionen definierte Funktion in Betracht ziehen.

int c = five - seven;       // c = -2
int d = abs(five - seven);  // d =  2

Seien Sie sehr vorsichtig, insbesondere beim Schreiben von Bedingungen, da:

if (abs(five - seven) < seven)  // = if (2 < 7)
    // ...

if (five - seven < -1)          // = if (-2 < -1)
    // ...

if (one - six < 1)              // = if (-5 < 1)
    // ...

if ((int)(five - seven) < 1)    // = if (-2 < 1)
    // ...

aber

if (five - seven < 1)   // = if ((unsigned int)-2 < 1) = if (4294967294 < 1)
    // ...

if (one - six < five)   // = if ((unsigned int)-5 < 5) = if (4294967291 < 5)
    // ...
LihO
quelle
4
Netter mit den Uhren, obwohl der Beweis dies zur richtigen Antwort machen würde. Die Prämisse der Frage beinhaltet bereits die Behauptung, dass all dies wahr sein könnte.
Leichtigkeitsrennen im Orbit
5
@ LightnessRacesinOrbit: Danke. Ich habe es geschrieben, weil ich denke, dass jemand es sehr hilfreich finden könnte. Ich stimme zu, dass es keine vollständige Antwort ist.
LihO
4
Die Leitung int d = abs(five - seven);ist nicht gut. Zuerst five - sevenwird berechnet: Promotion belässt die Operandentypen als unsigned int, das Ergebnis wird modulo berechnet (UINT_MAX+1)und ausgewertet UINT_MAX-1. Dann ist dieser Wert der eigentliche Parameter abs, was eine schlechte Nachricht ist. abs(int)Verursacht undefiniertes Verhalten beim Übergeben des Arguments, da es nicht im Bereich liegt und abs(long long)wahrscheinlich den Wert enthalten kann. Undefiniertes Verhalten tritt jedoch auf, wenn der Rückgabewert intzum Initialisieren gezwungen wird d.
Ben Voigt
1
@LihO: Der einzige Operator in C ++, der kontextsensitiv ist und sich je nach Verwendung des Ergebnisses unterschiedlich verhält, ist ein benutzerdefinierter Konvertierungsoperator operator T(). Die Hinzufügung in den beiden Ausdrücken, die wir diskutieren, erfolgt in Typ unsigned int, basierend auf den Operandentypen. Das Ergebnis der Addition ist unsigned int. Dieses Ergebnis wird dann implizit in den im Kontext erforderlichen Typ konvertiert. Diese Konvertierung schlägt fehl, da der Wert im neuen Typ nicht darstellbar ist.
Ben Voigt
1
@ LiO: Es kann hilfreich sein, an double x = 2/3;vsdouble y = 2.0/3;
Ben Voigt
5

Nun, die erste Interpretation ist richtig. Ihre Argumentation zur "signierten Semantik" in diesem Zusammenhang ist jedoch falsch.

Auch hier ist Ihre erste Interpretation richtig. Arithmetik ohne Vorzeichen folgt den Regeln der Modulo-Arithmetik, dh, 0x0000 - 0x0001sie wird 0xFFFFfür vorzeichenlose 32-Bit-Typen ausgewertet .

Die zweite Interpretation (die auf "signierter Semantik" basiert) ist jedoch ebenfalls erforderlich, um das gleiche Ergebnis zu erzielen. Das heißt, selbst wenn Sie 0 - 1im Bereich des signierten Typs auswerten und -1als Zwischenergebnis erhalten, ist dies -1dennoch erforderlich, um zu produzieren0xFFFF wenn es später in einen nicht signierten Typ konvertiert wird. Selbst wenn eine Plattform eine exotische Darstellung für vorzeichenbehaftete Ganzzahlen verwendet (1er-Komplement, vorzeichenbehaftete Größe), muss diese Plattform beim Konvertieren vorzeichenbehafteter Ganzzahlwerte in vorzeichenlose Ganzzahlregeln Regeln der Modulo-Arithmetik anwenden.

Zum Beispiel diese Bewertung

signed int a = 0, b = 1;
unsigned int c = a - b;

ist nach wie vor produzieren garantiert UINT_MAXin csogar, wenn die Plattform eine exotische Darstellung für signierte ganze Zahlen verwendet.

Ameise
quelle
4
Ich denke, Sie meinen 16-Bit-Typen ohne Vorzeichen, nicht 32-Bit.
Xioxox
4

Bei vorzeichenlosen Zahlen vom Typ unsigned intoder größer wird in Abwesenheit von Typkonvertierungen a-bdefiniert, dass die vorzeichenlose Zahl erhalten wird, die, wenn sie hinzugefügt bwird, ergibt a. Die Konvertierung einer negativen Zahl in eine vorzeichenlose Zahl ergibt die Zahl, die beim Hinzufügen zu der vorzeichenumgekehrten ursprünglichen Zahl Null ergibt. Wenn Sie also -5 in vorzeichenlose Zahl umwandeln, erhalten Sie einen Wert, der bei Addition zu 5 Null ergibt.) .

Beachten Sie, dass vorzeichenlose Zahlen, die kleiner sind als vor der Subtraktion unsigned intzum Typ intheraufgestuft werden können, das Verhalten von a-bvon der Größe von abhängt int.

Superkatze
quelle