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


209

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?


50
Prawdopodobnie dlatego, że istnieje więcej niż jeden sposób reprezentowania podpisanych liczb całkowitych. Który sposób nie jest określony w standardzie, a przynajmniej nie w C ++.
juanchopanza,


7
To, co powiedziała juanchopanza, ma sens. Jak rozumiem, oryginalny standard C w dużej części skodyfikował istniejącą praktykę. Jeśli wszystkie implementacje w tym czasie zgodziły się co do tego, co powinien zrobić „przepełnienie” bez znaku, to dobry powód, aby go ujednolicić. Nie zgodzili się co do tego, co powinno zrobić podpisane przepełnienie, więc nie weszło w standard.

2
@DavidElliman Niepodpisane zawijanie przy dodawaniu jest również łatwe do wykrycia ( if (a + b < a)). Przepełnienie przy mnożeniu jest trudne zarówno dla typów podpisanych, jak i niepodpisanych.

5
@DavidElliman: Nie chodzi tylko o to, czy można to wykryć, ale o wynik. W implementacji znak + wartość MAX_INT+1 == -0, podczas gdy na uzupełnieniu dwójki byłbyINT_MIN
David Rodríguez - dribeas

Odpowiedzi:


163

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.


6
Ważna uwaga jest jednak taka, że we współczesnym świecie nie ma architektury używającej arytmetyki z dopełnieniem 2. To, że standardy językowe nadal pozwalają na implementację np. PDP-1, jest czystym historycznym artefaktem.
Andy Ross,

9
@AndyRoss, ale nadal istnieją systemy (kompilatory OS +, co prawda ze starą historią) z uzupełnieniem i nowymi wersjami od 2013 roku. Przykład: OS 2200.
ouah

3
@Andy Ross, czy uważasz, że „nie ma architektur… wykorzystujących coś innego niż uzupełnienie 2…” obejmuje dzisiaj gamę procesorów DSP i wbudowanych procesorów?
chux - Przywróć Monikę

11
@AndyRoss: Chociaż istnieją „nie” architektury wykorzystujące coś innego niż uzupełnienie 2s (dla pewnej definicji „nie”), zdecydowanie istnieją architektury DSP, które używają arytmetyki nasycania dla liczb całkowitych ze znakiem.
Stephen Canon

10
Nasycona arytmetyka ze znakiem jest zdecydowanie zgodna ze standardem. Oczywiście należy stosować instrukcje zawijania dla arytmetyki bez znaku, ale kompilator zawsze ma informacje, aby wiedzieć, czy wykonywana jest arytmetyka bez znaku lub podpisana, więc z pewnością może odpowiednio wybrać instrukcje.
caf

15

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


23
Kompilatory nie chcą, abyś polegał na tym, że robią to dobrze, a większość z nich pokaże ci to, gdy tylko skompilujesz int f(int x) { return x+1>x; }z optymalizacją. GCC i ICC optymalizują powyższe opcje przy użyciu domyślnych opcji return 1;.
Pascal Cuoq,

1
Przykład programu, który daje różne wyniki w przypadku intprzepełnienia w zależności od poziomów optymalizacji, zobacz ideone.com/cki8nM Myślę, że to pokazuje, że twoja odpowiedź zawiera złe porady.
Magnus Hoff,

Trochę poprawiłem tę część.
Mats Petersson,

Gdyby C miał zapewnić sposób deklarowania liczby całkowitej „zawijanie ze znakiem uzupełnienia do dwóch”, żadna platforma, która może w ogóle uruchomić C, nie powinna mieć większych problemów z utrzymaniem go co najmniej umiarkowanie wydajnie. Dodatkowy narzut wystarczyłby, aby kod nie używał takiego typu, gdy zachowanie zawijania nie jest wymagane, ale większość operacji na liczbach całkowitych dopełniacza dwóch jest identyczna z operacjami na liczbach całkowitych bez znaku, z wyjątkiem porównań i promocji.
supercat

1
Wartości ujemne muszą istnieć i „działać”, aby kompilator działał poprawnie. Oczywiście jest całkowicie możliwe obejście braku podpisanych wartości w procesorze i stosowanie wartości niepodpisanych, jako uzupełnień lub uzupełnień dwójkowych, w zależności od tego, który z nich jest najbardziej wyczucie oparte na zestawie instrukcji. Zwykle byłoby to znacznie wolniejsze niż obsługa sprzętu, ale nie różni się od procesorów, które nie obsługują zmiennoprzecinkowego sprzętu lub podobnie - po prostu dodaje dużo dodatkowego kodu.
Mats Petersson

10

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.


6

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.


Nie do końca rozumiem - dlaczego pomaga mieć odwrotność dodatku? Naprawdę nie mogę wymyślić żadnej sytuacji, w której zachowanie przy przepełnieniu jest rzeczywiście przydatne ...
sleske

@sleske: Używanie dziesiętnego dla czytelności dla człowieka, jeśli licznik energii czyta 0003, a poprzedni odczyt wynosił 9995, czy to oznacza, że ​​użyto -9992 jednostek energii, czy użyto 0008 jednostek energii? Mając 0003-9995 wydajność 0008 ułatwia obliczenie tego ostatniego wyniku. Uzyskanie wydajności -9992 sprawiłoby, że byłoby to trochę bardziej niezręczne. Brak możliwości uczynienia tego wymagałby jednak porównania 0003 do 9995, zauważ, że jest mniej, wykonaj odejmowanie odwrotne, odejmij wynik z 9999 i dodaj 1.
supercat

@sleske: Jest to również bardzo przydatne dla ludzi i kompilatorów, aby móc stosować asocjacyjne, dystrybucyjne i przemienne prawa arytmetyki do przepisywania wyrażeń i upraszczania ich; Na przykład, jeśli wyrażenie a+b-cjest obliczane w pętli, ale bi csą stałe wewnątrz tej pętli, może to być pomocne, aby przenieść obliczenia (b-c)zewnątrz pętli, ale robi to wymagałoby wśród innych rzeczy, które (b-c)dają wartość, która po dodaniu do a, przyniesie a+b-c, co z kolei wymaga codwrotności dodatku.
supercat

: Dzięki za wyjaśnienia. Jeśli dobrze to rozumiem, wszystkie twoje przykłady zakładają, że naprawdę chcesz poradzić sobie z przepełnieniem. W większości przypadków, które napotkałem, przepełnienie jest niepożądane i chcesz temu zapobiec, ponieważ wynik obliczenia z przepełnieniem nie jest użyteczny. Na przykład w przypadku licznika energii prawdopodobnie chcesz użyć takiego typu, aby przelew nigdy się nie pojawiał.
śleske

1
... taki, który (a+b)-cjest równy, a+(b-c)czy wartość arytmetyczna b-cjest reprezentowalna w obrębie typu, podstawienie będzie ważne bez względu na możliwy zakres wartości dla (b-c).
supercat

1

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.


Aby struktura była polem, każdy element struktury inny niż tożsamość addytywna musi mieć multiplikatywną odwrotność. Struktura liczb całkowitych przystających mod N będzie polem tylko wtedy, gdy N jest jednym lub pierwszym [pole zdegenerowane, gdy N == 1]. Czy czujesz, że brakuje mi odpowiedzi?
supercat

Masz rację. Zdezorientowały mnie moduły mocy pierwotnej. Oryginalna odpowiedź została edytowana.
yth

Extra mylące jest to, że nie jest to dziedzina rzędu 2 ^ n, to jest po prostu nie ring-izomorficzne do liczb całkowitych modulo 2 ^ n.
Kevin Ventullo

A 2 ^ 31-1 to Mersenne Prime (ale 2 ^ 63-1 nie jest liczbą pierwszą). Tak więc mój oryginalny pomysł został zrujnowany. Ponadto, liczby całkowite były różne w ciągu dnia. Więc mój pomysł był w najlepszym razie rewizjonistyczny.
yth

Fakt, że niepodpisane liczby całkowite tworzą pierścień (a nie pole), pobranie części niskiego rzędu również daje pierścień, a wykonywanie operacji na całej wartości, a następnie obcięcie zachowuje się tak samo, jak wykonywanie operacji tylko na dolnej części, gdzie IMHO prawie na pewno względy.
supercat
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.