359 votos

La mejor manera de detectar desbordamiento de entero en C / C

Yo estaba escribiendo un programa en C++ para encontrar todas las soluciones de unb = c, donde un, b y c juntos uso de todos los dígitos 0-9 exactamente una vez. El programa itera sobre los valores de un y b, y corrió a un dígito de conteo de rutina cada vez que en un, b, y unab para comprobar si los dígitos condición se ha cumplido.

Sin embargo, falsas soluciones que se pueden generar cuando unb desbordamientos de entero límite. Terminé la comprobación de esto usando un código similar a:

unsigned long b, c, c_test;
...
c_test=c*b;         // Possible overflow
if (c_test/b != c) {/* There has been an overflow*/}
else c=c_test;      // No overflow

Hay una manera mejor de las pruebas para el desbordamiento? Sé que algunos chips tienen un indicador interno que se establece cuando se produce desbordamiento, pero nunca he visto que se accede a través de C o C++.

126voto

Head Geek Puntos 10874

No es una manera para determinar si una operación es probable desbordamiento, mediante las posiciones de los más significativos de uno de los bits de los operandos y un poco binaria básica-conocimientos matemáticos.

Además, cualquiera de los dos operandos resultado será (en la mayoría) un poco más de la más grande operando más alto de un bit. Por ejemplo:

bool addition_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits<32 && b_bits<32);
}

Para la multiplicación, cualquiera de los dos operandos resultado será (en la mayoría) la suma de los bits de los operandos. Por ejemplo:

bool multiplication_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits+b_bits<=32);
}

Del mismo modo, se puede estimar el tamaño máximo del resultado de a a la potencia de b como esta:

bool exponentiation_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a);
    return (a_bits*b<=32);
}

(Sustituya el número de bits para su destino entero, por supuesto.)

No estoy seguro de la forma más rápida para determinar la posición de la máxima de bits en un número, he aquí un método de fuerza bruta:

size_t highestOneBitPosition(uint32_t a) {
    size_t bits=0;
    while (a!=0) {
        ++bits;
        a>>=1;
    };
    return bits;
}

No es perfecto, pero que voy a dar una buena idea de si cualquiera de los dos números podría desbordamiento antes de hacer la operación. No sé si sería más rápido que simplemente comprobar el resultado de la manera que usted sugiere, debido a que el bucle en el highestOneBitPosition función, pero es posible (especialmente si supieras cuántos bits de los operandos de antemano).

84voto

pmg Puntos 52636

Veo que estás usando enteros sin signo. Por definición, en C (no sé acerca de C++), sin signo aritmético no desbordamiento ... así que, al menos para C, su punto es discutible :)

Con enteros, una vez que ha habido desbordamiento, un Comportamiento Indefinido se ha producido y su programa puede hacer cualquier cosa (por ejemplo: procesar las pruebas no concluyentes).

#include <limits.h>
int a = <something>;
int x = <something>;
a += x;              /* UB */
if (a < 0) {         /* unreliable test */
  /* ... */
}

Para crear un conformándose con el programa que necesitas para la prueba de desbordamiento antes de generar dijo desbordamiento. El método puede ser utilizado con enteros sin signo demasiado

#include <limits.h>
int a = <something>;
int x = <something>;
if ((x > 0) && (a > INT_MAX - x)) /* `a + x` would overflow */;
if ((x < 0) && (a < INT_MIN - x)) /* `a + x` would underflow */;
/* ... same thing for subtraction, multiplication, and division */

41voto

Robert Gamble Puntos 41984

Algunos compiladores proporcionan acceso a la bandera de desbordamiento de entero en la CPU que usted podría entonces probar pero esto no es estándar.

También podría poner a prueba la posibilidad de desbordamiento antes de realizar la multiplicación:

 if ( b > ULONG_MAX / a ) // a * b would overflow
 

28voto

A Fog Puntos 614

Advertencia: GCC puede optimizar la distancia de un desbordamiento de verificación al compilar -O2. La opción -Wall le dará una advertencia en algunos casos como

if (a + b < a) { /* deal with overflow */ }

pero no en este ejemplo:

b = abs(a);
if (b < 0) { /* deal with overflow */ }

La única manera segura es la comprobación de desbordamiento antes de que se produzca, como se describe en el CERT de papel, y este iba a ser increíblemente tedioso para utilizar de forma sistemática.

Compilar con -fwrapv resuelve el problema, pero deshabilita algunas optimizaciones.

Necesitamos desesperadamente una solución mejor. Creo que el compilador debe emitir una advertencia por defecto a la hora de hacer una optimización que se basa en el desbordamiento no ocurre. La situación actual permite que el compilador para optimizar la distancia de un desbordamiento de verificación, lo cual es inaceptable en mi opinión.

15voto

Andrew Edgecombe Puntos 13183

La forma más simple para convertir su unsigned longs en unsigned long longs, hacer su multiplicación, y comparar el resultado con 0x100000000LL.

Usted probablemente encontrará que esto es más eficaz que hacer la división como lo hemos hecho en el ejemplo.

Ah, y va a trabajar en C y C++ (como se ha etiquetado a la pregunta con ambos).


Acaba de echar un vistazo a la glibc manual. Hay una mención de un desbordamiento de enteros en la trampa (FPE_INTOVF_TRAP) como parte de SIGFPE. Eso sería lo ideal, aparte de la desagradable bits en el manual:

FPE_INTOVF_TRAP Desbordamiento de entero (imposible en un programa de C a menos que se active el desbordamiento de la captura en un hardware específico de la moda).

Una pena realmente.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by: