int sau long long? Cum eviți overflow în C++
Alege tipul după valorile intermediare, nu doar după intrare. Vezi de ce atribuirea în long long nu repară o înmulțire făcută deja pe int.
În acest material
Un program poate compila și totuși să calculeze greșit deoarece o valoare intermediară nu încape în tipul folosit. Problema nu se rezolvă întotdeauna schimbând doar tipul variabilei în care salvezi rezultatul.
Pornește de la limita matematică
Dacă aduni 100000 de valori, fiecare de cel mult 10^9, suma poate ajunge la 10^14. Nu contează că fiecare element încape într-un int uzual pe 32 de biți; suma cere un domeniu mai mare. Pentru produsul a două numere de până la 10^9, limita este 10^18, care încape într-un long long cu cel puțin 64 de biți.
C++ nu impune ca int să aibă exact 32 de biți. Verifică mediul și, când este relevant, limitele prin numeric_limits. long long are cel puțin 64 de biți. Nici el nu poate reprezenta orice produs sau orice factorial.
Produsul 50000 ori 50000 este 2500000000. Folosirea lui 1LL înaintea înmulțirii mută calculul în long long.Mărește schema ↗
Conversia trebuie să aibă loc înaintea operației
În expresia long long p = a * b, dacă a și b sunt int, înmulțirea este evaluată în tipul operanzilor înaintea atribuirii. Destinația mai largă nu repară un rezultat intermediar nereprezentabil. Poți folosi 1LL * a * b sau o conversie explicită a unui operand la long long.
Același principiu se aplică formulei n*(n+1)/2. Împărțirea finală nu garantează că produsul anterior încape. Pentru n=100000, rezultatul matematic este 5000050000, iar produsul intermediar este 10000100000. La limite și mai mari trebuie verificat și n+1, nu doar înmulțirea.
Overflow cu semn nu înseamnă „se întoarce la început”
Pentru întregii cu semn, un rezultat nereprezentabil are comportament nedefinit. Nu construi teste care presupun o anumită valoare negativă după depășire. Compilatorul poate optimiza folosind presupunerea că un asemenea caz nu apare.
Întregii fără semn au aritmetică modulară, dar schimbarea la unsigned nu rezolvă automat problema. Dacă un indice zero este decrementat, poate deveni un număr foarte mare, ceea ce este periculos într-o parcurgere inversă.
O verificare practică în patru pași
Scrie limitele intrărilor. Calculează limita fiecărei expresii intermediare. Alege tipurile înainte de implementare. Testează apoi valori apropiate de acele limite. Pentru suma unui vector, include și un caz cu toate elementele maxime; câteva valori mici nu pot descoperi overflow-ul.
Separă eroarea de domeniu de împărțirea între întregi. Expresia 5/2 produce 2 pentru operanzi întregi, chiar dacă atribui apoi rezultatul unui double. Dacă vrei 2,5, unul dintre operanzi trebuie să fie real înaintea împărțirii. Nu toate rezultatele numerice greșite provin din depășire.
Recapitulează tipurile de date, evaluarea expresiilor și acumularea sumelor. Regula generală despre rezultatele nereprezentabile este precizată în specificația expresiilor C++.
Întrebări frecvente
De ce poate apărea overflow dacă rezultatul este long long?
Expresia din dreapta este calculată înainte de atribuire. Dacă ambii factori sunt int, produsul lor poate depăși acel tip înainte să ajungă în variabila long long. Convertește un operand înaintea înmulțirii.
Ce face 1LL într-o înmulțire în C++?
Literalul 1LL are tipul long long. În expresia 1LL * a * b, el face ca înmulțirile să folosească acest tip, dar nu protejează împotriva depășirii limitei lui long long.
Overflow-ul întregilor cu semn produce mereu un număr negativ?
Nu. Depășirea domeniului unui întreg cu semn are comportament nedefinit în C++. Calculează limitele expresiilor înainte de execuție și nu te baza pe o presupusă revenire la începutul intervalului.