poner - titledborder java
¿Por qué Java piensa que el producto de todos los números del 10 al 99 es 0? (9)
El siguiente bloque de códigos da el resultado como 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);
}
}
Por favor, ¿alguien puede explicar por qué sucede esto?
Dado que muchas de las respuestas existentes apuntan a detalles de implementación de Java y salida de depuración, echemos un vistazo a las matemáticas detrás de la multiplicación binaria para realmente responder al por qué.
El comentario de @kasperd va en la dirección correcta. Supongamos que no se multiplica directamente con el número sino con los factores primos de ese número. Que muchos números tendrán 2 como factor principal. En binario esto es igual a un cambio a la izquierda. Por conmutatividad podemos multiplicar primero con factores primos de 2. Eso significa que simplemente hacemos un cambio a la izquierda.
Al observar las reglas de multiplicación binarias, el único caso en el que un 1 dará como resultado una posición de dígito específico es cuando ambos valores de operando son uno.
Entonces, el efecto de un cambio a la izquierda es que la posición más baja de un 1 cuando se multiplica aún más el resultado aumenta.
Dado que el entero contiene solo los bits de orden más bajo, todos se establecerán en 0 cuando el factor primo 2 se agrupe con la suficiente frecuencia en el resultado.
Tenga en cuenta que la representación del complemento de dos no es de interés para este análisis, ya que el signo del resultado de la multiplicación puede calcularse independientemente del número resultante. Eso significa que si el valor se desborda y se vuelve negativo, los bits de orden más bajo se representan como 1, pero durante la multiplicación se tratan de nuevo como 0.
En algún lugar en el medio obtienes 0 como producto. Entonces, todo tu producto será 0.
En tu caso :
for (int i = 10; i < 99; i++) {
if (product < Integer.MAX_VALUE)
System.out.println(product);
product *= i;
}
// System.out.println(product);
System.out.println(-2147483648 * EvenValueOfi); // --> this is the culprit (Credits : Kocko''s answer )
O/P :
1
10
110
1320
17160
240240
3603600
57657600
980179200
463356416
213837312
-18221056
-382642176
171806720
-343412736
348028928
110788608
-1414463488
464191488
112459776
-1033633792
-944242688
793247744
-385875968
150994944
838860800
-704643072
402653184
2013265920
-805306368
-1342177280 --> Multiplying this and the current value of `i` will also give -2147483648 (INT overflow)
-2147483648 --> Multiplying this and the current value of `i` will also give -2147483648 (INT overflow)
-2147483648 -> Multiplying this and the current value of ''i'' will give 0 (INT overflow)
0
0
0
Cada vez que multiplicas el valor actual de i con el número obtienes 0 como salida.
Es debido al desbordamiento de enteros. Cuando multiplicas muchos números pares, el número binario obtiene muchos ceros finales. Cuando tiene más de 32 ceros finales para un int , se desplaza a 0 .
Para ayudarlo a visualizar esto, aquí están las multiplicaciones en hexadecimal calculadas en un tipo de número que no se desbordará. Vea cómo los ceros finales crecen lentamente, y tenga en cuenta que un int se compone de los últimos 8 dígitos hexadecimales. ¡Después de multiplicar por 42 (0x2A), los 32 bits de un int son ceros!
1 (int: 00000001) * 0A =
A (int: 0000000A) * 0B =
6E (int: 0000006E) * 0C =
528 (int: 00000528) * 0D =
4308 (int: 00004308) * 0E =
3AA70 (int: 0003AA70) * 0F =
36FC90 (int: 0036FC90) * 10 =
36FC900 (int: 036FC900) * 11 =
3A6C5900 (int: 3A6C5900) * 12 =
41B9E4200 (int: 1B9E4200) * 13 =
4E0CBEE600 (int: 0CBEE600) * 14 =
618FEE9F800 (int: FEE9F800) * 15 =
800CE9315800 (int: E9315800) * 16 =
B011C0A3D9000 (int: 0A3D9000) * 17 =
FD1984EB87F000 (int: EB87F000) * 18 =
17BA647614BE8000 (int: 14BE8000) * 19 =
25133CF88069A8000 (int: 069A8000) * 1A =
3C3F4313D0ABB10000 (int: ABB10000) * 1B =
65AAC1317021BAB0000 (int: 1BAB0000) * 1C =
B1EAD216843B06B40000 (int: 06B40000) * 1D =
142799CC8CFAAFC2640000 (int: C2640000) * 1E =
25CA405F8856098C7B80000 (int: C7B80000) * 1F =
4937DCB91826B2802F480000 (int: 2F480000) * 20 =
926FB972304D65005E9000000 (int: E9000000) * 21 =
12E066E7B839FA050C309000000 (int: 09000000) * 22 =
281CDAAC677B334AB9E732000000 (int: 32000000) * 23 =
57BF1E59225D803376A9BD6000000 (int: D6000000) * 24 =
C56E04488D526073CAFDEA18000000 (int: 18000000) * 25 =
1C88E69E7C6CE7F0BC56B2D578000000 (int: 78000000) * 26 =
43C523B86782A6DBBF4DE8BAFD0000000 (int: D0000000) * 27 =
A53087117C4E76B7A24DE747C8B0000000 (int: B0000000) * 28 =
19CF951ABB6C428CB15C2C23375B80000000 (int: 80000000) * 29 =
4223EE1480456A88867C311A3DDA780000000 (int: 80000000) * 2A =
AD9E50F5D0B637A6610600E4E25D7B00000000 (int: 00000000)
Es un desbordamiento de enteros.
El tipo de datos int es 4 bytes o 32 bits. Por lo tanto, los números más grandes que 2 ^ (32 - 1) - 1 (2,147,483,647) no se pueden almacenar en este tipo de datos. Tus valores numéricos serán incorrectos.
Para números muy grandes, querrás importar y usar la clase java.math.BigInteger:
BigInteger product = BigInteger.ONE;
for (long i = 10; i < 99; i++)
product = product.multiply(BigInteger.valueOf(i));
System.out.println(product.toString());
NOTA: Para valores numéricos que todavía son demasiado grandes para el tipo de datos int, pero lo suficientemente pequeños como para caber dentro de 8 bytes (valor absoluto menor o igual que 2 ^ (64 - 1) - 1), probablemente debería usar el primitivo long .
Los problemas de práctica de HackerRank (www.hackerrank.com), como la sección de práctica de Algoritmos ( https://www.hackerrank.com/domains/algorithms/warmup ) incluyen algunas preguntas muy buenas sobre números grandes que ofrecen buenas prácticas sobre cómo piense en el tipo de datos apropiado para usar.
Esto es lo que hace el programa en cada paso:
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
Observe que en algunos pasos la multiplicación resulta en un número menor (980179200 * 18 = 463356416) o en un signo incorrecto (213837312 * 20 = -18221056), lo que indica que hubo un desbordamiento de enteros. Pero, ¿de dónde viene el cero? Sigue leyendo.
Teniendo en cuenta que el tipo de datos int es un entero de complemento de dos con signo de 32 bits , aquí hay una explicación de cada paso:
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
- es el resultado correcto
- es la representación interna del resultado (64 bits se usan para ilustración)
- es el resultado representado por el complemento de los dos de los 32 bits más bajos
Sabemos que multiplicar un número por un número par:
- desplaza los bits hacia la izquierda y agrega cero bits hacia la derecha
- resultados en un número par
Así que, básicamente, su programa multiplica un número par con otro número repetidamente, lo que pone a cero los bits de resultado comenzando desde la derecha.
PD: Si las multiplicaciones involucran números impares solamente, entonces el resultado no será cero.
Eventualmente, el cálculo se desborda, y eventualmente ese desbordamiento conduce a un producto de cero; eso sucede cuando el product == -2147483648 y i == 42 . Pruebe este código para verificarlo usted mismo (o ejecute el código here ):
import java.math.BigInteger;
class Ideone {
public static void main (String[] args) throws java.lang.Exception {
System.out.println("Result: " + (-2147483648 * 42));
}
}
Una vez que es cero, por supuesto permanece cero. Aquí hay un código que producirá un resultado más preciso (puede ejecutar el código here ):
import java.math.BigInteger;
class Ideone {
public static void main (String[] args) throws java.lang.Exception {
BigInteger p = BigInteger.valueOf(1);
BigInteger start = BigInteger.valueOf(10);
BigInteger end = BigInteger.valueOf(99);
for(BigInteger i = start; i.compareTo(end) < 0; i = i.add(BigInteger.ONE)){
p = p.multiply(i);
System.out.println("p: " + p);
}
System.out.println("/nProduct: " + p);
}
}
La multiplicación de la computadora realmente está pasando modulo 2 ^ 32. Una vez que haya acumulado suficientes poderes de dos en el multiplicando, todos los valores serán 0.
Aquí tenemos todos los números pares de la serie, junto con la potencia máxima de dos que divide el número y el poder acumulado de dos.
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
El producto hasta 42 es igual a x * 2 ^ 32 = 0 (mod 2 ^ 32). La secuencia de los poderes de dos está relacionada con los códigos Gray (entre otras cosas) y aparece como https://oeis.org/A001511 .
EDITAR: para ver por qué otras respuestas a esta pregunta son incompletas, considere el hecho de que el mismo programa, restringido solo a enteros impares, no convergería a 0, a pesar de todo el desbordamiento.
Parece un desbordamiento de enteros .
Mira esto
BigDecimal product=new BigDecimal(1);
for(int i=10;i<99;i++){
product=product.multiply(new BigDecimal(i));
}
System.out.println(product);
Salida:
25977982938941930515945176761070443325092850981258133993315252362474391176210383043658995147728530422794328291965962468114563072000000000000000000000
La salida ya no es un valor int . Entonces obtendrás un valor incorrecto debido al desbordamiento.
Si se desborda, vuelve al valor mínimo y continúa desde allí. Si se desborda, vuelve al valor máximo y continúa desde allí.
Más info
Editar .
Cambiemos su código de la siguiente manera
int product = 1;
for (int i = 10; i < 99; i++) {
product *= i;
System.out.println(product);
}
Fuera puesto:
10
110
1320
17160
240240
3603600
57657600
980179200
463356416
213837312
-18221056
-382642176
171806720
-343412736
348028928
110788608
-1414463488
464191488
112459776
-1033633792
-944242688
793247744
-385875968
150994944
838860800
-704643072
402653184
2013265920
-805306368
-1342177280
-2147483648
-2147483648>>>binary representation is 11111111111111111111111111101011 10000000000000000000000000000000
0 >>> here binary representation will become 11111111111111111111111111101011 00000000000000000000000000000000
----
0
Si ejecuto este código Lo que obtengo todo -
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 <- Integer Overflow (17643225600)
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 <- produce 0
0 * 43 = 0
Causa de desbordamiento entero -
980179200 * 18 = 463356416 (should be 17643225600)
17643225600 : 10000011011100111100100001000000000 <-Actual
MAX_Integer : 1111111111111111111111111111111
463356416 : 0011011100111100100001000000000 <- 32 bit Integer
Producir 0 causa -
-2147483648 * 42 = 0 (should be -90194313216)
-90194313216: 1010100000000000000000000000000000000 <- Actual
MAX_Integer : 1111111111111111111111111111111
0 : 00000000000000000000000000000000 <- 32 bit Integer