Ist das Verhalten der vorzeichenlosen ganzzahligen Subtraktion definiert?

Ich bin auf Code von jemandem gestoßen, der zu glauben scheint, dass es ein Problem gibt, eine vorzeichenlose Ganzzahl von einer anderen Ganzzahl desselben 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 Integer-Typ dargestellt werden kann, modulo um die Zahl reduziert wird, die um 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 rechte Operand größer ist, die Operation so angepasst wird, dass sie im Kontext von Modulo-gekürzten Zahlen sinnvoll ist.

dh

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

im Gegensatz zur Verwendung der implementierungsabhängigen signierten Semantik:

0x0000 – 0x0001 == (unsigned)(0 + -1) == (0xFFFF aber auch 0xFFFE oder 0x8001)

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

Wenn Sie mit arbeiten ohne Vorzeichen Typen, Modulararithmetik (auch bekannt als “umwickeln” Verhalten) stattfindet. Um dies zu verstehen Modulararithmetikschau dir einfach diese Uhren an:

9 + 4 = 1 (13 Mod 12), also in die andere Richtung: 1 – 4 = 9 (-3 Mod 12). Das gleiche Prinzip wird beim Arbeiten mit vorzeichenlosen Typen angewendet. Wenn die Ergebnistyp ist unsigneddann findet modulare Arithmetik statt.

Sehen Sie sich nun die folgenden Operationen an, die das Ergebnis als speichern 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 ist signeddann gespeichert in signed Variable oder umwandeln signed. Wenn Sie den Unterschied zwischen Zahlen ermitteln und sicherstellen möchten, dass die modulare Arithmetik nicht angewendet wird, sollten Sie die Verwendung von in Betracht ziehen abs() Funktion definiert in stdlib.h:

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

Seien Sie sehr vorsichtig, besonders beim Schreiben von Bedingungen, denn:

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)
    // ...

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

1. […] Eine Berechnung mit vorzeichenlosen Operanden kann niemals überlaufen, da ein Ergebnis, das nicht durch den resultierenden vorzeichenlosen ganzzahligen Typ dargestellt werden kann, modulo um die Zahl reduziert wird, die um 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 du sehen kannst, (unsigned)0 - (unsigned)1 gleich -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 glauben machen könnte, dass es nur für das Überschreiten der Obergrenze gilt, dies als a dargestellt wird Motivation für den eigentlichen Bindungsteil des Satzes: “ein Ergebnis, das nicht durch den resultierenden vorzeichenlosen ganzzahligen Typ dargestellt werden kann, wird modulo um die Zahl reduziert, die um eins größer ist als der größte Wert, der durch den resultierenden Typ dargestellt werden kann.” Dieser Satz ist nicht auf das Überlaufen der oberen Grenze des Typs beschränkt und gilt gleichermaßen für Werte, die zu niedrig sind, um dargestellt zu werden.

Nun, die erste Interpretation ist richtig. Ihre Argumentation zur “vorzeichenbehafteten Semantik” in diesem Zusammenhang ist jedoch falsch.

Auch hier ist Ihre erste Interpretation richtig. Vorzeichenlose Arithmetik folgt den Regeln der Modulo-Arithmetik, was bedeutet, dass 0x0000 - 0x0001 wertet zu 0xFFFF für 32-Bit-Typen ohne Vorzeichen.

Allerdings ist auch die zweite Interpretation (die auf der “vorzeichenbehafteten Semantik” basiert) erforderlich, um das gleiche Ergebnis zu erzielen. Dh auch wenn Sie bewerten 0 - 1 in der Domäne des signierten Typs und erhalten -1 als Zwischenergebnis dies -1 muss noch produziert werden 0xFFFF wenn es später in einen unsignierten Typ konvertiert wird. Selbst wenn einige Plattformen eine exotische Darstellung für vorzeichenbehaftete Ganzzahlen verwenden (1er-Komplement, vorzeichenbehaftete Größe), muss diese Plattform dennoch Regeln der Modulo-Arithmetik anwenden, wenn sie vorzeichenbehaftete Ganzzahlwerte in vorzeichenlose umwandelt.

Zum Beispiel diese Bewertung

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

wird noch garantiert produziert UINT_MAX in cauch wenn die Plattform eine exotische Darstellung für vorzeichenbehaftete Ganzzahlen verwendet.

Mit vorzeichenlosen Nummern vom Typ unsigned int oder größer, in Ermangelung von Typkonvertierungen, a-b ist definiert als die vorzeichenlose Zahl, die, wenn sie hinzugefügt wird, ergibt bwird nachgeben a. Die Umwandlung einer negativen Zahl in eine vorzeichenlose Zahl ist definiert als die Erzielung der Zahl, die, wenn sie zur vorzeichenumgekehrten ursprünglichen Zahl addiert wird, Null ergibt (also ergibt die Umwandlung von -5 in eine vorzeichenlose Zahl einen Wert, der, wenn sie zu 5 addiert wird, Null ergibt). .

Beachten Sie, dass vorzeichenlose Zahlen kleiner als sind unsigned int kann zum Schreiben befördert werden int vor der Subtraktion, das Verhalten von a-b hängt von der Größe ab int.

Nun, eine vorzeichenlose ganzzahlige Subtraktion hat ein definiertes Verhalten, außerdem ist es eine knifflige Sache. Wenn Sie zwei Ganzzahlen ohne Vorzeichen subtrahieren, wird das Ergebnis zu einem höheren Typ int heraufgestuft, wenn der Ergebnistyp (lvalue) nicht explizit angegeben ist. Im letzteren Fall zum Beispiel int8_t result = a – b; (wobei a und b den Typ int8_t haben) können Sie ein sehr seltsames Verhalten erhalten. Ich meine, Sie können verlieren Transitivitätseigenschaft (dh wenn a > b und b > c ist es wahr, dass a > c). Der Verlust der Transitivität kann a zerstören baumartige Datenstruktur Arbeit. Es muss darauf geachtet werden, keine Vergleichsfunktion zum Sortieren, Suchen, Baumaufbau bereitzustellen, die eine vorzeichenlose ganzzahlige Subtraktion verwendet, um abzuleiten, welcher Schlüssel höher oder niedriger ist.

Siehe Beispiel unten.

#include <stdint.h>
#include <stdio.h>

void main()
{
    uint8_t a = 255;
    uint8_t b = 100;
    uint8_t c = 150;

    printf("uint8_t a = %+d, b = %+d, c = %+d\n\n", a, b, c);

    printf("          b - a  = %+d\tpromotion to int type\n"
           " (int8_t)(b - a) = %+d\n\n"
           "          b + a  = %+d\tpromotion to int type\n"
           "(uint8_t)(b + a) = %+d\tmodular arithmetic\n"
           "     b + a %% %d = %+d\n\n", 
           b - a,  (int8_t)(b - a), 
           b + a, (uint8_t)(b + a),
           UINT8_MAX + 1,
           (b + a) % (UINT8_MAX + 1));

    printf("c %s b (b - c = %d), b %s a (b - a = %d), AND c %s a (c - a = %d)\n",
           (int8_t)(c - b) < 0 ? "<" : ">", (int8_t)(c - b),
           (int8_t)(b - a) < 0 ? "<" : ">", (int8_t)(b - a),
           (int8_t)(c - a) < 0 ? "<" : ">", (int8_t)(c - a));
}

$ ./a.out 
uint8_t a = +255, b = +100, c = +150

          b - a  = -155 promotion to int type
 (int8_t)(b - a) = +101

          b + a  = +355 promotion to int type
(uint8_t)(b + a) = +99  modular arithmetic
     b + a % 256 = +99

c > b (b - c = 50), b > a (b - a = 101), AND c < a (c - a = -105)

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

std::abs ist nicht “geeignet” für Ganzzahlen ohne Vorzeichen. Eine Besetzung ist jedoch erforderlich.