Natrafiłem na poniższy program w C ++ ( źródło ):
#include <iostream>
int main()
{
for (int i = 0; i < 300; i++)
std::cout << i << " " << i * 12345678 << std::endl;
}
Wygląda jak prosty program i podaje prawidłowe dane wyjściowe na mojej lokalnej maszynie, np. Coś takiego:
0 0
1 12345678
2 24691356
...
297 -628300930
298 -615955252
299 -603609574
Ale w internetowych środowiskach IDE, takich jak codechef , daje następujący wynik:
0 0
1 12345678
2 24691356
...
4167 -95167326
4168 -82821648
4169 -7047597
Dlaczego for
pętla nie kończy się przy 300? Również ten program zawsze kończy się 4169
. Dlaczego 4169
a nie inna wartość?
c++
undefined-behavior
integer-overflow
arpanmangal
źródło
źródło
Odpowiedzi:
Zakładam, że kompilatory online używają GCC lub kompatybilnego kompilatora. Oczywiście każdy inny kompilator może również przeprowadzić taką samą optymalizację, ale dokumentacja GCC dobrze wyjaśnia, co robi:
Ta opcja pozwala jedynie na przyjmowanie założeń na podstawie przypadków, w których udowodniono UB. Aby skorzystać z tych założeń, może być konieczne włączenie innych optymalizacji, takich jak ciągłe zwijanie.
Przepełnienie liczby całkowitej ze znakiem ma niezdefiniowane zachowanie. Optymalizator był w stanie udowodnić, że jakakolwiek wartość
i
większa niż 173 spowodowałaby UB, a ponieważ może założyć, że nie ma UB, może również założyć, żei
nigdy nie jest większa niż 173. Następnie może dalej udowodnić, żei < 300
jest to zawsze prawda, i więc stan pętli można zoptymalizować.Witryny te prawdopodobnie ograniczają liczbę wyświetlanych wierszy wyjściowych (lub znaków lub bajtów) i mają ten sam limit.
źródło
i
większej niż 173, to dlaczego nie emituje ostrzeżenia zamiast bezcelowej optymalizacji?„Niezdefiniowane zachowanie jest nieokreślone”. (do)
Kompilator używany na codechef wydaje się używać następującej logiki:
i * 12345678
przepełnia i powoduje UB ifi > 173
(zakładając 32 bityint
).i
nigdy nie może przekroczyć173
.i < 300
jest zbędny i można go zastąpićtrue
.Sama pętla wydaje się być nieskończona. Wygląda na to, że codechef po prostu zatrzymuje program po określonym czasie lub obcina dane wyjściowe.
źródło
2^16
. Najwyraźniej to zbieg okoliczności, że obcinają dane wyjściowe do2^16
znaków.Wywołujesz niezdefiniowane zachowanie prawdopodobnie w 174. iteracji wewnątrz twojej
for
pętli, ponieważint
prawdopodobnie maksymalna wartość jest2147483647
jeszcze174 * 123456789
obliczana,2148147972
co jest niezdefiniowanym zachowaniem, ponieważ nie ma przepełnienia liczb całkowitych ze znakiem. Więc obserwujesz efekty UB, szczególnie z kompilatorem GCC z ustawionymi flagami optymalizacji. Prawdopodobnie kompilator ostrzegłby Cię o tym, wydając następujące ostrzeżenie:warning: iteration 174 invokes undefined behavior [-Waggressive-loop-optimizations]
Usuń
-O2
flagi optymalizacji ( ), aby obserwować różne wyniki.źródło
Kompilator może założyć, że niezdefiniowane zachowanie nie wystąpi, a ponieważ przepełnienie podpisane to UB, może założyć, że nigdy
i * 12345678 > INT_MAX
, a zatem również,i <= INT_MAX / 12345678 < 300
a tym samym usunąć sprawdzeniei < 300
.źródło