Pytanie Czy zdefiniowane zachowanie bez znaku jest całkowitym odejmowaniem?


Znalazłem kod od kogoś, kto wydaje się wierzyć, że istnieje problem z odjęciem liczby całkowitej bez znaku od innej liczby tego samego typu, gdy wynik byłby ujemny. Tak więc kod taki jak ten byłby niepoprawny, nawet gdyby zadziałał na większości architektur.

unsigned int To, Tf;

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

Jest to jedyny mało konkretny cytat ze standardu C, jaki mogłem znaleźć.

Obliczenia zawierające niepodpisane operandy nie mogą nigdy przepłynąć, ponieważ a   wynik, który nie może być reprezentowany przez wynikową liczbę całkowitą bez znaku   typ jest zredukowany modulo o liczbę większą od największej   wartość, która może być reprezentowana przez wynikowy typ.

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

to znaczy

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

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

0x0000 - 0x0001 == (unsigned) (0 + -1) == (0xFFFF ale również 0xFFFE lub 0x8001)

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


76
2017-08-28 13:59


pochodzenie


Wybó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żywając terminologii w standardzie, zamiast przepełniać wartość "opakowuje". - danorton


Odpowiedzi:


Wynik odejmowania generującego liczbę ujemną w niepodpisanym typie jest dobrze zdefiniowany:

  1. [...] Obliczenia zawierające niepodpisane operandy nigdy nie mogą się przepełnić,   ponieważ wynik, który nie może być reprezentowany przez wynikowy unsigned integer type   zmniejszona liczba modulo o jeden większy od największej możliwej wartości   reprezentowany przez wynikowy typ.   (ISO / IEC 9899: 1999 (E) §6.2.5 / 9)

Jak widzisz, (unsigned)0 - (unsigned)1 wynosi -1 modulo UINT_MAX + 1 lub innymi słowy UINT_MAX.

Zauważ, że chociaż mówi: "Obliczenia zawierające niepodpisane operandy nigdy nie mogą się przepełnić", co może prowadzić do przekonania, że ​​dotyczy tylko przekroczenia górnego limitu, jest to przedstawione jako motywacja dla rzeczywistej części wiążącej zdania: "wynik, który nie może być reprezentowany przez wynikowy unsigned integer type zmniejszona liczba modulo o jeden większy od największej możliwej wartości reprezentowany przez wynikowy typ. "Ta fraza nie jest ograniczona do przepełnienia górnej granicy typu i odnosi się w równym stopniu do wartości zbyt niskich, aby mogła być reprezentowana.


84
2017-08-28 14:06



Dziękuję Ci! Teraz widzę interpretację, której mi brakowało. Myślę, że mogli wybrać bardziej przejrzyste sformułowanie. - jbcreix
Teraz czuję się o wiele lepiej, wiedząc, że jeśli jakikolwiek niepodpisany dodatek wypadnie do zera i wywoła chaos, będzie to spowodowane tym, że uint zawsze miał reprezentować matematyczne pierścień z liczb całkowitych 0 przez UINT_MAX, z operacjami dodawania i mnożenia modulo UINT_MAX+1, a nie z powodu przepełnienia. Pyta jednak, dlaczego, jeśli pierścienie są takim podstawowym typem danych, język nie oferuje bardziej ogólnej obsługi pierścieni o innych rozmiarach. - Theodore Murdock
@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, aby niepodpisane typy miały wszystkie bity uczestniczące w reprezentacji wartości. Zachowanie pierścieniowe płynie z tego naturalnie. Jeśli chcesz takie zachowanie od innych typów, to wykonaj swoją arytmetykę, a następnie zastosuj wymagany moduł; który używa podstawowych operatorów. - underscore_d
@ longerscore_d Oczywiście ... jasne jest, dlaczego podjęli decyzję o projekcie. To zabawne, że napisali specyfikację z grubsza jako "nie ma arytmetyki nad / niedopełnienia, ponieważ typ danych jest określany jako pierścień", tak jakby ten wybór projektu oznaczał, że programiści nie musieli starannie unikać over- i under -flow lub ich programy nie działają spektakularnie. - Theodore Murdock


Kiedy pracujesz z niepodpisany typy, arytmetyka modułowa (znany również jako "owinąć" zachowanie). Aby to zrozumieć arytmetyka modułowa, spójrz na te zegary:

enter image description here 

9 + 4 = 1 (13 mod 12), więc w przeciwnym kierunku jest: 1 - 4 = 9 (-3 mod 12). Ta sama zasada jest stosowana podczas pracy z typami bez znaku. Jeśli typ wyniku jest unsigned, następnie ma miejsce arytmetyka modularna.


Teraz spójrz na następujące operacje przechowywania wyniku 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

Kiedy chcesz się upewnić, że wynik jest signed, a następnie zapisał go w signedZmienna lub rzutuj na signed. Jeśli chcesz uzyskać różnicę między liczbami i upewnić się, że modularna arytmetyka nie zostanie zastosowana, powinieneś rozważyć użycie abs() funkcja zdefiniowana w stdlib.h:

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

Bądź bardzo ostrożny, zwłaszcza podczas pisania warunków, 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)
    // ...

96
2018-02-22 17:56



Niezły z zegarkami dowód czy to poprawna odpowiedź. Przesłanka pytania zawiera już stwierdzenie, że wszystko to może być prawdą. - Lightness Races in Orbit
@LightnessRacesinOrbit: Dziękuję. Napisałem to, ponieważ uważam, że ktoś może uznać to za bardzo pomocne. Zgadzam się, że to nie jest kompletna odpowiedź. - LihO
Linia int d = abs(five - seven); nie jest dobrze. Pierwszy five - seven jest obliczana: promocja pozostawia typy operandów jako unsigned int, wynik jest obliczany modulo (UINT_MAX+1)i ocenia UINT_MAX-1. Wtedy ta wartość jest faktycznym parametrem do abs, co jest złą wiadomością. abs(int) powoduje niezdefiniowane zachowanie przechodzące przez argument, ponieważ nie jest w zasięgu, i abs(long long) może prawdopodobnie posiadać wartość, ale niezdefiniowane zachowanie występuje, gdy zwracana jest wartość int zainicjować d. - Ben Voigt
@LihO: Jedynym operatorem w C ++, który jest kontekstowy i działa inaczej w zależności od tego, w jaki sposób jest używany jego wynik, jest niestandardowy operator konwersji operator T(). Dodatek w dwóch wyrażeniach, które omawiamy, jest wykonywany w typie unsigned int, w oparciu o typy argumentów. Wynik dodania jest unsigned int. Następnie wynik ten jest niejawnie konwertowany na typ wymagany w kontekście, konwersja, która kończy się niepowodzeniem, ponieważ wartości nie można przedstawić w nowym typie. - Ben Voigt
@LihO: To może pomóc w przemyśleniu double x = 2/3; vs double y = 2.0/3; - Ben Voigt


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

Ponownie, twoja pierwsza interpretacja jest poprawna. Niepodpisana arytmetyka jest zgodna z zasadami arytmetyki modulo, co oznacza, że 0x0000 - 0x0001 ocenia na 0xFFFF w przypadku 32-bitowych typów bez znaku.

Jednak druga interpretacja (ta oparta na "podpisanej semantyki") jest również wymagana do uzyskania tego samego wyniku. To znaczy. nawet jeśli oceniasz 0 - 1 w dziedzinie podpisanego typu i uzyskania -1 jako wynik pośredni, to -1 jest nadal wymagane do produkcji 0xFFFF gdy później zostanie przekonwertowany na niepodpisany typ. Nawet jeśli platforma używa egzotycznej reprezentacji dla liczb całkowitych ze znakiem (dopełnienie 1, wielkość znaku), to ta platforma nadal wymaga stosowania reguł arytmetycznych modulo przy konwersji wartości liczb całkowitych ze znakiem na niepodpisane.

Na przykład ta ocena

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

jest wciąż gwarantowane UINT_MAX w c, nawet jeśli platforma używa egzotycznej reprezentacji dla liczb całkowitych ze znakiem.


3
2018-02-22 18:22



Myślę, że masz na myśli 16-bitowe rodzaje bez znaku, a nie 32-bitowe. - xioxox


Z niepodpisanymi numerami typu unsigned int lub większe, w przypadku braku konwersji typu, a-b jest zdefiniowany jako generujący niepodpisany numer, który po dodaniu b, przyniesie a. Konwersja liczby ujemnej na niepodpisaną definiuje się jako liczbę, która po dodaniu do oryginalnego numeru odwróconego znakiem przyniesie zero (więc konwersja -5 na niepodpisaną da wartość, która po dodaniu do 5 da zero) .

Zwróć uwagę, że liczby bez znaku mniejsze niż unsigned int może zostać awansowany na typ int przed odejmowaniem zachowanie a-b będzie zależeć od wielkości int.


2
2018-01-09 17:22