Czy odejmowanie liczb całkowitych bez znaku jest zdefiniowane jako zachowanie?

Natknąłem się na kod kogoś, kto wydaje się sądzić, że istnieje problem z odejmowaniem liczby całkowitej bez znaku od innej liczby całkowitej tego samego typu, gdy wynik byłby ujemny. Tak więc taki kod byłby niepoprawny, nawet gdyby działał na większości architektur.

unsigned int To, Tf;

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

To jedyny niejasny cytat ze standardu C, jaki udało mi się znaleźć.

Obliczenie obejmujące operandy bez znaku nigdy nie może przekroczyć wartości, ponieważ wynik, którego nie można przedstawić za pomocą wynikowego typu liczby całkowitej bez znaku, jest redukowany modulo o liczbę, która jest o jeden większa niż największa wartość, która może być reprezentowana przez wynikowy typ.

Przypuszczam, że można by przyjąć, że ten cytat oznacza, że ​​gdy prawy operand jest większy, operacja jest dostosowywana tak, aby była sensowna w kontekście liczb obciętych modulo.

to znaczy

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

w przeciwieństwie do używania semantyki ze znakiem zależnej od implementacji:

0x0000 - 0x0001 == (unsigned) (0 + -1) == (0xFFFF ale także 0xFFFE lub 0x8001)

Która lub jaka interpretacja jest właściwa? Czy to w ogóle jest zdefiniowane?

Wynik odejmowania generujący liczbę ujemną w typie bez znaku jest dobrze zdefiniowany:

1. [...] Obliczenie obejmujące operandy bez znaku nigdy nie może się przepełnić, ponieważ wynik, który nie może być reprezentowany przez wynikowy typ liczby całkowitej bez znaku, jest redukowany modulo o liczbę większą o jeden niż największa wartość, która może być reprezentowana przez wynikowy typ. (ISO / IEC 9899: 1999 (E) § 6.2.5 / 9)

Jak widać, (unsigned)0 - (unsigned)1wynosi -1 modulo UINT_MAX + 1, czyli innymi słowy UINT_MAX.

Zauważ, że chociaż mówi "Obliczenie obejmujące operandy bez znaku nigdy nie może się przepełnić", co może prowadzić do wniosku, że ma zastosowanie tylko do przekroczenia górnej granicy, jest to przedstawiane jako motywacja dla rzeczywistej wiążącej części zdania: "a wynik, który nie może być reprezentowany przez wynikowy typ liczby całkowitej bez znaku, jest redukowany modulo liczba, która jest o jeden większa niż największa wartość, która może być reprezentowana przez wynikowy typ. " Ta fraza nie ogranicza się do przekroczenia górnej granicy typu i dotyczy w równym stopniu wartości zbyt niskich, aby mogły być przedstawione.

Kiedy pracujesz z typami bez znaku , ma miejsce arytmetyka modularna (znana również jako zachowanie „zawijania” ). Aby zrozumieć arytmetykę modularną , wystarczy spojrzeć na te zegary:

9 + 4 = 1 ( 13 mod 12 ), więc w drugą stronę jest: 1 - 4 = 9 ( -3 mod 12 ). Ta sama zasada obowiązuje podczas pracy z typami bez znaku. Jeśli typ wyniku to unsigned, to wykonywana jest arytmetyka modularna.

Teraz spójrz na następujące operacje przechowujące wynik jako 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

Jeśli chcesz się upewnić, że wynik jest signed, zapisz go w signedzmiennej lub przerzuć na signed. Jeśli chcesz uzyskać różnicę między liczbami i upewnić się, że arytmetyka modularna nie zostanie zastosowana, powinieneś rozważyć użycie abs()funkcji zdefiniowanej w stdlib.h:

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

Zachowaj szczególną ostrożność, szczególnie w warunkach pisania, ponieważ:

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

ale

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

if (one - six < five)   // = if ((unsigned int)-5 < 5) = if (4294967291 < 5)
    // ...

Cóż, pierwsza interpretacja jest poprawna. Jednak twoje rozumowanie dotyczące „semantyki ze znakiem” w tym kontekście jest błędne.

Twoja pierwsza interpretacja jest poprawna. Arytmetyka bez znaku jest zgodna z zasadami arytmetyki modulo, co oznacza, że 0x0000 - 0x0001wartościuje do0xFFFF bez znaku jest dla 32-bitowych typów bez znaku.

Jednak druga interpretacja (oparta na „semantyce ze znakiem”) jest również wymagana do uzyskania tego samego wyniku. To znaczy, nawet jeśli oceniasz 0 - 1w domenie typu podpisanego i otrzymujesz -1jako wynik pośredni, -1nadal jest to wymagane do wyprodukowania0xFFFF gdy później zostanie przekonwertowany na typ bez znaku. Nawet jeśli na niektórych platformach używane są egzotyczne reprezentacje liczb całkowitych ze znakiem (uzupełnienie 1, wielkość ze znakiem), platforma ta nadal musi stosować zasady arytmetyki modulo podczas konwersji wartości całkowitych ze znakiem na liczby całkowite bez znaku.

Na przykład ta ocena

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

jest jeszcze gwarancją produkować UINT_MAXw c, nawet jeśli platforma jest za pomocą egzotycznych reprezentacji dla podpisanych liczb całkowitych.

W przypadku liczby typu bez znaku unsigned intlub większej, w przypadku braku konwersji typu, a-bdefiniuje się liczbę bez znaku, która po dodaniu bda wynik a. Konwersja liczby ujemnej na liczbę bez znaku jest definiowana jako otrzymanie liczby, która po dodaniu do pierwotnej liczby odwróconej znakiem da zero (więc zamiana -5 na unsigned da wartość, która po dodaniu do 5 da zero) .

Zauważ, że liczby bez znaku mniejsze niż unsigned intmogą być promowane do typu intprzed odejmowaniem, zachowanie a-bbędzie zależeć od rozmiaru int.