C++ Overflow

pytanie zadane 12 czerwca 2018 w C i C++ przez qlucha Obywatel (1,790 p.)
edycja 13 czerwca 2018 przez qlucha

Witam, prosiłbym kogoś doświadczonego w programowaniu aby potwierdził lub naprowadził mnie na dobrą drogę otóż:

Własnie analizuję kod mergeSort ze strony:

https://www.geeksforgeeks.org/merge-sort/

I zastanawiam się nad informacją którą tam znalazłem:

void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l+(r-l)/2;
 
        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
 
        merge(arr, l, m, r);
    }
}

Chodzi mi dokładnie o komentarz // Same as (l+r)/2, but avoids overflow for large l and h

Czy overflow oznacza przypadek w którym użyjemy funkcji do posortowania bardzo dużych tablic i ich indeksy będą mieć bardzo duże wielkości których nie pomieści nam typ danych int dla liczb całkowitych który może przechować dodatnie i ujemne liczby całkowite o wartości około 2 miliardów (znam wzór ale aby było szybciej nie będe o nim pisał i nie jest to istotą mojego pytania ) i w pewnym przypadku po dodaniu 2 zmiennych int przechowujących wartości których suma przekroczy tak zwaną pojemność maksymalną int'a ???

(A ta metoda zabezpiecza nas przed tym problemem powyżej)

Czy to nazywamy w programowaniu sytuację jako overflow ??? :

    int a = 2000000000;
    int b = 2000000000;
    int c = INT_MAX;
    std::cout << a << std::endl;
    std::cout << b << std::endl;
    std::cout << a+b << std::endl;
    std::cout << c << std::endl;

komentarz 12 czerwca 2018 przez Wunsz Użytkownik (680 p.)

Doświadczonym programistą nie jestem ale wydaje mi się ,że masz racje. Jest jeszcze błąd stack overflow kiedy przepełnimy stos przy rekurencji

komentarz 12 czerwca 2018 przez qlucha Obywatel (1,790 p.)
edycja 13 czerwca 2018 przez qlucha

Ok, dzieki za odpowiedz (Wiem ,że prawdopodobnie to jest proste pytanie ale wole sobię to utrwalić i zakodować raz na zawsze i może dowiem się jeszcze ciekawego czegoś)

komentarz 13 czerwca 2018 przez qlucha Obywatel (1,790 p.)

@Wunsz, Ale prawdopodobnie pewnie pewnego pięknego dnia nim zostaniesz. Powodzenia.

1 odpowiedź

odpowiedź 13 czerwca 2018 przez criss Mędrzec (172,590 p.)
wybrane 13 czerwca 2018 przez qlucha

Najlepsza

Na x86 dodawanie/odejmowanie typów unsigned i signed jest realizowane tą samą instrukcją. Dlatego, że to działa - liczby zapisane w U2 możesz dodać do siebie w ten sam sposób jak liczby zapisane w zwykłym kodzie binarnym i wynik będzie poprawny. Dodatkowo liczby nieujemne w U2 mają identyczną reprezentacje binarną jak w zwykłym kodzie binarnym. Więc jeśli dodasz do siebie 2mld + 2mld, to otrzymasz reprezentacje binarną 4mld, ale w zwykłym kodzie binarnym. Jako, ze wynik jest typu signed int, to std::cout zinterpretuje bity jako kod U2 i wypisze jakąś liczbe ujemną która ma taką właśnie reprezentacje binarną w kodzie U2. Wynik jednak jest poprawny, ale nie w tym kodowaniu. Jakbyś zmusił cout do interpretacji tych 4 bajtów jako typ unsigned, to zobaczyłbyś poprawny wynik 4mld. Możesz to zrobić w taki sposób:

int a = 2000000000;
int b = 2000000000;
int c = a + b;
std::cout << *((unsigned*)&c);

Jeśli ktoś by chciał się przyczepić, że to UB - tak, wiem, ale zakładając x86 (i prawdopodobnie jakąkolwiek popularną współczesną architekture), to wszystko jest ok.

Możesz się zapoznać z flagami procesora CF i OF. CF (carry) zapala się gdy w wyniku instrukcji nastąpiło wyjście poza zakres interpretując bity jako liczbę unsigned, a OF (overflow) analogicznie dla signed. W powyższym przypadku zapali się OF, ale CF już nie.

komentarz 13 czerwca 2018 przez qlucha Obywatel (1,790 p.)

Ok, dzięki za odpowiedz, wiedziałem ,że dowiem się jeszcze czegoś ciekawego.

Ale będę musiał to jeszcze przeanalizować.

komentarz 13 czerwca 2018 przez criss Mędrzec (172,590 p.)

Nie wiem czy odpowiedziałem stricte na twoje pytanie :P Ale mam nadzieję, że teraz wszystko będzie jasne. Jakby co, to pytaj

komentarz 13 czerwca 2018 przez qlucha Obywatel (1,790 p.)

Jestem w pełni zadowolony z odpowiedzi. Już wiem na 100% co oznacza w tym kodzie powyżej zagrożenie jakie może spowodować tak zwany overflow, i jak jest to zabezpieczone na jakiej zasadzie to działa . Mam kod quickSort'a w którym ten problem nie jest zabezpieczony i teraz dopiero to zobaczyłem, ale raczej rzadko ma się do czynienia z tak dużymi tablicami do sortowania raczej ... . Ale dobrze o tym wiedzieć.

komentarz 13 czerwca 2018 przez criss Mędrzec (172,590 p.)

Zabezpieczenie raczej bez sensu, bo taka tablica musiałaby zajmować conajmniej kilka GB pamięci na co ten kod raczej nigdy nie trafi :D A nawet jeśli funkcja była projektowana z myślą o jakichś olbrzymich rozmiarach, to używa się wtedy 64bitowych typów zamiast stosować jakieś dziwne sztuczki. No i nie ma sensu do reprezentacji indeksów używać signed inta..