Poniższy blok kodów daje wynik jako 0.
public class HelloWorld{
public static void main(String []args){
int product = 1;
for (int i = 10; i <= 99; i++) {
product *= i;
}
System.out.println(product);
}
}Czy ktoś może wyjaśnić, dlaczego tak się dzieje?
java
integer
integer-overflow
Aniruddha Sarkar
źródło
źródło
2pojawi się około 90 razy. Oznacza to, że będziesz potrzebować zmiennej z co najmniej 90 bitami, aby uzyskać niezerowe dane wyjściowe. 32 i 64 to mniej niż 90. Aby obliczyć liczby całkowite większe niż słowa rodzime, musisz użyć dowolnej klasy dużych liczb całkowitych dostępnej w wybranym języku.Odpowiedzi:
Oto, co program robi na każdym kroku:
Zwróć uwagę, że w niektórych krokach mnożenie daje mniejszą liczbę (980179200 * 18 = 463356416) lub nieprawidłowy znak (213837312 * 20 = -18221056), co wskazuje, że wystąpiło przepełnienie liczby całkowitej. Ale skąd pochodzi zero? Czytaj.
Pamiętając, że
inttyp danych jest 32-bitowa , uzupełnienie dwójkowe całkowitą, tutaj jest wyjaśnienie każdego etapu:Wiemy, że pomnożenie liczby przez liczbę parzystą:
Zasadniczo twój program wielokrotnie mnoży liczbę parzystą przez inną, co zeruje bity wyniku, zaczynając od prawej.
PS: Jeśli mnożenia obejmowały tylko liczby nieparzyste, wynik nie będzie zerowy.
źródło
Mnożenie komputera naprawdę się dzieje modulo 2 ^ 32. Kiedy zgromadzisz wystarczającą liczbę potęg dwóch w mnożniku, wszystkie wartości będą równe 0.
Tutaj mamy wszystkie liczby parzyste w serii, wraz z maksymalną potęgą dwóch, która dzieli liczbę, i łączną potęgą dwóch
Iloczyn do 42 równa się x * 2 ^ 32 = 0 (mod 2 ^ 32). Sekwencja potęg dwóch jest związana między innymi z kodami Graya i pojawia się jako https://oeis.org/A001511 .
EDYCJA: aby zobaczyć, dlaczego inne odpowiedzi na to pytanie są niekompletne, weź pod uwagę fakt, że ten sam program, ograniczony tylko do nieparzystych liczb całkowitych, nie zbiegałby się do 0, pomimo całego przepełnienia.
źródło
Wygląda na przepełnienie liczby całkowitej .
Spójrz na to
Wynik:
Wynik nie jest już
intwartością. Wtedy otrzymasz błędną wartość z powodu przepełnienia.Więcej informacji
Edytuj .
Zmieńmy Twój kod w następujący sposób
Wynik:
źródło
To z powodu przepełnienia liczb całkowitych. Kiedy pomnożymy razem wiele liczb parzystych, liczba binarna otrzyma wiele końcowych zer. Jeśli masz więcej niż 32 zera końcowe dla an
int, przechodzi on do0.Aby pomóc ci to zwizualizować, oto mnożenia szesnastkowe obliczone dla typu liczby, która nie przepełni się. Zobacz, jak końcowe zera powoli rosną i zwróć uwagę, że an
intskłada się z ostatnich 8 cyfr szesnastkowych. Po pomnożeniu przez 42 (0x2A) wszystkie 32 bityintsą zerami!źródło
Gdzieś pośrodku otrzymujesz
0produkt. Zatem cały Twój produkt będzie wynosił 0.W Twoim przypadku :
Za każdym razem, gdy pomnożymy bieżącą wartość
iprzez liczbę otrzymaną0jako wynik.źródło
Ponieważ wiele z istniejących odpowiedzi wskazuje na szczegóły implementacji języka Java i wyniki debugowania, przyjrzyjmy się matematyce stojącej za mnożeniem binarnym, aby naprawdę odpowiedzieć na pytanie, dlaczego.
Komentarz @kasperd idzie w dobrym kierunku. Załóżmy, że nie mnożysz bezpośrednio przez liczbę, ale zamiast tego przez czynniki pierwsze tej liczby. Niż wiele liczb będzie miało 2 jako czynnik pierwszy. W systemie binarnym jest to przesunięcie w lewo. Przez przemienność możemy najpierw pomnożyć przez czynniki pierwsze 2. Oznacza to, że po prostu wykonujemy przesunięcie w lewo.
Patrząc na binarne reguły mnożenia, jedynym przypadkiem, w którym 1 da w wyniku określoną pozycję cyfry, jest sytuacja, w której obie wartości operandów są równe jeden.
Zatem efekt przesunięcia w lewo jest taki, że najniższe położenie bitu 1 przy dalszym mnożeniu wyniku jest zwiększane.
Ponieważ liczba całkowita zawiera tylko bity najniższego rzędu, wszystkie zostaną ustawione na 0, gdy w wyniku dostatecznie często występuje czynnik pierwszy 2.
Zauważ, że reprezentacja dopełnienia do dwóch nie jest interesująca dla tej analizy, ponieważ znak wyniku mnożenia można obliczyć niezależnie od wynikowej liczby. Oznacza to, że jeśli wartość przepełni się i stanie się ujemna, bity najniższego rzędu są reprezentowane jako 1, ale podczas mnożenia są ponownie traktowane jako 0.
źródło
Jeśli uruchomię ten kod Co otrzymam wszystko -
Przyczyna przepełnienia liczby całkowitej -
Wyprodukuj 0 przyczyn -
źródło
Ostatecznie obliczenia przepełniają się i ostatecznie to przepełnienie prowadzi do iloczynu zerowego; to się dzieje, gdy
product == -2147483648ii == 42. Wypróbuj ten kod, aby zweryfikować go samodzielnie (lub uruchom kod tutaj ):Gdy jest zero, oczywiście pozostaje zero. Oto kod, który da dokładniejszy wynik (możesz uruchomić kod tutaj ):
źródło
Jest to przepełnienie całkowitoliczbowe.
Typ danych int to 4 bajty lub 32 bity. Dlatego liczby większe niż 2 ^ (32 - 1) - 1 (2 147 483 647) nie mogą być przechowywane w tym typie danych. Twoje wartości liczbowe będą nieprawidłowe.
W przypadku bardzo dużych liczb będziesz chciał zaimportować klasę i używać jej
java.math.BigInteger:UWAGA: W przypadku wartości liczbowych, które są nadal zbyt duże dla typu danych int, ale wystarczająco małe, aby zmieścić się w 8 bajtach (wartość bezwzględna mniejsza lub równa 2 ^ (64 - 1) - 1), prawdopodobnie powinieneś użyć
longprymitywu.Praktyczne problemy HackerRank (www.hackerrank.com), takie jak sekcja ćwiczeń algorytmów, ( https://www.hackerrank.com/domains/algorithms/warmup ) obejmują kilka bardzo dobrych, dużych pytań, które dają dobre praktyki dotyczące tego, jak pomyśl o odpowiednim typie danych do użycia.
źródło