¿Cómo detectar el desbordamiento de enteros?

Estaba escribiendo un progtwig en C ++ para encontrar todas las soluciones de a b = c , donde a , byc juntas usan todos los dígitos 0-9 exactamente una vez. El progtwig pasó por encima de los valores de a y b , y ejecutó una rutina de conteo de dígitos cada vez en a , by a b para verificar si la condición de los dígitos estaba satisfecha.

Sin embargo, las soluciones espurias se pueden generar cuando un b sobrepasa el límite entero. Terminé buscando esto usando un código como:

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 mejor manera de probar el desbordamiento? Sé que algunos chips tienen un indicador interno que se establece cuando se produce el desbordamiento, pero nunca lo he visto acceder a través de C o C ++.

Hay una manera de determinar si una operación puede desbordarse, usando las posiciones de los bits más significativos en los operandos y un poco de conocimiento básico de matemática binaria.

Además, dos operandos resultarán (como máximo) un bit más que el bit de un bit más grande del operando más grande. 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, dos operandos darán como resultado (como máximo) la sum 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, puede estimar el tamaño máximo del resultado de a a la potencia de b esta manera:

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

(Sustituya la cantidad de bits por su entero objective, por supuesto).

No estoy seguro de la manera más rápida de determinar la posición del más alto de un bit en un número, aquí hay 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 eso te dará una buena idea de si dos números podrían desbordarse antes de realizar la operación. No sé si sería más rápido que simplemente verificar el resultado de la manera que sugirió, debido al bucle en la función highestOneBitPosition , pero podría (especialmente si sabía cuántos bits había en los operandos de antemano).

Veo que estás usando enteros sin signo. Por definición, en C (no sé sobre C ++), la aritmética sin signo no se desborda … así que, al menos para C, tu punto es discutible 🙂

Con enteros con signo, una vez que se ha producido un desbordamiento, se ha producido un comportamiento indefinido y su progtwig puede hacer cualquier cosa (por ejemplo: las pruebas de procesamiento no son concluyentes).

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

Para crear un progtwig conforme debe probar el desbordamiento antes de generar dicho desbordamiento. El método se puede usar con enteros sin signo también

 // for addition #include  int a = ; int x = ; if ((x > 0) && (a > INT_MAX - x)) /* `a + x` would overflow */; if ((x < 0) && (a < INT_MIN - x)) /* `a + x` would underflow */; 

 // for subtraction #include  int a = ; int x = ; if ((x < 0) && (a > INT_MAX + x)) /* `a - x` would overflow */; if ((x > 0) && (a < INT_MIN + x)) /* `a - x` would underflow */; 

 // for multiplication #include  int a = ; int x = ; if (a > INT_MAX / x) /* `a * x` would overflow */; if ((a < INT_MIN / x)) /* `a * x` would underflow */; // there may be need to check for -1 for two's complement machines if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */ if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */ 

para la división (excepto para el caso especial INT_MIN y -1 ) no hay posibilidad de pasar por INT_MIN o INT_MAX .

Clang 3.4+ y GCC 5+ ofrecen comprobaciones aritméticas comprobadas. Ofrecen una solución muy rápida a este problema, especialmente cuando se compara con las comprobaciones de seguridad de prueba de bits.

Por ejemplo, en la pregunta de OP, funcionaría así:

 unsigned long b, c, c_test; if (__builtin_umull_overflow(b, c, &c_test)) { // returned non-zero: there has been an overflow } else { // return zero: there hasn't been an overflow } 

La documentación de Clang no especifica si c_test contiene el resultado desbordado si se produjo un desbordamiento, pero la documentación de GCC dice que sí lo hace. Dado que a estos dos les gusta ser compatibles con __builtin , probablemente sea seguro suponer que así es como funciona Clang también.

Hay un __builtin para cada operación aritmética que puede desbordarse (sum, resta, multiplicación), con variantes firmadas y sin firmar, para tamaños int, longitudes largas y tamaños largos y largos. La syntax para el nombre es __builtin_[us](operation)(l?l?)_overflow :

  • u para unsigned o s para signed ;
  • la operación es una de add , sub o mul ;
  • no l sufijo significa que los operandos son int s; uno l significa long ; dos l s significa long long .

Por lo tanto, para una adición de entero largo marcado y marcado, sería __builtin_saddl_overflow . La lista completa se puede encontrar en la página de documentación de Clang .

GCC 5+ y Clang 3.8+ también ofrecen edificaciones genéricas que funcionan sin especificar el tipo de valores: __builtin_add_overflow , __builtin_sub_overflow y __builtin_mul_overflow . Estos también funcionan en tipos más pequeños que int .

Los builtins bajan a lo mejor para la plataforma. En x86, verifican los indicadores de acarreo, desbordamiento y señalización.

Cl.exe de Visual Studio no tiene equivalentes directos. Para adiciones y restas sin firmar, incluyendo le permitirá usar addcarry_uNN y addcarry_uNN (donde NN es el número de bits, como addcarry_u8 o addcarry_u8 ). Su firma es un poco obtusa:

 unsigned char _addcarry_u32(unsigned char c_in, unsigned int src1, unsigned int src2, unsigned int *sum); unsigned char _subborrow_u32(unsigned char b_in, unsigned int src1, unsigned int src2, unsigned int *diff); 

c_in / b_in es el indicador de acarreo / préstamo en la entrada, el valor de retorno es el acarreo / préstamo en la salida. No parece tener equivalentes para operaciones o multiplicaciones firmadas.

De lo contrario, Clang para Windows ahora está listo para producción (lo suficientemente bueno para Chrome), por lo que podría ser una opción también.

Algunos comstackdores proporcionan acceso al indicador de desbordamiento de enteros en la CPU, que luego puede probar, pero esto no es estándar.

También puede probar la posibilidad de desbordamiento antes de realizar la multiplicación:

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

Advertencia: GCC puede optimizar una verificación de desbordamiento al comstackr con -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 forma segura es verificar el desbordamiento antes de que ocurra, como se describe en el documento CERT , y sería increíblemente tedioso utilizarlo sistemáticamente.

La -fwrapv con -fwrapv resuelve el problema pero desactiva algunas optimizaciones.

Necesitamos desesperadamente una mejor solución. Creo que el comstackdor debería emitir una advertencia por defecto cuando no se realiza una optimización que se basa en el desbordamiento. La situación actual permite al comstackdor optimizar una verificación de desbordamiento, lo cual es inaceptable en mi opinión.

clang ahora admite comprobaciones dinámicas de desbordamiento para enteros con y sin signo. Ver -fsanitize = integer switch Por ahora, es solo un comstackdor de C ++ con comprobación de desbordamiento dynamic totalmente soportado para fines de depuración.

Aquí hay una solución “no portátil” para la pregunta. Las CPU Intel x86 y x64 tienen el llamado EFLAGS-register ( http://en.wikipedia.org/wiki/EFLAGS ), que el procesador llena después de cada operación aritmética de números enteros. Voy a omitir una descripción detallada aquí. Los indicadores relevantes son la bandera “Desbordamiento” (máscara 0x800) y la bandera “Transporte” (máscara 0x1). Para interpretarlos correctamente, uno debe considerar si los operandos son de tipo firmado o no firmado.

Aquí hay una forma práctica de verificar los indicadores de C / C ++. El siguiente código funcionará en Visual Studio 2005 o posterior (32 y 64 bits), así como en GNU C / C ++ de 64 bits.

 #include  #if defined( _MSC_VER ) #include  #endif inline size_t query_intel_x86_eflags( const size_t query_bit_mask ) { #if defined( _MSC_VER ) return __readeflags() & query_bit_mask; #elif defined( __GNUC__ ) // this code will work only on 64-bit GNU-C machines; // Tested and does NOT work with Intel C++ 10.1! size_t eflags; __asm__ __volatile__( "pushfq \n\t" "pop %%rax\n\t" "movq %%rax, %0\n\t" :"=r"(eflags) : :"%rax" ); return eflags & query_bit_mask; #else #pragma message("No inline assembly will work with this compiler!") return 0; #endif } int main(int argc, char **argv) { int x = 1000000000; int y = 20000; int z = x * y; int f = query_intel_x86_eflags( 0x801 ); printf( "%X\n", f ); } 

Si los operandos se multiplicaran sin desbordamiento, obtendría un valor de retorno de 0 de query_intel_eflags (0x801), es decir, no se configuran los indicadores de acarreo ni de desbordamiento. En el código de ejemplo proporcionado de main (), se produce un desbordamiento y las dos banderas se establecen en 1. Esta comprobación no implica ningún otro cálculo, por lo que debería ser bastante rápido.

Veo que mucha gente respondió la pregunta sobre el desbordamiento, pero quería abordar su problema original. Dijo que el problema era encontrar un b = c tal que todos los dígitos se usaran sin repetir. Ok, eso no es lo que preguntó en esta publicación, pero sigo pensando que era necesario estudiar el límite superior del problema y concluir que nunca necesitaría calcular o detectar un desbordamiento (nota: no soy competente en matemáticas, así que lo hice paso a paso, pero el resultado final fue tan simple que podría tener una fórmula simple).

El punto principal es que el límite superior que el problema requiere para a, boc es 98.765.432. De todos modos, comenzando por dividir el problema en las partes triviales y no triviales:

  • x 0 == 1 (todas las permutaciones de 9, 8, 7, 6, 5, 4, 3, 2 son soluciones)
  • x 1 == x (no hay solución posible)
  • 0 b == 0 (no hay solución posible)
  • 1 b == 1 (no es posible una solución)
  • a b , a> 1, b> 1 (no trivial)

Ahora solo tenemos que demostrar que no hay otra solución posible y solo las permutaciones son válidas (y luego el código para imprimirlas es trivial). Volvemos al límite superior. En realidad, el límite superior es c ≤ 98.765.432. Es el límite superior porque es el número más grande con 8 dígitos (10 dígitos en total menos 1 por cada ayb). Este límite superior es solo para c porque los límites para a y b deben ser mucho más bajos debido al crecimiento exponencial, como podemos calcular, variando b desde 2 hasta el límite superior:

  9938.08^2 == 98765432 462.241^3 == 98765432 99.6899^4 == 98765432 39.7119^5 == 98765432 21.4998^6 == 98765432 13.8703^7 == 98765432 9.98448^8 == 98765432 7.73196^9 == 98765432 6.30174^10 == 98765432 5.33068^11 == 98765432 4.63679^12 == 98765432 4.12069^13 == 98765432 3.72429^14 == 98765432 3.41172^15 == 98765432 3.15982^16 == 98765432 2.95305^17 == 98765432 2.78064^18 == 98765432 2.63493^19 == 98765432 2.51033^20 == 98765432 2.40268^21 == 98765432 2.30883^22 == 98765432 2.22634^23 == 98765432 2.15332^24 == 98765432 2.08826^25 == 98765432 2.02995^26 == 98765432 1.97741^27 == 98765432 

Observe, por ejemplo, la última línea: dice que 1.97 ^ 27 ~ 98M. Entonces, por ejemplo, 1 ^ 27 == 1 y 2 ^ 27 == 134.217.728 y eso no es una solución porque tiene 9 dígitos (2> 1.97 por lo que en realidad es más grande de lo que debería probarse). Como se puede ver, las combinaciones disponibles para probar a y b son muy pequeñas. Para b == 14, tenemos que probar 2 y 3. Para b == 3, comenzamos en 2 y nos detenemos en 462. Todos los resultados se otorgan a menos de ~ 98M.

Ahora solo prueba todas las combinaciones de arriba y busca las que no repiten ningún dígito:

  ['0', '2', '4', '5', '6', '7', '8'] 2^84 = 7056 ['1', '2', '3', '4', '5', '8', '9'] 2^59 = 3481 ['0', '1', '2', '3', '4', '5', '8', '9'] 2^59 = 3481 (+leading zero) ['1', '2', '3', '5', '8'] 3^8 = 512 ['0', '1', '2', '3', '5', '8'] 3^8 = 512 (+leading zero) ['1', '2', '4', '6'] 2^4 = 16 ['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero) ['1', '2', '4', '6'] 4^2 = 16 ['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero) ['1', '2', '8', '9'] 2^9 = 81 ['0', '1', '2', '8', '9'] 2^9 = 81 (+leading zero) ['1', '3', '4', '8'] 4^3 = 81 ['0', '1', '3', '4', '8'] 4^3 = 81 (+leading zero) ['2', '3', '6', '7', '9'] 6^3 = 729 ['0', '2', '3', '6', '7', '9'] 6^3 = 729 (+leading zero) ['2', '3', '8'] 3^2 = 8 ['0', '2', '3', '8'] 3^2 = 8 (+leading zero) ['2', '3', '9'] 2^3 = 9 ['0', '2', '3', '9'] 2^3 = 9 (+leading zero) ['2', '4', '6', '8'] 2^8 = 64 ['0', '2', '4', '6', '8'] 2^8 = 64 (+leading zero) ['2', '4', '7', '9'] 2^7 = 49 ['0', '2', '4', '7', '9'] 2^7 = 49 (+leading zero) 

Ninguno de ellos coincide con el problema (que también se puede ver por la ausencia de ‘0’, ‘1’, …, ‘9’).

El código de ejemplo que lo resuelve sigue. También tenga en cuenta que está escrito en python, no porque necesita enteros de precisión arbitrarios (el código no calcula nada más grande que 98 millones), sino porque descubrimos que la cantidad de pruebas es tan pequeña que deberíamos usar un lenguaje de alto nivel para hacer uso de sus contenedores y bibliotecas integradas (también nota: el código tiene 28 líneas).

  import math m = 98765432 l = [] for i in xrange(2, 98765432): inv = 1.0/i r = m**inv if (r < 2.0): break top = int(math.floor(r)) assert(top <= m) for j in xrange(2, top+1): s = str(i) + str(j) + str(j**i) l.append((sorted(s), i, j, j**i)) assert(j**i <= m) l.sort() for s, i, j, ji in l: assert(ji <= m) ss = sorted(set(s)) if s == ss: print '%s %d^%d = %d' % (s, i, j, ji) # Try with non significant zero somewhere s = ['0'] + s ss = sorted(set(s)) if s == ss: print '%s %d^%d = %d (+leading zero)' % (s, i, j, ji) 

Si tiene un tipo de datos que es más grande que el que quiere probar (digamos que hace un agregado de 32 bits y tiene un tipo de 64 bits). Entonces esto detectará si ocurrió un desbordamiento. Mi ejemplo es para agregar 8 bits. Pero se puede ampliar.

 uint8_t x, y; /* give these values */ const uint16_t data16 = x + y; const bool carry = (data16 > 0xff); const bool overflow = ((~(x ^ y)) & (x ^ data16) & 0x80); 

Se basa en los conceptos explicados en esta página: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html

Para un ejemplo de 32 bits, 0xff convierte en 0xffffffff y 0x80 convierte en 0x80000000 y finalmente uint16_t convierte en uint64_t .

NOTA : esto atrapa desbordamientos de sum / resta enteros, y me di cuenta de que su pregunta involucra la multiplicación. En ese caso, la división es probablemente el mejor enfoque. Esta es comúnmente una forma en que las implementaciones de calloc aseguran de que los params no se desborden a medida que se multiplican para obtener el tamaño final.

La forma más simple es convertir sus unsigned long unsigned long long en unsigned long long , hacer su multiplicación y comparar el resultado a 0x100000000LL.

Probablemente descubrirá que esto es más eficiente que hacer la división como lo hizo en su ejemplo.

Ah, y funcionará tanto en C como en C ++ (ya que has etiquetado la pregunta con ambos).


Acabo de echarle un vistazo al manual de glibc . Hay una mención de una trampa de desbordamiento de enteros ( FPE_INTOVF_TRAP ) como parte de SIGFPE . Eso sería ideal, aparte de las partes desagradables en el manual:

FPE_INTOVF_TRAP Desbordamiento de enteros (imposible en un progtwig C a menos que active el reventado de desbordamiento de un modo específico de hardware).

Un poco de vergüenza realmente.

Para enteros sin signo, simplemente verifique que el resultado sea menor que uno de los argumentos:

 unsigned int r, a, b; r = a+b; if (r < a) { // overflow } 

Para enteros con signo puede verificar los signos de los argumentos y del resultado. los enteros de diferentes signos no pueden desbordarse, y los enteros del mismo desbordamiento de signo solo son el resultado es de signo diferente:

 signed int r, a, b, s; r = a+b; s = a>=0; if (s == (b>=0) && s != (r>=0)) { // overflow } 

A pesar de que han pasado dos años, sentí que podría agregar mi penithworth para una forma realmente rápida de detectar desbordamiento para al menos adiciones, lo que podría dar una ventaja para la multiplicación, división y poder de

La idea es que exactamente porque el procesador simplemente dejará que el valor vuelva a cero y que C / C ++ se abstraiga de cualquier procesador específico, usted puede:

 uint32_t x, y; uint32_t value = x + y; bool overflow = value < (x | y); 

Esto asegura que si un operando es cero y uno no, entonces el desbordamiento no se detectará falsamente, y es significativamente más rápido que muchas operaciones NOT / XOR / AND / como se sugirió anteriormente.

Editar : Como se señaló, este enfoque, aunque mejor que otras formas más elaboradas, sigue siendo optimizable. La siguiente es una revisión del código original que contiene la optimización:

 uint32_t x, y; uint32_t value = x + y; bool overflow = value < x; // Alternatively "value < y" should also work 

No puede acceder al indicador de desbordamiento desde C / C ++.

Algunos comstackdores le permiten insertar instrucciones de trampa en el código. En GCC, la opción es -ftrapv (pero tengo que admitir que nunca la he usado. Lo verificará después de publicarla).

La única cosa independiente portátil y comstackdora que puede hacer es verificar los desbordamientos por su cuenta. Como lo hiciste en tu ejemplo.

Editar:

Acabo de comprobar: -ftrapv parece no hacer nada en x86 utilizando el último GCC. Supongo que es una sobra de una versión anterior o específica de alguna otra architecture. Esperaba que el comstackdor insertara un código de operación INTO después de cada adición. Desafortunadamente no hace esto.

Necesitaba responder a esta misma pregunta para los números de coma flotante, donde el enmascaramiento de bits y el cambio no parecen prometedores. El enfoque que establecí funciona para números con signo y sin signo, entero y punto flotante. Funciona incluso si no hay un tipo de datos más grande para promover para cálculos intermedios. No es el más eficiente para todos estos tipos, pero como funciona para todos, vale la pena usarlo.

Prueba de Desbordamiento Firmado, Suma y Resta:

  1. Obtenga las constantes que representan los valores más grandes y más pequeños posibles para el tipo, MAXVALUE y MINVALUE.

  2. Calcule y compare los signos de los operandos.

    a. Si cualquiera de los valores es cero, entonces ni la sum ni la resta pueden desbordarse. Omita las pruebas restantes.

    segundo. Si los signos son opuestos, entonces la sum no puede desbordarse. Omita las pruebas restantes.

    do. Si los signos son iguales, la resta no puede desbordarse. Omita las pruebas restantes.

  3. Prueba de desbordamiento positivo de MAXVALUE.

    a. Si ambos signos son positivos y MAXVALUE – A

    segundo. Si el signo de B es negativo y MAXVALUE – A <-B, la resta se desbordará.

  4. Prueba de desbordamiento negativo de MINVALUE.

    a. Si ambos signos son negativos y MINVALUE – A> B, entonces la adición se desbordará.

    segundo. Si el signo de A es negativo y MINVALUE – A> B, la resta se desbordará.

  5. De lo contrario, no hay desbordamiento.

Prueba de Desbordamiento Firmado, Multiplicación y División:

  1. Obtenga las constantes que representan los valores más grandes y más pequeños posibles para el tipo, MAXVALUE y MINVALUE.

  2. Calcule y compare las magnitudes (valores absolutos) de los operandos en uno. (A continuación, suponga que A y B son estas magnitudes, no los originales firmados).

    a. Si cualquiera de los valores es cero, la multiplicación no puede desbordarse, y la división arrojará cero o un infinito.

    segundo. Si cualquiera de los valores es uno, la multiplicación y la división no pueden desbordarse.

    do. Si la magnitud de un operando está por debajo de uno y el otro es mayor que uno, la multiplicación no puede desbordarse.

    re. Si las magnitudes son ambas menores de una, la división no puede desbordarse.

  3. Prueba de desbordamiento positivo de MAXVALUE.

    a. Si ambos operandos son mayores que uno y MAXVALUE / A

    segundo. Si B es menor que uno y MAXVALUE * B

  4. De lo contrario, no hay desbordamiento.

Nota: El desbordamiento mínimo de MINVALUE es manejado por 3, porque tomamos valores absolutos. Sin embargo, si ABS (MINVALUE)> MAXVALUE, entonces tendremos algunos falsos positivos raros.

Las pruebas de subdesbordamiento son similares, pero implican EPSILON (el número positivo más pequeño mayor que cero).

Otra herramienta interesante: http://embed.cs.utah.edu/ioc/

Este es un comstackdor de clang parcheado, que agrega comprobaciones al código en tiempo de comstackción. So you get output looking like this:

 CLANG ARITHMETIC UNDEFINED at  : Op: +, Reason : Signed Addition Overflow, BINARY OPERATION: left (int32): 2147483647 right (int32): 1 

CERT has developed a new approach to detecting and reporting signed integer overflow, unsigned integer wrapping, and integer truncation using the “as-if” infinitely ranged (AIR) integer model. CERT has published a technical report describing the model and produced a working prototype based on GCC 4.4.0 and GCC 4.5.0.

The AIR integer model either produces a value equivalent to one that would have been obtained using infinitely ranged integers or results in a runtime constraint violation. Unlike previous integer models, AIR integers do not require precise traps, and consequently do not break or inhibit most existing optimizations.

Another variant of solution using assembler is an external procedure. This example for unsigned integer multiplication using g++ and fasm under linux x64.

This procedure multiplies two unsigned integer arguments (32 bits) (according to specification for amd64 (section 3.2.3 Parameter Passing)

If the class is INTEGER, the next available register of the sequence %rdi,%rsi,%rdx,%rcx,%r8 and %r9 is used

(edi and esi registers in my code)) and returns the result or 0 if an overflow has occured.

 format ELF64 section '.text' executable public u_mul u_mul: MOV eax, edi mul esi jnc u_mul_ret xor eax, eax u_mul_ret: ret 

test:

 extern "C" unsigned int u_mul(const unsigned int a, const unsigned int b); int main() { printf("%u\n", u_mul(4000000000,2));//0 printf("%u\n", u_mul(UINT_MAX/2,2));//ok return 0; } 

link program with asm object file. In my case in Qt Creator add it to LIBS in a .pro file

Calculate the results with doubles. They have 15 significant digits. Your requirement has a hard upper bound on c of 10 8 — it can have at most 8 digits. Hence, the result will be precise if it’s in range, and it will not overflow otherwise.

Try this macro to test the overflow bit of 32-bit machines (adapted the solution of Angel Sinigersky)

 #define overflowflag(isOverflow){ \ size_t eflags; \ asm ("pushfl ;" \ "pop %%eax" \ : "=a" (eflags)); \ isOverflow = (eflags >> 11) & 1;} 

I defined it as a macro because otherwise the overflow bit would have been overwritten.

Subsequent is a little application with the code segement above:

 #include  #include  #include  #include  #if defined( _MSC_VER ) #include  #include  #endif using namespace std; #define detectOverflow(isOverflow){ \ size_t eflags; \ asm ("pushfl ;" \ "pop %%eax" \ : "=a" (eflags)); \ isOverflow = (eflags >> 11) & 1;} int main(int argc, char **argv) { bool endTest = false; bool isOverflow; do { cout << "Enter two intergers" << endl; int x = 0; int y = 0; cin.clear(); cin >> x >> y; int z = x * y; detectOverflow(isOverflow) printf("\nThe result is: %d", z); if (!isOverflow) { std::cout << ": no overflow occured\n" << std::endl; } else { std::cout << ": overflow occured\n" << std::endl; } z = x * x * y; detectOverflow(isOverflow) printf("\nThe result is: %d", z); if (!isOverflow) { std::cout << ": no overflow ocurred\n" << std::endl; } else { std::cout << ": overflow occured\n" << std::endl; } cout << "Do you want to stop? (Enter \"y\" or \"Y)" << endl; char c = 0; do { c = getchar(); } while ((c == '\n') && (c != EOF)); if (c == 'y' || c == 'Y') { endTest = true; } do { c = getchar(); } while ((c != '\n') && (c != EOF)); } while (!endTest); } 

You can’t access the overflow flag from C/C++.

I don’t agree with this. You could write some inline asm and use a jo (jump overflow) instruction assuming you are on x86 to trap the overflow. Of course you code would no longer be portable to other architectures.

look at info as and info gcc .

Catching Integer Overflows in C points out a solution more general than the one discussed by CERT (it is more general in term of handled types), even if it requires some GCC extensions (I don’t know how widely supported they are).

Inline assembly lets you check the overflow bit directly. If you are going to be using C++, you really should learn assembly.

A clean way to do it would be to override all operators (+ and * in particular) and check for an overflow before perorming the operations.

To expand on Head Geek’s answer, there is a faster way to do the addition_is_safe ;

 bool addition_is_safe(unsigned int a, unsigned int b) { unsigned int L_Mask = std::numeric_limits::max(); L_Mask >>= 1; L_Mask = ~L_Mask; a &= L_Mask; b &= L_Mask; return ( a == 0 || b == 0 ); } 

This uses machine-architecture safe, in that 64-bit and 32-bit unsigned integers will still work fine. Basically, I create a mask that will mask out all but the most significant bit. Then, I mask both integers, and if either of them do not have that bit set, then addition is safe.

This would be even faster if you pre-initialize the mask in some constructor, since it never changes.

x86 instruction set includes unsigned multiply instruction that stores the result to two registers. To use that instruction from C one can write following code in 64bit program (gcc):

 unsigned long checked_imul(unsigned long a, unsigned long b) { __int128 res = (__int128)a * (__int128)b; if ((unsigned long)(res >> 64)) printf("overflow in integer multiply"); return (unsigned long)res; } 

For 32bit program one needs to make result 64 bit and parameters 32bit.

Alternative is to use compiler depend instincts to check the flag register. GCC documentation for overflow instincts can be found from https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html

mozilla::CheckedInt provides overflow-checked integer math for integer type T (using compiler intrinsics on clang and gcc as available). The code is under MPL 2.0 and depends on three ( IntegerTypeTraits.h , Attributes.h and Compiler.h ) other header-only non-standard library headers plus Mozilla-specific assertion machinery . You probably want to replace the assertion machinery if you import the code.

@MSalters: Good idea.

If the integer calculation is required (for precision), but floating point is available, you could do something like:

 uint64_t foo( uint64_t a, uint64_t b ) { double dc; dc = pow( a, b ); if ( dc < UINT_MAX ) { return ( powu64( a, b ) ); } else { // overflow } } 
 #include  #include  #define MAX 100 int mltovf(int a, int b) { if (a && b) return abs(a) > MAX/abs(b); else return 0; } main() { int a, b; for (a = 0; a <= MAX; a++) for (b = 0; b < MAX; b++) { if (mltovf(a, b) != (a*b > MAX)) printf("Bad calculation: a: %db: %d\n", a, b); } } 

It depends what you use it for. Performing unsigned long(DWORD) addition or Multiplication the best solution is to use ULARGE_INTEGER.

ULARGE_INTEGER is a structure of two DWORDs. The full value can be accessed as “QuadPart” while the hi DWORD is accessed as “HighPart” and the low DWORD is accessed as “LowPart”

Por ejemplo:

DWORD My Addition(DWORD Value_A,DWORD Value_B) { ULARGE_INTEGER a,b;

  b.LowPart = Value_A; // a 32 bit value(up to 32 bit) b.HighPart = 0; a.LowPart = Value_B; // a 32 bit value(up to 32 bit) a.HighPart = 0; a.QuadPart += b.QuadPart; // if a.HighPart // Then a.HighPart contains the overflow(carry) return (a.LowPart + a.HighPart) 

// any overflow is stored in a.HighPart(up to 32 bits)

To perform an unsigned multiplication without overflowing in a portable way the following can be used:

 ... /* begin multiplication */ unsigned multiplicand, multiplier, product, productHalf; int zeroesMultiplicand, zeroesMultiplier; zeroesMultiplicand = number_of_leading_zeroes( multiplicand ); zeroesMultiplier = number_of_leading_zeroes( multiplier ); if( zeroesMultiplicand + zeroesMultiplier <= 30 ) goto overflow; productHalf = multiplicand * ( c >> 1 ); if( (int)productHalf < 0 ) goto overflow; product = productHalf * 2; if( multiplier & 1 ){ product += multiplicand; if( product < multiplicand ) goto overflow; } ..../* continue code here where "product" is the correct product */ .... overflow: /* put overflow handling code here */ int number_of_leading_zeroes( unsigned value ){ int ctZeroes; if( value == 0 ) return 32; ctZeroes = 1; if( ( value >> 16 ) == 0 ){ ctZeroes += 16; value = value << 16; } if( ( value >> 24 ) == 0 ){ ctZeroes += 8; value = value << 8; } if( ( value >> 28 ) == 0 ){ ctZeroes += 4; value = value << 4; } if( ( value >> 30 ) == 0 ){ ctZeroes += 2; value = value << 2; } ctZeroes -= x >> 31; return ctZeroes; }