Dlaczego zachowanie związane z przepełnieniem liczb całkowitych bez znaku jest zdefiniowane, a przepełnienie ze znakiem całkowitym nie?

Niepisane przepełnienie liczb całkowitych jest dobrze zdefiniowane zarówno przez standardy C, jak i C ++. Na przykład stwierdza stan C99 standard ( §6.2.5/9)

Obliczenia obejmujące niepodpisane operandy nigdy nie mogą się przepełnić, ponieważ wynik, który nie może być reprezentowany przez wynikowy typ liczb całkowitych bez znaku, jest zmniejszany modulo o liczbę, która jest o jeden większa od największej wartości, jaką może reprezentować wynikowy typ.

Jednak oba standardy stwierdzają, że podpisane przepełnienie liczb całkowitych jest zachowaniem niezdefiniowanym. Ponownie, ze standardu C99 ( §3.4.3/1)

Przykładem nieokreślonego zachowania jest zachowanie przy przepełnieniu liczby całkowitej

Czy istnieje jakaś historyczna lub (jeszcze lepsza!) Techniczna przyczyna tej rozbieżności?

Historyczny powód jest taki, że większość implementacji C (kompilatorów) właśnie używała takiego zachowania przepełnienia, które było najłatwiejsze do wdrożenia z zastosowaną reprezentacją liczb całkowitych. Implementacje w języku C zwykle używały tej samej reprezentacji, z której korzysta procesor - więc zachowanie związane z przepełnieniem wynikało z reprezentacji liczb całkowitych używanych przez procesor.

W praktyce tylko reprezentacje podpisanych wartości mogą się różnić w zależności od implementacji: uzupełnienie własne, uzupełnienie dwóch, wielkość znaku. Dla typu bez znaku nie ma powodu, aby standard zezwalał na zmiany, ponieważ istnieje tylko jedna oczywista reprezentacja binarna (standard zezwala tylko na reprezentację binarną).

Odpowiednie cytaty:

C99 6.2.6.1:3 :

Wartości przechowywane w niepodpisanych polach bitowych i obiektach typu unsigned char powinny być reprezentowane przy użyciu czystej notacji binarnej.

C99 6.2.6.2:2 :

Jeśli bit znaku ma wartość jeden, wartość należy zmodyfikować na jeden z następujących sposobów:

- odpowiednia wartość z bitem znaku 0 jest zanegowana ( znak i wielkość );

- bit znaku ma wartość - (2 ^N ) ( uzupełnienie dwóch );

- bit znaku ma wartość - (2 ^N - 1) ( uzupełnienie własne ).

Obecnie wszystkie procesory używają reprezentacji uzupełnienia do dwóch, ale podpisane przepełnienie arytmetyczne pozostaje niezdefiniowane, a twórcy kompilatorów chcą, aby pozostała niezdefiniowana, ponieważ używają tej niezdefiniowanej pomocy do optymalizacji. Zobacz na przykład ten post na blogu Iana Lance'a Taylora lub skargę Agnera Foga oraz odpowiedzi na jego raport o błędzie.

Oprócz dobrej odpowiedzi Pascala (jestem pewien, że to główna motywacja), możliwe jest również, że niektóre procesory powodują wyjątek w przypadku przepełnienia liczby całkowitej ze znakiem, co oczywiście spowodowałoby problemy, gdyby kompilator musiał „zorganizować inne zachowanie” ( np. użyj dodatkowych instrukcji, aby sprawdzić potencjalne przepełnienie i w takim przypadku obliczyć inaczej).

Warto również zauważyć, że „niezdefiniowane zachowanie” nie oznacza „nie działa”. Oznacza to, że wdrożenie może robić, co chce w tej sytuacji. Obejmuje to robienie „właściwych rzeczy”, a także „wezwania policji” lub „rozbicia się”. Większość kompilatorów, jeśli to możliwe, wybiera „rób to, co należy”, zakładając, że jest to stosunkowo łatwe do zdefiniowania (w tym przypadku tak jest). Jeśli jednak występują przepełnienia w obliczeniach, ważne jest, aby zrozumieć, co tak naprawdę powoduje, i że kompilator MOŻE zrobić coś innego niż się spodziewasz (i że może to bardzo zależeć od wersji kompilatora, ustawień optymalizacji itp.) .

Przede wszystkim należy pamiętać, że C11 3.4.3, podobnie jak wszystkie przykłady i nuty, nie jest tekstem normatywnym, a zatem nie ma sensu cytować!

Odpowiedni tekst stwierdzający, że przepełnienie liczb całkowitych i liczb zmiennoprzecinkowych jest niezdefiniowanym zachowaniem, jest następujący:

C11 6,5 / 5

Jeśli podczas oceny wyrażenia wystąpi wyjątkowy warunek (to znaczy, jeśli wynik nie jest zdefiniowany matematycznie lub nie mieści się w zakresie reprezentatywnych wartości dla jego typu), zachowanie jest niezdefiniowane.

Wyjaśnienie dotyczące zachowania niepodpisanych typów liczb całkowitych można znaleźć tutaj:

C11 6.2.5 / 9

Zakres nieujemnych wartości podpisanego typu liczby całkowitej jest podzakresem odpowiadającego typu liczby całkowitej bez znaku, a reprezentacja tej samej wartości w każdym typie jest taka sama. Obliczenia obejmujące niepodpisane operandy nigdy nie mogą się przepełnić, ponieważ wynikiem, który nie może być reprezentowany przez wynikowy typ liczb całkowitych bez znaku, jest zmniejszone modulo liczba, która jest o jeden większa od największej wartości, jaką może reprezentować wynikowy typ.

To sprawia, że ​​typy całkowite bez znaku są specjalnym przypadkiem.

Należy również pamiętać, że istnieje wyjątek, jeśli dowolny typ jest konwertowany na typ podpisany, a starej wartości nie można już reprezentować. Zachowanie jest wówczas jedynie definiowane w ramach implementacji, chociaż sygnał może zostać podniesiony.

C11 6.3.1.3

6.3.1.3 Liczba całkowita ze znakiem i bez znaku

Gdy wartość o typie całkowitym jest konwertowana na inny typ liczb całkowitych inny niż _Bool, jeśli wartość może być reprezentowana przez nowy typ, pozostaje niezmieniona.

W przeciwnym razie, jeśli nowy typ nie jest podpisany, wartość jest konwertowana przez wielokrotne dodawanie lub odejmowanie wartości większej niż maksymalna wartość, którą można przedstawić w nowym typie, dopóki wartość nie znajdzie się w zakresie nowego typu.

W przeciwnym razie nowy typ jest podpisany i nie można w nim reprezentować wartości; albo wynik jest zdefiniowany w implementacji, albo podniesiony jest sygnał zdefiniowany w implementacji.

Oprócz innych wspomnianych problemów, posiadanie niepodpisanego zawijania matematycznego powoduje, że niepodpisane typy liczb całkowitych zachowują się jak abstrakcyjne grupy algebraiczne (co oznacza, że ​​między innymi dla dowolnej pary wartości Xi Ybędą istniały inne wartości Z, które X+Z, jeśli zostaną poprawnie rzutowane , równa Yi Y-Zbędzie, jeśli odpowiednio rzucona, równaX). Jeśli niepodpisane wartości były jedynie typami lokalizacji do przechowywania, a nie typami wyrażeń pośrednich (np. Jeśli nie było żadnego niepodpisanego odpowiednika największego typu liczby całkowitej, a operacje arytmetyczne na niepodpisanych typach zachowywały się tak, jakby były najpierw konwertowane na większe typy ze znakiem, wówczas nie byłoby takiej potrzeby zdefiniowanego zachowania zawijania, ale trudno jest wykonać obliczenia w typie, który nie ma np. odwrotności addytywnej.

Pomaga to w sytuacjach, gdy zachowanie zawijania jest rzeczywiście przydatne - na przykład przy numerach sekwencji TCP lub niektórych algorytmach, takich jak obliczanie wartości skrótu. Może to również pomóc w sytuacjach, w których konieczne jest wykrycie przepełnienia, ponieważ wykonywanie obliczeń i sprawdzenie, czy przepełnienie jest często łatwiejsze niż wcześniejsze sprawdzenie, czy przepełnią, szczególnie jeśli obliczenia dotyczą największej dostępnej liczby całkowitej.

Być może innym powodem, dla którego zdefiniowano arytmetykę bez znaku, jest to, że liczby bez znaku tworzą liczby całkowite modulo 2 ^ n, gdzie n jest szerokością liczby bez znaku. Numery niepodpisane są po prostu liczbami całkowitymi reprezentowanymi za pomocą cyfr binarnych zamiast cyfr dziesiętnych. Wykonywanie standardowych operacji w systemie modułowym jest dobrze zrozumiałe.

Cytat PO odnosi się do tego faktu, ale także podkreśla fakt, że istnieje tylko jeden, jednoznaczny, logiczny sposób reprezentowania liczb całkowitych bez znaku w systemie binarnym. Natomiast liczby podpisane są najczęściej reprezentowane za pomocą uzupełnienia do dwóch, ale możliwe są inne wybory, jak opisano w normie (sekcja 6.2.6.2).

Reprezentacja uzupełnienia Two pozwala niektórym operacjom na bardziej sensowny w formacie binarnym. Np. Inkrementacja liczb ujemnych jest taka sama jak dla liczb dodatnich (należy się spodziewać w warunkach przepełnienia). Niektóre operacje na poziomie komputera mogą być takie same dla numerów podpisanych i niepodpisanych. Jednak przy interpretacji wyników tych operacji niektóre przypadki nie mają sensu - przepełnienie dodatnie i ujemne. Ponadto wyniki przepełnienia różnią się w zależności od podpisanej reprezentacji.