Blok kode berikut memberikan output sebagai 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);
}
}Tolong bisakah seseorang menjelaskan mengapa ini terjadi?
java
integer
integer-overflow
Aniruddha Sarkar
sumber
sumber
2muncul sekitar 90 kali. Itu berarti Anda akan memerlukan variabel dengan setidaknya 90 bit untuk mendapatkan output yang tidak nol. 32 dan 64 keduanya kurang dari 90. Untuk menghitung bilangan bulat yang lebih besar dari kata-kata asli, Anda harus menggunakan kelas bilangan bulat besar apa pun yang tersedia dalam bahasa pilihan Anda.Jawaban:
Inilah yang dilakukan program pada setiap langkah:
Perhatikan bahwa pada beberapa langkah, hasil perkalian dalam jumlah yang lebih kecil (980179200 * 18 = 463356416) atau tanda yang salah (213837312 * 20 = -18221056), menunjukkan bahwa ada bilangan bulat bilangan bulat. Tapi dari mana nol berasal? Baca terus.
Perlu diingat bahwa
inttipe data adalah 32-bit yang ditandatangani , integer pelengkap dua , berikut adalah penjelasan dari setiap langkah:Kita tahu bahwa mengalikan angka dengan angka genap:
Jadi pada dasarnya program Anda mengalikan angka genap dengan angka lain berulang kali yang nol bit hasil mulai dari kanan.
PS: Jika penggandaan hanya melibatkan angka ganjil maka hasilnya tidak akan menjadi nol.
sumber
Multiplikasi komputer benar-benar terjadi modulo 2 ^ 32. Setelah Anda mengumpulkan cukup kekuatan dua di multiplicand, maka semua nilai akan menjadi 0.
Di sini kita memiliki semua angka genap dalam seri, bersama dengan kekuatan maksimum dua yang membagi angka, dan kekuatan kumulatif dua
Produk hingga 42 sama dengan x * 2 ^ 32 = 0 (mod 2 ^ 32). Urutan kekuatan dua terkait dengan kode Gray (antara lain), dan muncul sebagai https://oeis.org/A001511 .
EDIT: untuk melihat mengapa tanggapan lain terhadap pertanyaan ini tidak lengkap, pertimbangkan fakta bahwa program yang sama, terbatas hanya pada bilangan bulat ganjil, tidak akan konvergen ke 0, meskipun semua meluap.
sumber
Itu terlihat seperti integer overflow .
Lihatlah ini
Keluaran:
Output tidak lagi menjadi
intnilai. Maka Anda akan mendapatkan nilai yang salah karena melimpah.Info lebih lanjut
Edit .
Mari kita ubah kode Anda sebagai berikut
Keluarkan:
sumber
Itu karena integer overflow. Ketika Anda mengalikan banyak angka genap, angka biner mendapat banyak angka nol. Ketika Anda memiliki lebih dari 32 angka nol di belakangnya, angka
intitu berguling ke0.Untuk membantu Anda memvisualisasikan ini, berikut adalah perkalian dalam hex yang dihitung pada tipe angka yang tidak akan meluap. Lihat bagaimana nol trailing tumbuh perlahan, dan perhatikan bahwa
intterdiri dari 8 digit hex terakhir. Setelah dikalikan dengan 42 (0x2A), semua 32 bitintadalah nol!sumber
Di suatu tempat di tengah Anda dapatkan
0sebagai produk. Jadi, seluruh produk Anda adalah 0.Dalam kasus Anda:
Setiap kali Anda mengalikan nilai saat ini
idengan angka yang Anda dapatkan0sebagai output.sumber
Karena banyak dari titik jawaban yang ada untuk rincian implementasi Java dan hasil debug, mari kita lihat matematika di balik perkalian biner untuk benar-benar menjawab alasannya.
Komentar @kasperd mengarah ke arah yang benar. Misalkan Anda tidak memperbanyak secara langsung dengan angka tetapi dengan faktor prima dari angka itu sebagai gantinya. Dari banyak angka akan memiliki 2 sebagai faktor utama. Dalam biner ini sama dengan shift kiri. Dengan komutatif kita dapat mengalikan dengan faktor prima dari 2 terlebih dahulu. Itu artinya kita hanya melakukan shift kiri.
Ketika melihat aturan perkalian biner, satu-satunya kasus di mana 1 akan menghasilkan posisi digit tertentu adalah ketika kedua nilai operan adalah satu.
Jadi efek dari pergeseran kiri adalah bahwa posisi bit terendah dari 1 ketika lebih jauh mengalikan hasilnya meningkat.
Karena integer hanya berisi bit urutan terendah, mereka semua akan ditetapkan ke 0 ketika faktor prima 2 cukup sering ditandai dalam hasilnya.
Perhatikan bahwa representasi komplemen dua tidak menarik untuk analisis ini, karena tanda hasil multiplikasi dapat dihitung secara independen dari angka yang dihasilkan. Itu berarti jika nilai meluap dan menjadi negatif, bit urutan terendah direpresentasikan sebagai 1, tetapi selama penggandaan mereka diperlakukan lagi sebagai 0.
sumber
Jika saya menjalankan kode ini What I get all -
Penyebab Integer Overflow -
Menghasilkan 0 penyebab -
sumber
Akhirnya, perhitungan meluap, dan akhirnya meluap itu menghasilkan produk nol; itu terjadi ketika
product == -2147483648dani == 42. Coba kode ini untuk memverifikasi sendiri (atau jalankan kode di sini ):Begitu nol, tentu saja tetap nol. Berikut beberapa kode yang akan menghasilkan hasil yang lebih akurat (Anda dapat menjalankan kode di sini ):
sumber
Ini adalah integer overflow.
Tipe data int adalah 4 byte, atau 32 bit. Oleh karena itu, angka yang lebih besar dari 2 ^ (32 - 1) - 1 (2.147.483.647) tidak dapat disimpan dalam tipe data ini. Nilai numerik Anda akan salah.
Untuk jumlah yang sangat besar, Anda ingin mengimpor dan menggunakan kelas
java.math.BigInteger:CATATAN: Untuk nilai numerik yang masih terlalu besar untuk tipe data int, tetapi cukup kecil untuk muat dalam 8 byte (nilai absolut kurang dari atau sama dengan 2 ^ (64 - 1) - 1), Anda mungkin harus menggunakan
longprimitif.Masalah praktik HackerRank (www.hackerrank.com), seperti bagian praktik Algoritma, ( https://www.hackerrank.com/domains/algorithms/warmup ) mencakup beberapa pertanyaan besar yang sangat bagus yang memberikan praktik bagus tentang cara pikirkan tipe data yang tepat untuk digunakan.
sumber