Jeśli liczba jest zbyt duża, czy przenosi się do następnej lokalizacji w pamięci?

30

Przeglądałem programowanie w C i przeszkadza mi tylko kilka rzeczy.

Weźmy na przykład ten kod:

int myArray[5] = {1, 2, 2147483648, 4, 5};
int* ptr = myArray;
int i;
for(i=0; i<5; i++, ptr++)
    printf("\n Element %d holds %d at address %p", i, myArray[i], ptr);

Wiem, że int może pomieścić maksymalną wartość dodatnią 2 147 483 647. A zatem, przechodząc o jeden powyżej, „rozlewa się” na następny adres pamięci, co powoduje, że element 2 pojawia się pod tym adresem jako „-2147483648”? Ale to naprawdę nie ma sensu, ponieważ na wyjściu nadal jest napisane, że następny adres zawiera wartość 4, a następnie 5. Jeśli liczba przelałaby się na następny adres, to nie zmieniłoby to wartości zapisanej pod tym adresem ?

Nie pamiętam z programowania w MIPS Assembly i patrzenia, jak adresy zmieniają się podczas programu krok po kroku, że wartości przypisane do tych adresów zmieniają się.

O ile nie pamiętam niepoprawnie, oto kolejne pytanie: Jeśli liczba przypisana do określonego adresu jest większa niż typ (jak w myArray [2]), to czy nie wpływa to na wartości przechowywane pod kolejnym adresem?

Przykład: Mamy int myNum = 4 miliardy pod adresem 0x10010000. Oczywiście myNum nie może przechowywać 4 miliardów, więc pojawia się jako pewna liczba ujemna pod tym adresem. Mimo że nie jest w stanie zapisać tak dużej liczby, nie ma to wpływu na wartość przechowywaną pod kolejnym adresem 0x10010004. Poprawny?

Adresy pamięci mają po prostu wystarczającą ilość miejsca, aby pomieścić pewne rozmiary liczb / znaków, a jeśli rozmiar przekroczy limit, wówczas będzie reprezentowany inaczej (jak próba zapisania 4 miliardów w int, ale pojawi się jako liczba ujemna) i więc nie ma to wpływu na liczby / znaki przechowywane pod następnym adresem.

Przepraszam, jeśli poszedłem za burtę. Cały dzień miałem od tego pierdnięcie mózgu.

krępy
źródło
10
Być może mylisz się z przekroczeniami ciągu .
Robbie Dee,
19
Praca domowa: Zmienić prosty CPU tak, że ma wycieku. Przekonasz się, że logika staje się znacznie bardziej złożona, wszystko dla „funkcji”, która gwarantowałaby dziury w zabezpieczeniach wszędzie, bez bycia użytecznym w pierwszej kolejności.
phihag
4
Jeśli potrzebujesz naprawdę dużych liczb, możesz mieć reprezentację liczb, która zwiększy ilość pamięci używanej do zmieszczenia dużych liczb. Sam procesor nie może tego zrobić i nie jest to cecha języka C, ale biblioteka może to zaimplementować - powszechną biblioteką C jest biblioteka arytmetyczna GNU Multiple Precision . Biblioteka musi zarządzać pamięcią, aby przechowywać liczby, których koszt wydajności jest większy niż arytmetyka. Wiele języków ma wbudowane tego rodzaju funkcje (co nie pozwala uniknąć kosztów).
Steve314,
1
napisz prosty test, nie jestem programistą C, ale coś w stylu int c = INT.MAXINT; c+=1;i zobacz, co się stało z c.
JonH
2
@JonH: Problemem jest przepełnienie niezdefiniowanego zachowania. Kompilator AC może wykryć ten kod i wydedukować, że jest to kod nieosiągalny, ponieważ bezwarunkowo przepełnia się. Ponieważ nieosiągalny kod nie ma znaczenia, można go wyeliminować. Wynik końcowy: brak kodu.
MSalters

Odpowiedzi:

48

Nie. W C zmienne mają ustalony zestaw adresów pamięci do pracy. Jeśli pracujesz w systemie z 4 bajtami intsi ustawisz intzmienną na, 2,147,483,647a następnie dodasz 1, zmienna zwykle będzie zawierać -2147483648. (W większości systemów. Zachowanie jest w rzeczywistości niezdefiniowane.) Żadne inne lokalizacje pamięci nie zostaną zmodyfikowane.

Zasadniczo kompilator nie pozwoli ci przypisać wartości, która jest zbyt duża dla tego typu. To wygeneruje błąd kompilatora. Jeśli wymusisz to w przypadku, wartość zostanie obcięta.

Patrząc nieco bitowo, jeśli typ może przechowywać tylko 8 bitów i spróbujesz zmusić wartość 1010101010101do niego za pomocą skrzynki, skończysz z dolnymi 8 bitami lub 01010101.

W twoim przykładzie, niezależnie od tego, co zrobisz myArray[2], myArray[3]będzie zawierać „4”. Nie ma „przelewu”. Próbujesz umieścić coś, co ma więcej niż 4 bajty, po prostu odetnie wszystko z wyższej półki, pozostawiając dolne 4 bajty. W większości systemów spowoduje to -2147483648.

Z praktycznego punktu widzenia chcesz po prostu upewnić się, że tak się nigdy nie stanie. Tego rodzaju przepełnienia często powodują trudne do rozwiązania wady. Innymi słowy, jeśli uważasz, że istnieje jakakolwiek szansa, że ​​twoje wartości będą w miliardach, nie używaj int.

Gort the Robot
źródło
52
Jeśli pracujesz w systemie z 4-bajtowymi liczbami całkowitymi i ustawisz zmienną int na 2 147 483 647, a następnie dodasz 1, zmienna będzie zawierać -2147483648. => Nie , jest to niezdefiniowane zachowanie , więc może zapętlić się lub może zrobić coś zupełnie innego; Widziałem kompilatory optymalizujące kontrole w oparciu o brak przepełnienia i dostałem nieskończone pętle na przykład ...
Matthieu M.
Przepraszam, tak, masz rację. Powinienem dodać tam „zwykle”.
Gort the Robot
@MatthieuM z perspektywy językowej , to prawda. Jeśli chodzi o wykonanie w danym systemie, o czym tu mówimy, to absolutny nonsens.
hobbs
@ Hobbs: Problem polega na tym, że kiedy kompilatory zmieniają program z powodu niezdefiniowanego zachowania, faktyczne uruchomienie programu rzeczywiście spowoduje nieoczekiwane zachowanie, porównywalne w efekcie do nadpisywania pamięci.
Matthieu M.
24

Przepełnienie całkowitą ze znakiem jest zachowaniem niezdefiniowanym. Jeśli tak się stanie, twój program jest nieprawidłowy. Kompilator nie musi tego sprawdzać, więc może wygenerować plik wykonywalny, który wydaje się robić coś rozsądnego, ale nie ma gwarancji, że to zrobi.

Jednak przepełnienie liczb całkowitych bez znaku jest dobrze zdefiniowane. To zawinie modulo UINT_MAX + 1. Nie wpłynie to na pamięć nie zajmowaną przez zmienną.

Zobacz także https://stackoverflow.com/q/18195715/951890

Vaughn Cato
źródło
przepełnienie liczb całkowitych ze znakiem jest tak samo dobrze zdefiniowane, jak przepełnienie liczb całkowitych bez znaku. jeśli słowo ma bity $ N $, górna granica przepełnienia liczby całkowitej ze znakiem wynosi $$ 2 ^ {N-1} -1 $$ (gdzie zawija się do -2 ^ {N-1} $), podczas gdy górna granica przepełnienia liczby całkowitej bez znaku wynosi $$ 2 ^ N - 1 $$ (gdzie obejmuje się do 0 $). te same mechanizmy dodawania i odejmowania, taki sam rozmiar zakresu liczb (2 $ ^ N $), które mogą być reprezentowane. po prostu inna granica przepełnienia.
Robert Bristol-Johnnson
1
@ robertbristow-johnson: Niezgodne ze standardem C.
Vaughn Cato
cóż, standardy czasem są anachroniczne. patrząc na odniesienie do SO, pojawia się jeden komentarz, który trafia bezpośrednio: „Ważna uwaga jest jednak taka, że ​​we współczesnym świecie nie ma żadnych architektur wykorzystujących arytmetykę z dopełnieniem 2. Poza tym standardy językowe nadal pozwalają na wdrożenie na przykład PDP-1 jest czystym historycznym artefaktem. - Andy Ross 12.12.2013 o 20:12 "
Robert Bristol-John
przypuszczam, że nie jest to standard C, ale przypuszczam, że mogłaby istnieć implementacja, w której nie byłaby używana zwykła arytmetyka binarna int. I s'pose mogliby wykorzystać kod Grey lub BCD lub EBCDIC . Nie wiem, dlaczego ktokolwiek miałby projektować sprzęt do arytmetyki z kodem Graya lub EBCDIC, ale z drugiej strony, nie wiem, dlaczego ktokolwiek zrobiłby unsignedz binarnym i podpisywałby intsię czymkolwiek innym niż uzupełnienie 2.
Robert Bristol-Johnnson
14

Istnieją więc dwie rzeczy:

  • poziom języka: jakie są semantyki języka C
  • poziom maszyny: jaka jest semantyka zestawu / procesora, którego używasz

Na poziomie językowym:

W C:

  • przepełnienie i niedopełnienie są zdefiniowane jako arytmetyka modulo dla liczb całkowitych bez znaku , a zatem ich wartość „pętle”
  • przepełnienie i niedopełnienie są niezdefiniowanymi zachowaniami dla podpisanych liczb całkowitych, więc wszystko może się zdarzyć

Dla tych, którzy chcieliby przykładu „cokolwiek”, widziałem:

for (int i = 0; i >= 0; i++) {
    ...
}

zmienić się w:

for (int i = 0; true; i++) {
    ...
}

i tak, jest to uzasadniona transformacja.

Oznacza to, że rzeczywiście istnieje potencjalne ryzyko zastąpienia pamięci przy przepełnieniu z powodu dziwnej transformacji kompilatora.

Uwaga: na Clang lub gcc użyj -fsanitize=undefinedw Debugowaniu, aby aktywować narzędzie do dezynfekcji niezdefiniowanych zachowań, które przerwie działanie przy niedopełnieniu / przepełnieniu podpisanych liczb całkowitych.

Lub oznacza to, że można zastąpić pamięć, używając wyniku operacji do indeksowania (niezaznaczonego) do tablicy. Jest to niestety o wiele bardziej prawdopodobne w przypadku braku wykrywania niedopełnienia / przepełnienia.

Uwaga: na Clang lub gcc użyj -fsanitize=addressw Debugowaniu, aby aktywować narzędzie Sanitizer adresu, które przerwie dostęp poza granicami.


Na poziomie maszyny :

To zależy od instrukcji montażu i używanego procesora:

  • na x86 ADD użyje 2-dopełniacza przy przepełnieniu / niedopełnieniu i ustawi OF (flaga przepełnienia)
  • w przyszłym procesorze Mill będą dostępne 4 różne tryby przepełnienia dla Add:
    • Modulo: moduł 2 uzupełnień
    • Pułapka: pułapka jest generowana, zatrzymując obliczenia
    • Nasycenie: wartość utknie do wartości minimalnej przy przepełnieniu lub maksimum przy przepełnieniu
    • Podwójna szerokość: wynik jest generowany w rejestrze o podwójnej szerokości

Zauważ, że niezależnie od tego, czy coś dzieje się w rejestrach, czy w pamięci, w żadnym przypadku procesor nie zastępuje pamięci po przepełnieniu.

Matthieu M.
źródło
Czy podpisano trzy ostatnie tryby? (Nie ma znaczenia dla pierwszego, ponieważ jest to 2-dopełniacz.)
Deduplicator
1
@Deduplicator: Zgodnie z wprowadzeniem do modelu programowania procesora Mill istnieją różne kody dodawania podpisanego i niepodpisanego; Spodziewam się, że oba kody będą obsługiwały 4 tryby (i będą mogły działać na różnych szerokościach bitów i skalarach / wektorach). Z drugiej strony, na razie jest to sprzęt parowy;)
Matthieu M.
4

Aby udzielić odpowiedzi @ StevenBurnap, dzieje się tak z powodu sposobu działania komputerów na poziomie komputera.

Twoja tablica jest przechowywana w pamięci (np. W pamięci RAM). Gdy wykonywana jest operacja arytmetyczna, wartość z pamięci jest kopiowana do rejestrów wejściowych obwodu, który wykonuje arytmetykę (ALU: Arithmetic Logic Unit ), następnie operacja jest wykonywana na danych w rejestrach wejściowych, co daje wynik w rejestrze wyjściowym. Wynik ten jest następnie kopiowany z powrotem do pamięci pod prawidłowym adresem w pamięci, pozostawiając pozostałe obszary pamięci nietknięte.

Pharap
źródło
4

Po pierwsze (zakładając standard C99), możesz chcieć dołączyć <stdint.h>standardowy nagłówek i użyć niektórych typów tam zdefiniowanych, w szczególności, int32_tktóra jest dokładnie 32-bitową liczbą całkowitą ze uint64_tznakiem lub dokładnie dokładnie 64-bitową liczbą całkowitą bez znaku i tak dalej. Możesz chcieć używać typów takich jak int_fast16_tze względu na wydajność.

Przeczytaj inne odpowiedzi wyjaśniające, że arytmetyka bez znaku nigdy nie rozlewa (ani nie przepełnia) do sąsiednich miejsc pamięci. Uważaj na niezdefiniowane zachowanie przy podpisanym przepełnieniu.

Następnie, jeśli chcesz obliczyć dokładnie ogromne liczby całkowite (np. Chcesz obliczyć silnię 1000 ze wszystkimi 2568 cyframi dziesiętnymi), potrzebujesz bigintów, czyli dowolnych liczb precyzji (lub bignów). Algorytmy efektywnej arytmetyki bigint są bardzo sprytne i zwykle wymagają użycia specjalistycznych instrukcji maszynowych (np. Niektóre dodają słowo z przeniesieniem, jeśli procesor to posiada). Dlatego zdecydowanie zalecam w takim przypadku użycie istniejącej biblioteki bigint, takiej jak GMPlib

Basile Starynkevitch
źródło