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

100

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?

LihO
źródło
3
Dobór słów w standardzie jest niefortunny. To, że „nigdy nie może się przepełnić” oznacza, że ​​nie jest to sytuacja błędu. Używanie terminologii w standardzie zamiast przepełniania wartości „wrap”.
danorton

Odpowiedzi:

107

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.

bdonlan
źródło
2
Dziękuję Ci! Teraz widzę interpretację, której brakowało. Myślę jednak, że mogli wybrać jaśniejsze sformułowanie.
4
Czuję się teraz o wiele lepiej, wiedząc, że jeśli jakiekolwiek dodawanie bez znaku przetoczy się do zera i spowoduje chaos, będzie tak, ponieważ uintzawsze miał reprezentować matematyczny pierścień liczb całkowitych 0do UINT_MAX, z operacjami dodawania i mnożenia modulo UINT_MAX+1, a nie dlatego, że przelewu. Jednak nasuwa się pytanie, dlaczego, jeśli pierścienie są tak podstawowym typem danych, język nie oferuje bardziej ogólnego wsparcia dla pierścieni o innych rozmiarach.
Theodore Murdock
2
@TheodoreMurdock Myślę, że odpowiedź na to pytanie jest prosta. O ile wiem, fakt, że jest to pierścień, jest konsekwencją, a nie przyczyną. Prawdziwym wymaganiem jest to, że typy bez znaku muszą mieć wszystkie swoje bity uczestniczące w reprezentacji wartości. Naturalnie z tego wynika zachowanie przypominające pierścień. Jeśli chcesz takiego zachowania od innych typów, wykonaj swoją arytmetykę, a następnie zastosuj wymagany moduł; który używa operatorów podstawowych.
podkreślenie_d
@underscore_d Oczywiście ... jest jasne, dlaczego podjęli decyzję projektową. To po prostu zabawne, że napisali specyfikację mniej więcej tak, że "nie ma arytmetycznego przepełnienia / niedomiaru, ponieważ typ danych jest określony jako pierścień", jakby ten wybór projektu oznaczał, że programiści nie muszą ostrożnie unikać nadmiernego i niedostatecznego -flow lub sprawić, że ich programy zawodzą spektakularnie.
Theodore Murdock
121

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:

wprowadź opis obrazu tutaj

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)
    // ...
LihO
źródło
4
Niezły z zegarami, chociaż dowód potwierdziłby, że jest to poprawna odpowiedź. Przesłanka pytania zawiera już stwierdzenie, że wszystko to może być prawdą.
Wyścigi lekkości na orbicie
5
@LightnessRacesinOrbit: Dziękuję. Napisałem to, ponieważ myślę, że ktoś może uznać to za bardzo pomocne. Zgadzam się, że to nie jest pełna odpowiedź.
LihO
4
Linia int d = abs(five - seven);nie jest dobra. Pierwsza five - sevenjest obliczana: promocja pozostawia typy operandów jako unsigned int, wynik jest obliczany modulo (UINT_MAX+1)i obliczany do UINT_MAX-1. Wtedy ta wartość jest rzeczywistym parametrem to abs, co jest złą wiadomością. abs(int)powoduje przekazanie argumentu przez niezdefiniowane zachowanie, ponieważ nie jest on w zakresie i abs(long long)prawdopodobnie może przechowywać wartość, ale niezdefiniowane zachowanie występuje, gdy wartość zwracana jest zmuszana intdo zainicjowania d.
Ben Voigt
1
@LihO: jedynym operatorem w C ++, który jest zależny od kontekstu i działa inaczej w zależności od tego, jak jest używany jego wynik, jest niestandardowy operator konwersji operator T(). Dodatek w dwóch omawianych wyrażeniach jest wykonywany w typie unsigned intna podstawie typów operandów. Wynik dodawania to unsigned int. Następnie ten wynik jest niejawnie konwertowany na typ wymagany w kontekście, konwersja, która kończy się niepowodzeniem, ponieważ wartość nie jest reprezentowalna w nowym typie.
Ben Voigt,
1
@LihO: Warto pomyśleć o double x = 2/3;vsdouble y = 2.0/3;
Ben Voigt
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.

Mrówka
źródło
4
Myślę, że masz na myśli 16-bitowe typy bez znaku, a nie 32-bitowe.
xioxox
4

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.

supercat
źródło