¿Cómo maneja Java los desbordamientos y los desbordamientos de enteros y cómo lo comprobaría?
¿Cómo maneja Java los desbordamientos y los desbordamientos de enteros?
A partir de eso, ¿cómo comprobarías/probarías que esto esté ocurriendo?
Si se desborda, vuelve al valor mínimo y continúa desde allí. Si se desborda por debajo, vuelve al valor máximo y continúa desde allí.
Puede utilizar los métodos Math#addExact()y Math#subtractExact()que generarán un ArithmeticExceptiondesbordamiento.
public static boolean willAdditionOverflow(int left, int right) {
try {
Math.addExact(left, right);
return false;
} catch (ArithmeticException e) {
return true;
}
}
public static boolean willSubtractionOverflow(int left, int right) {
try {
Math.subtractExact(left, right);
return false;
} catch (ArithmeticException e) {
return true;
}
}
Puede sustituir intpor longpara realizar las mismas comprobaciones para long.
El código fuente se puede encontrar aquí y aquí respectivamente.
Por supuesto, también puedes usarlos de inmediato en lugar de ocultarlos en un booleanmétodo de utilidad.
Si cree que esto puede ocurrir con más frecuencia, considere usar un tipo de datos u objeto que pueda almacenar valores más grandes, por ejemplo, longo tal vez java.math.BigInteger. Este último no se desborda, prácticamente, la memoria JVM disponible es el límite.
Bueno, en lo que respecta a los tipos enteros primitivos, Java no maneja Over/Underflow en absoluto (para float y double el comportamiento es diferente, se vaciará hasta +/- infinito tal como lo exige IEEE-754).
Al agregar dos int, no obtendrá ninguna indicación cuando se produzca un desbordamiento. Un método simple para verificar el desbordamiento es usar el siguiente tipo más grande para realizar la operación y verificar si el resultado todavía está dentro del rango para el tipo de fuente:
public int addWithOverflowCheck(int a, int b) {
// the cast of a is required, to make the + work with long precision,
// if we just added (a + b) the addition would use int precision and
// the result would be cast to long afterwards!
long result = ((long) a) + b;
if (result > Integer.MAX_VALUE) {
throw new RuntimeException("Overflow occured");
} else if (result < Integer.MIN_VALUE) {
throw new RuntimeException("Underflow occured");
}
// at this point we can safely cast back to int, we checked before
// that the value will be withing int's limits
return (int) result;
}
Lo que haría en lugar de las cláusulas de lanzamiento depende de los requisitos de su aplicación (lanzar, vaciar al mínimo/máximo o simplemente registrar lo que sea). Si desea detectar desbordamiento en operaciones largas y no tiene suerte con las primitivas, utilice BigInteger en su lugar.
Editar (21 de mayo de 2014): dado que parece que se hace referencia a esta pregunta con bastante frecuencia y tuve que resolver el mismo problema yo mismo, es bastante fácil evaluar la condición de desbordamiento mediante el mismo método que una CPU calcularía su indicador V.
Es básicamente una expresión booleana que involucra el signo de ambos operandos así como el resultado:
/**
* Add two int's with overflow detection (r = s + d)
*/
public static int add(final int s, final int d) throws ArithmeticException {
int r = s + d;
if (((s & d & ~r) | (~s & ~d & r)) < 0)
throw new ArithmeticException("int overflow add(" + s + ", " + d + ")");
return r;
}
En Java, es más sencillo aplicar la expresión (en el if) a los 32 bits completos y verificar el resultado usando <0 (esto probará efectivamente el bit de signo). El principio funciona exactamente igual para todos los tipos primitivos de enteros ; cambiar todas las declaraciones en el método anterior a long hace que funcione por mucho tiempo.
Para tipos más pequeños, debido a la conversión implícita a int (consulte JLS para obtener más detalles sobre operaciones bit a bit), en lugar de verificar < 0, la verificación debe enmascarar el bit de signo explícitamente (0x8000 para operandos cortos, 0x80 para operandos de bytes, ajustar conversiones y declaración de parámetros apropiadamente):
/**
* Subtract two short's with overflow detection (r = d - s)
*/
public static short sub(final short d, final short s) throws ArithmeticException {
int r = d - s;
if ((((~s & d & ~r) | (s & ~d & r)) & 0x8000) != 0)
throw new ArithmeticException("short overflow sub(" + s + ", " + d + ")");
return (short) r;
}
(Tenga en cuenta que el ejemplo anterior utiliza la expresión necesidad de restar la detección de desbordamiento)
Entonces, ¿cómo/por qué funcionan estas expresiones booleanas? En primer lugar, algo de pensamiento lógico revela que sólo puede ocurrir un desbordamiento si los signos de ambos argumentos son los mismos. Porque, si un argumento es negativo y otro positivo, el resultado (de la suma) debe ser más cercano a cero, o en el caso extremo un argumento es cero, igual que el otro argumento. Dado que los argumentos por sí solos no pueden crear una condición de desbordamiento, su suma tampoco puede crear un desbordamiento.
Entonces, ¿qué pasa si ambos argumentos tienen el mismo signo? Echemos un vistazo al caso en que ambos son positivos: agregar dos argumentos que crean una suma mayor que los tipos MAX_VALUE siempre producirá un valor negativo, por lo que se produce un desbordamiento si arg1 + arg2 > MAX_VALUE. Ahora el valor máximo que podría resultar sería MAX_VALUE + MAX_VALUE (en el caso extremo ambos argumentos son MAX_VALUE). Para un byte (ejemplo), eso significaría 127 + 127 = 254. Al observar las representaciones de bits de todos los valores que pueden resultar de la suma de dos valores positivos, se encuentra que aquellos que se desbordan (128 a 254) tienen el bit 7 configurado, mientras que todos los que no se desbordan (0 a 127) tienen el bit 7 (superior, signo) borrado. Eso es exactamente lo que comprueba la primera parte (derecha) de la expresión:
if (((s & d & ~r) | (~s & ~d & r)) < 0)
(~s & ~d & r) se vuelve verdadera, solo si ambos operandos (s, d) son positivos y el resultado (r) es negativo (la expresión funciona en los 32 bits, pero el único bit que nos interesa es el bit superior (signo), que se compara con < 0).
Ahora bien, si ambos argumentos son negativos, su suma nunca puede estar más cerca de cero que cualquiera de los argumentos, la suma debe estar más cerca de menos infinito. El valor más extremo que podemos producir es MIN_VALUE + MIN_VALUE, que (nuevamente para el ejemplo de byte) muestra que para cualquier valor dentro del rango (-1 a -128) el bit de signo está establecido, mientras que cualquier posible valor desbordado (-129 a -256 ) tiene el bit de signo borrado. Entonces el signo del resultado revela nuevamente la condición de desbordamiento. Eso es lo que verifica la mitad izquierda (s & d & ~r) para el caso en el que ambos argumentos (s, d) son negativos y un resultado positivo. La lógica es en gran medida equivalente al caso positivo; en todos los patrones de bits que puedan resultar de la suma de dos valores negativos se borrará el bit de signo si y sólo si se produjo un desbordamiento insuficiente.
De forma predeterminada, las matemáticas int y long de Java se ajustan silenciosamente al desbordamiento y al desbordamiento insuficiente. (Las operaciones con números enteros en otros tipos de números enteros se realizan promoviendo primero los operandos a int o long, según JLS 4.2.2 ).
A partir de Java 8, java.lang.Mathproporciona métodos addExact, subtractExact, , y estáticos para argumentos int y long que realizan la operación nombrada, generando ArithmeticException en caso de desbordamiento multiplyExact. (No existe un método divideExact; deberá verificar usted mismo el caso especial ( ).)incrementExactdecrementExactnegateExactMIN_VALUE / -1
A partir de Java 8, java.lang.Math también permite toIntExactconvertir un largo a un int, lanzando ArithmeticException si el valor del largo no cabe en un int. Esto puede ser útil, por ejemplo, para calcular la suma de ints utilizando operaciones matemáticas largas sin marcar y luego usar toIntExactpara convertir a int al final (pero tenga cuidado de no permitir que la suma se desborde).
Si todavía estás usando una versión anterior de Java, Google Guava proporciona métodos estáticos IntMath y LongMath para verificar sumas, restas, multiplicaciones y exponenciaciones (lanzando el desbordamiento). Estas clases también proporcionan métodos para calcular factoriales y coeficientes binomiales que regresan MAX_VALUEen caso de desbordamiento (lo cual es menos conveniente de verificar). Las clases de utilidad primitivas de Guava, SignedBytes, y , proporcionan métodos para limitar tipos más grandes UnsignedBytes( lanzando IllegalArgumentException en caso de desbordamiento/desbordamiento, no ArithmeticException), así como métodos que regresan o en caso de desbordamiento.ShortsIntscheckedCastsaturatingCastMIN_VALUEMAX_VALUE
Java no hace nada con el desbordamiento de enteros para tipos primitivos int o long e ignora el desbordamiento con enteros positivos y negativos.
Esta respuesta primero describe el desbordamiento de enteros, brinda un ejemplo de cómo puede suceder, incluso con valores intermedios en la evaluación de expresiones, y luego brinda enlaces a recursos que brindan técnicas detalladas para prevenir y detectar el desbordamiento de enteros.
La aritmética de enteros y las expresiones que provocan un desbordamiento inesperado o no detectado son un error de programación común. El desbordamiento de enteros inesperado o no detectado también es un problema de seguridad explotable bien conocido, especialmente porque afecta a los objetos de matriz, pila y lista.
El desbordamiento puede ocurrir en una dirección positiva o negativa donde el valor positivo o negativo estaría más allá de los valores máximo o mínimo para el tipo primitivo en cuestión. El desbordamiento puede ocurrir en un valor intermedio durante la evaluación de una expresión u operación y afectar el resultado de una expresión u operación donde se esperaría que el valor final estuviera dentro del rango.
A veces, el desbordamiento negativo se denomina erróneamente desbordamiento insuficiente. El desbordamiento es lo que sucede cuando un valor estaría más cerca de cero de lo que permite la representación. El desbordamiento se produce en aritmética de enteros y es de esperar. El desbordamiento de enteros ocurre cuando una evaluación de enteros estaría entre -1 y 0 o 0 y 1. Lo que sería un resultado fraccionario se trunca a 0. Esto es normal y esperado con aritmética de enteros y no se considera un error. Sin embargo, puede provocar que el código genere una excepción. Un ejemplo es una excepción "ArithmeticException: / por cero" si el resultado del desbordamiento de enteros se utiliza como divisor en una expresión.
Considere el siguiente código:
int bigValue = Integer.MAX_VALUE;
int x = bigValue * 2 / 5;
int y = bigValue / x;
lo que da como resultado que a x se le asigne 0 y la evaluación posterior de bigValue / x arroje una excepción, "ArithmeticException: / por cero" (es decir, dividir por cero), en lugar de que a y se le asigne el valor 2.
El resultado esperado para x sería 858.993.458, que es menor que el valor int máximo de 2.147.483.647. Sin embargo, el resultado intermedio de evaluar Integer.MAX_Value * 2 sería 4,294,967,294, que excede el valor int máximo y es -2 de acuerdo con las representaciones de enteros en complemento a 2. La evaluación posterior de -2/5 se evalúa como 0, que se asigna a x.
Reorganizando la expresión para calcular x a una expresión que, cuando se evalúa, divide antes de multiplicar, el siguiente código:
int bigValue = Integer.MAX_VALUE;
int x = bigValue / 5 * 2;
int y = bigValue / x;
da como resultado que a x se le asigne 858,993,458 y a y se le asigne 2, lo cual era de esperar.
El resultado intermedio de bigValue/5 es 429,496,729 que no excede el valor máximo para un int. La evaluación posterior de 429,496,729 * 2 no excede el valor máximo para un int y el resultado esperado se asigna a x. La evaluación de y entonces no se divide por cero. Las evaluaciones para xey funcionan como se esperaba.
Los valores enteros de Java se almacenan y se comportan de acuerdo con representaciones de enteros con signo en complemento a 2. Cuando un valor resultante sería mayor o menor que los valores enteros máximo o mínimo, se obtiene un valor entero en complemento a 2. En situaciones que no están diseñadas expresamente para utilizar el comportamiento del complemento a 2, que es la mayoría de las situaciones aritméticas de enteros comunes, el valor del complemento a 2 resultante provocará una lógica de programación o un error de cálculo, como se muestra en el ejemplo anterior. Un excelente artículo de Wikipedia describe los enteros binarios complementarios a 2 aquí: Complemento a dos - Wikipedia
Existen técnicas para evitar el desbordamiento de enteros involuntario. Las técnicas pueden clasificarse como pruebas de condiciones previas, upcasting y BigInteger.
Las pruebas de condiciones previas comprenden examinar los valores que entran en una operación o expresión aritmética para garantizar que no se produzca un desbordamiento con esos valores. La programación y el diseño deberán crear pruebas que garanticen que los valores de entrada no causarán desbordamiento y luego determinar qué hacer si se producen valores de entrada que causen desbordamiento.
La conversión ascendente comprende el uso de un tipo primitivo más grande para realizar la operación o expresión aritmética y luego determinar si el valor resultante está más allá de los valores máximo o mínimo para un número entero. Incluso con la conversión ascendente, aún es posible que el valor o algún valor intermedio en una operación o expresión supere los valores máximos o mínimos para el tipo de conversión ascendente y provoque un desbordamiento, que tampoco se detectará y provocará resultados inesperados y no deseados. Mediante análisis o condiciones previas, es posible evitar el desbordamiento con la conversión ascendente cuando la prevención sin la conversión ascendente no es posible o práctica. Si los números enteros en cuestión ya son tipos primitivos largos, entonces la conversión ascendente no es posible con tipos primitivos en Java.
La técnica BigInteger comprende el uso de BigInteger para la operación o expresión aritmética utilizando métodos de biblioteca que utilizan BigInteger. BigInteger no se desborda. Utilizará toda la memoria disponible, si es necesario. Sus métodos aritméticos normalmente son sólo un poco menos eficientes que las operaciones con números enteros. Aún es posible que un resultado usando BigInteger pueda estar más allá de los valores máximos o mínimos para un número entero; sin embargo, no se producirá desbordamiento en la aritmética que conduce al resultado. La programación y el diseño aún necesitarán determinar qué hacer si un resultado de BigInteger supera los valores máximo o mínimo para el tipo de resultado primitivo deseado, por ejemplo, int o long.
El programa CERT del Carnegie Mellon Software Engineering Institute y Oracle han creado un conjunto de estándares para la programación Java segura. En los estándares se incluyen técnicas para prevenir y detectar el desbordamiento de enteros. El estándar se publica como un recurso en línea de libre acceso aquí: The CERT Oracle Secure Coding Standard for Java
La sección del estándar que describe y contiene ejemplos prácticos de técnicas de codificación para prevenir o detectar el desbordamiento de enteros se encuentra aquí: NUM00-J. Detectar o prevenir el desbordamiento de enteros
También están disponibles el formulario de libro y el formulario PDF del estándar de codificación segura de Oracle CERT para Java.
Después de haberme encontrado con este problema, aquí está mi solución (tanto para la multiplicación como para la suma):
static boolean wouldOverflowOccurwhenMultiplying(int a, int b) {
// If either a or b are Integer.MIN_VALUE, then multiplying by anything other than 0 or 1 will result in overflow
if (a == 0 || b == 0) {
return false;
} else if (a > 0 && b > 0) { // both positive, non zero
return a > Integer.MAX_VALUE / b;
} else if (b < 0 && a < 0) { // both negative, non zero
return a < Integer.MAX_VALUE / b;
} else { // exactly one of a,b is negative and one is positive, neither are zero
if (b > 0) { // this last if statements protects against Integer.MIN_VALUE / -1, which in itself causes overflow.
return a < Integer.MIN_VALUE / b;
} else { // a > 0
return b < Integer.MIN_VALUE / a;
}
}
}
boolean wouldOverflowOccurWhenAdding(int a, int b) {
if (a > 0 && b > 0) {
return a > Integer.MAX_VALUE - b;
} else if (a < 0 && b < 0) {
return a < Integer.MIN_VALUE - b;
}
return false;
}
siéntase libre de corregir si está incorrecto o si se puede simplificar. He realizado algunas pruebas con el método de multiplicación, en su mayoría casos extremos, pero aún podría estar mal.
