Why does Java think that the product of all numbers from 10 to 99 is 0?
The following block of codes gives the output as 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);
}
}
Please can somebody explain why this happens?
Here is what the program does at each step:
1 * 10 = 10
10 * 11 = 110
110 * 12 = 1320
1320 * 13 = 17160
17160 * 14 = 240240
240240 * 15 = 3603600
3603600 * 16 = 57657600
57657600 * 17 = 980179200
980179200 * 18 = 463356416
463356416 * 19 = 213837312
213837312 * 20 = -18221056
-18221056 * 21 = -382642176
-382642176 * 22 = 171806720
171806720 * 23 = -343412736
-343412736 * 24 = 348028928
348028928 * 25 = 110788608
110788608 * 26 = -1414463488
-1414463488 * 27 = 464191488
464191488 * 28 = 112459776
112459776 * 29 = -1033633792
-1033633792 * 30 = -944242688
-944242688 * 31 = 793247744
793247744 * 32 = -385875968
-385875968 * 33 = 150994944
150994944 * 34 = 838860800
838860800 * 35 = -704643072
-704643072 * 36 = 402653184
402653184 * 37 = 2013265920
2013265920 * 38 = -805306368
-805306368 * 39 = -1342177280
-1342177280 * 40 = -2147483648
-2147483648 * 41 = -2147483648
-2147483648 * 42 = 0
0 * 43 = 0
0 * 44 = 0
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
0 * 97 = 0
0 * 98 = 0
Notice that on some steps the multiplication results in a smaller number (980179200 * 18 = 463356416) or incorrect sign (213837312 * 20 = -18221056), indicating that there was an integer overflow. But where does the zero come from? Read on.
Keeping in mind that int data type is a 32-bit signed, two's complement integer, here is an explanation of each step:
Operation Result(1) Binary Representation(2) Result(3)
---------------- ------------ ----------------------------------------------------------------- ------------
1 * 10 10 1010 10
10 * 11 110 1101110 110
110 * 12 1320 10100101000 1320
1320 * 13 17160 100001100001000 17160
17160 * 14 240240 111010101001110000 240240
240240 * 15 3603600 1101101111110010010000 3603600
3603600 * 16 57657600 11011011111100100100000000 57657600
57657600 * 17 980179200 111010011011000101100100000000 980179200
980179200 * 18 17643225600 100 00011011100111100100001000000000 463356416
463356416 * 19 8803771904 10 00001100101111101110011000000000 213837312
213837312 * 20 4276746240 11111110111010011111100000000000 -18221056
-18221056 * 21 -382642176 11111111111111111111111111111111 11101001001100010101100000000000 -382642176
-382642176 * 22 -8418127872 11111111111111111111111111111110 00001010001111011001000000000000 171806720
171806720 * 23 3951554560 11101011100001111111000000000000 -343412736
-343412736 * 24 -8241905664 11111111111111111111111111111110 00010100101111101000000000000000 348028928
348028928 * 25 8700723200 10 00000110100110101000000000000000 110788608
110788608 * 26 2880503808 10101011101100010000000000000000 -1414463488
-1414463488 * 27 -38190514176 11111111111111111111111111110111 00011011101010110000000000000000 464191488
464191488 * 28 12997361664 11 00000110101101000000000000000000 112459776
112459776 * 29 3261333504 11000010011001000000000000000000 -1033633792
-1033633792 * 30 -31009013760 11111111111111111111111111111000 11000111101110000000000000000000 -944242688
-944242688 * 31 -29271523328 11111111111111111111111111111001 00101111010010000000000000000000 793247744
793247744 * 32 25383927808 101 11101001000000000000000000000000 -385875968
-385875968 * 33 -12733906944 11111111111111111111111111111101 00001001000000000000000000000000 150994944
150994944 * 34 5133828096 1 00110010000000000000000000000000 838860800
838860800 * 35 29360128000 110 11010110000000000000000000000000 -704643072
-704643072 * 36 -25367150592 11111111111111111111111111111010 00011000000000000000000000000000 402653184
402653184 * 37 14898167808 11 01111000000000000000000000000000 2013265920
2013265920 * 38 76504104960 10001 11010000000000000000000000000000 -805306368
-805306368 * 39 -31406948352 11111111111111111111111111111000 10110000000000000000000000000000 -1342177280
-1342177280 * 40 -53687091200 11111111111111111111111111110011 10000000000000000000000000000000 -2147483648
-2147483648 * 41 -88046829568 11111111111111111111111111101011 10000000000000000000000000000000 -2147483648
-2147483648 * 42 -90194313216 11111111111111111111111111101011 00000000000000000000000000000000 0
0 * 43 0 0 0
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
0 * 98 0 0 0
- is the correct result
- is the internal representation of the result (64 bits are used for illustration)
- is the result represented by the two's complement of the lower 32 bits
We know that multiplying a number by an even number:
- shifts the bits towards left and adds zero bits towards right
- results in an even number
So basically your program multiplies an even number with another number repeatedly which zeroes out the result bits starting from right.
PS: If the multiplications involved odd numbers only then the result will not become zero.
Computer multiplication is really happening modulo 2^32. Once you have accumulated enough powers of two in the multiplicand, then all values will be 0.
Here we have all the even numbers in the series, along with the maximum power of two that divides the number, and the cumulative power of two
num max2 total
10 2 1
12 4 3
14 2 4
16 16 8
18 2 9
20 4 11
22 2 12
24 8 15
26 2 16
28 4 18
30 2 19
32 32 24
34 2 25
36 4 27
38 2 28
40 8 31
42 2 32
The product up to 42 is equal to x * 2^32 = 0 (mod 2^32). The sequence of the powers of two is related to Gray codes (among other things), and appears as https://oeis.org/A001511.
EDIT: to see why other responses to this question are incomplete, consider the fact that the same program, restricted to odd integers only, would not converge to 0, despite all the overflowing.