thumb|250px|El desbordamiento de enteros se puede demostrar a través de un odómetro en el que se va a dar la vuelta al marcador, una versión mecánica del fenómeno. Todos los dígitos están configurados en el máximo de 9 y el siguiente incremento del dígito blanco provoca una cascada de adiciones de arrastre que establece todos los dígitos en 0, pero no hay un dígito más alto para cambiar a 1, por lo que el contador se reinicia a cero. Esta situación corresponde al concepto de "retornar", en contraste con el de "saturar", situación que se traduce en el bloqueo del contador
En programación, se produce un desbordamiento de enteros cuando una operación aritmética intenta crear un valor numérico que está fuera del rango que puede representarse con un número dado de dígitos, ya sea mayor que el máximo o menor que el mínimo valor representable.
El resultado más común de un desbordamiento es que se almacenan los dígitos representables menos significativos del resultado; se dice que el resultado se envuelve alrededor del máximo (es decir, el resultado obtenido se corresponde a aplicar el módulo del máximo admisible, una potencia entera de la base interna de cálculo, generalmente dos en las computadoras modernas, pero a veces diez u otro número).
Una condición de desbordamiento puede dar resultados que conducen a un comportamiento no deseado. En particular, si no se ha anticipado esta posibilidad, el desbordamiento puede comprometer la fiabilidad de un programa y su seguridad.
Para algunas aplicaciones, como los temporizadores y los relojes, puede ser conveniente ajustar el desbordamiento. El estándar C11 indica que para enteros sin signo, el ajuste de módulo es el comportamiento definido y el término desbordamiento nunca se aplica: "un cálculo que involucre operandos sin signo nunca puede desbordarse".
En algunos procesadores como las tarjetas gráficas (GPUs) y procesadores digitales de señales (DSPs) que soportan aritmética de saturación, los resultados desbordados se "fijan", es decir, se establecen en el valor mínimo o máximo del rango representable, en lugar de modularse con respecto al máximo.
Origen La arquitectura interna de un procesador determina el rango de valores que se pueden representar en sus registros. Aunque la gran mayoría de las computadoras pueden realizar aritmética de precisión múltiple con los operandos de la memoria, lo que permite que los números sean arbitrariamente largos y se eviten los desbordamientos, el ancho del registro limita el tamaño de los números individuales que pueden operarse (por ejemplo, sumar o restar) usando una instrucción única por operación. Los anchos de registro binarios típicos para enteros sin signo incluyen:
8 bits: valor máximo representable 28 - 1 = 255 16 bits: valor máximo representable 216 - 1 = 65,535 32 bits: valor máximo representable 232 - 1 = 4,294,967,295 (el ancho más común para computadoras personales a comienzos de los años 2000) 64 bits: valor máximo representable 264 - 1 = 18,446,744,073,709,551,615 (el ancho más común para los procesadores de las computadoras personales hacia 2020), 128 bits: valor máximo representable 2128 - 1 = 340,282,366,920,938,463,374,607,431,768,211,455
Cuando una operación aritmética produce un resultado mayor que el máximo anterior para un entero de N bits, un desbordamiento reduce el resultado al módulo de la N-ésima potencia de 2, reteniendo solo los bits menos significativos del resultado y provocando una vuelta total.
En particular, multiplicar o sumar dos enteros puede resultar en un valor que es inesperadamente pequeño, y restar de un entero pequeño puede causar un ajuste a un valor positivo grande (por ejemplo, la suma de enteros de 8 bits 255 + 2 da como resultado 1, que es y, de manera similar, la resta 0 - 1 da como resultado 255, una representación complemento a dos de −1).
Dicha envolvente puede causar problemas de seguridad: si se utiliza un valor desbordado como el número de bytes para asignar a un búfer, el búfer se asignará de forma inesperadamente pequeña, lo que podría provocar un desbordamiento del búfer que, dependiendo de su uso, podría a su vez causa la ejecución de código arbitrario.
Si la variable es del tipo entero con signo, un programa puede suponer que una variable siempre contiene un valor positivo. Un desbordamiento de enteros puede hacer que el valor se ajuste y se vuelva negativo, lo que viola la suposición del programa y puede conducir a un comportamiento inesperado (por ejemplo, la adición de enteros de 8 bits de 127 + 1 da como resultado −128, un complemento de dos de 128). Una solución para este problema en particular es usar tipos de enteros sin signo para los valores que un programa espera y asume que nunca serán negativos.
Banderas La mayoría de las computadoras tienen dos indicadores del procesador dedicados para verificar las condiciones de desbordamiento.
La bandera de acarreo se activa cuando el resultado de una suma o resta, considerando los operandos y el resultado como números sin signo, no cabe en el número dado de bits. Esto indica un desbordamiento con un acarreo del bit más significativo. Una operación inmediatamente posterior a "agregar con acarreo" o "restar con préstamo" usaría el contenido de este indicador para modificar un registro o una ubicación de memoria que contenga la parte superior de un valor de varias palabras.
La bandera de desbordamiento también se activa cuando el resultado de una operación en números con signo no tiene el signo que se podría predecir a partir de los signos de los operandos, por ejemplo, un resultado negativo al sumar dos números positivos. Esto indica que se ha producido un desbordamiento y que el resultado presentado (el complemento a dos), no coincide con el resultado verdadero, que no cabría en el número dado de bits.
Variaciones de definición y ambigüedad
Para un tipo sin signo, cuando el resultado ideal de una operación está fuera del rango de los tipos representables y el resultado devuelto se obtiene mediante ajuste, entonces este evento se define comúnmente como un desbordamiento.
En contraste, el estándar C11 define que este evento no es un desbordamiento y establece que "un cálculo que involucre operandos sin signo nunca puede desbordarse".
Cuando el resultado ideal de una operación de enteros está fuera del rango de los tipos representables y el resultado devuelto se obtiene mediante fijación, entonces este evento se define comúnmente como una saturación.
El uso varía según si una saturación es o no un desbordamiento. Para eliminar esta ambigüedad, pueden usarse los términos desbordamiento y saturación.
El término subdesbordamiento se usa más comúnmente para las matemáticas de punto flotante y no para la aritmética de enteros. Sin embargo, se pueden encontrar muchas referencias a este concepto para enteros. Cuando se utiliza el término de subdesbordamiento de un entero, significa que el resultado ideal estaba más cercano a menos infinito, que el valor representable del tipo de salida más cercano a menos infinito.
Cuando se utiliza el término subdesbordamiento entero, puede incluir todos los tipos de desbordamientos o solo los casos en los que el resultado ideal queda más cercano al infinito positivo que el valor representable del tipo de salida más cercano al infinito positivo.
Cuando el resultado ideal de una operación no es un entero exacto, el significado de desbordamiento puede ser ambiguo en los casos límite.
Considérese el caso donde el resultado teórico tiene un valor 127.25 y el valor máximo representable del tipo de salida es 127. Si el desbordamiento se define como el valor ideal que está fuera del rango representable del tipo de salida, este caso se clasificaría como un desbordamiento.
Para las operaciones que tienen un comportamiento de redondeo bien definido, la clasificación de desbordamiento puede necesitar posponerse hasta que se aplique el redondeo.
El estándar C11 define que las conversiones de punto flotante a entero deben redondearse hacia cero. Si se usa C para convertir el valor de coma flotante 127.25 a entero, entonces se debe aplicar primero el redondeo para obtener una salida de entero ideal de 127. Dado que el entero redondeado está en el rango de salidas, el estándar C no clasificaría esta conversión como un desbordamiento.
Métodos para mitigar problemas de desbordamiento de enteros
+ Manejo de desbordamiento de enteros en varios Lenguajes de Programación Lenguaje Enterosin signo Enterocon signo Ada Se modula según tipo raise Constraint_Error C/C++ Módulo potencia de 2 Comportamiento indefinido C# Módulo potencia de 2 en contexto sin comprobación; System.OverflowException se plantea en contexto comprobado Java N/A Módulo potencia de 2 JavaScript Todos los números tienen formato en coma flotante de doble precisión MATLAB Los enteros incorporados se saturan. Enteros de punto fijo configurables para desbordar o saturarse Python 2 N/A Convierte a long, entero largo Seed7 N/A Mensaje raise OVERFLOW_ERRORSeed7 manual, section 15.2.3 OVERFLOW_ERROR. Scheme N/A Convierte a bigNum Simulink Configurable para desbordamiento o saturación Smalltalk N/A Convierte a LargeInteger (entero largo) Swift Causa error a menos que use operadores de desbordamiento especiales.The Swift Programming Language. Swift 2.1 Edition. October 21, 2015.
Hay varios métodos de manejo de desbordamiento:
Evitación: Al asignar variables con tipos de datos que son lo suficientemente grandes como para contener todos los valores que posiblemente puedan computarse y almacenarse en ellos, siempre es posible evitar el desbordamiento. Incluso cuando el espacio disponible o los tipos de datos fijos proporcionados por un lenguaje de programación o entorno son demasiado limitados para permitir que las variables se asignen defensivamente con tamaños generosos, al ordenar cuidadosamente las operaciones y verificar los operandos por adelantado, a menudo es posible asegurar a priori que el resultado nunca será mayor de lo que se puede almacenar. Las herramientas de análisis estático de software, las técnicas de verificación formal y el diseño por contrato se pueden utilizar para garantizar de manera más segura y sólida que no se produzca un desbordamiento accidental. Manejo: Si se anticipa que podría producirse un desbordamiento, entonces se pueden insertar pruebas en el programa para detectar cuándo sucede y disponer otro procesamiento para mitigarlo. Por ejemplo, si un resultado importante calculado a partir de las entradas del usuario se desborda, el programa puede detenerse, rechazar la entrada y quizás solicitarle al usuario una entrada diferente, en lugar de que el programa continúe con la entrada desbordada no válida y, en consecuencia, no funcione correctamente. Por ejemplo, es posible agregar dos números cada uno de dos bytes de ancho usando solo una adición de bytes en los pasos siguientes: primero agréguense los bytes bajos y luego agréguense los bytes altos, pero si es necesario efectuar un acarreo de los bytes bajos, esto es un desbordamiento aritmético de la adición de bytes y se hace necesario detectar e incrementar la suma de los bytes altos. las CPUs generalmente tienen una forma de detectar esto para admitir la adición de números más grandes que su tamaño de registro, normalmente utilizando un bit de estado; la técnica se llama aritmética de precisión múltiple. Propagación: si un valor es demasiado grande para almacenarlo, se le puede asignar un valor especial que indica que se ha producido un desbordamiento y luego todas las operaciones sucesivas devuelven este valor de indicador. Estos valores a veces se denominan NaNs, "no un número" en inglés. Esto es útil para que el problema pueda verificarse una vez al final de un cálculo largo en lugar de después de cada paso. Esto a menudo se admite en el hardware de punto flotante, llamado FPUs.