c++ - ¿Cómo detectar el desbordamiento de enteros?

integer-overflow

Question

Estaba escribiendo un programa en C ++ para encontrar todas las soluciones de a ^b = c , donde a , b y c usan todos los dígitos 0-9 exactamente una vez. El programa realizó un bucle sobre los valores de a y b , y ejecutó una rutina de conteo de dígitos cada vez en a , b y a ^b para verificar si se cumplía la condición de los dígitos.

Sin embargo, se pueden generar soluciones espurias cuando a ^b desborda el límite entero. Terminé revisando 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 un desbordamiento, pero nunca lo he visto a través de C o C ++.

Answer 1

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

No estoy de acuerdo con esto. Podría escribir un poco de asm en línea y usar una joinstrucción de (desbordamiento de salto) asumiendo que está en x86 para atrapar el desbordamiento. Por supuesto, su código ya no sería portátil a otras arquitecturas.

mirar info asy info gcc.

Answer 2

Advertencia: GCC puede optimizar una comprobación de desbordamiento al compilar con -O2 . La opción -Wall te -Wall 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 esto sería increíblemente tedioso de usar sistemáticamente.

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

Necesitamos desesperadamente una mejor solución. Creo que el compilador debería emitir una advertencia de forma predeterminada cuando se realiza una optimización que se basa en que no se produce un desbordamiento. La situación actual permite al compilador optimizar un control de desbordamiento, lo cual es inaceptable en mi opinión.

Answer 3

Algunos compiladores proporcionan acceso al indicador de desbordamiento de enteros en la CPU que luego podría 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

Answer 4

Aquí hay una solución "no portátil" a la pregunta. Las CPU Intel x86 y x64 tienen el denominado registro EFLAGS ( http://en.wikipedia.org/wiki/EFLAGS ), que es llenado por el procesador después de cada operación aritmética de enteros. Me saltaré una descripción detallada aquí. Los indicadores relevantes son el indicador "Desbordamiento" (máscara 0x800) y el indicador "Llevar" (máscara 0x1). Para interpretarlos correctamente, uno debe considerar si los operandos son de tipo firmado o sin signo.

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

#include <cstddef>
#if defined( _MSC_VER )
#include <intrin.h>
#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 establecen los indicadores de acarreo o desbordamiento. En el código de ejemplo proporcionado de main (), se produce un desbordamiento y ambos indicadores se establecen en 1. Esta verificación no implica ningún otro cálculo, por lo que debe ser bastante rápido.

Answer 5

Aunque han pasado dos años, sentí que también podría agregar mi penithworth para una manera realmente rápida de detectar el desbordamiento de al menos adiciones, lo que podría dar una ventaja para la multiplicación, la división y el 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, puede:

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

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

Edición : Como se señaló, este enfoque, aunque es mejor que otros métodos más elaborados, todavía es 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

Answer 6

Hay una manera de determinar si es probable que una operación se desborde, utilizando las posiciones de los bits de un bit más significativos en los operandos y un poco de conocimiento básico de matemática binario.

Además, cualquiera de los dos operandos resultará (como máximo) un bit más que el bit más alto 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, cualquiera de los dos operandos resultará (como máximo) 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, 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);
}

(Por supuesto, sustituya el número de bits de su entero objetivo).

No estoy seguro de cuál es la forma más rápida de determinar la posición del bit de un bit más alto 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 le 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 de más highestOneBitPosition , pero podría hacerlo (especialmente si sabía cuántos bits había en los operandos de antemano).

Answer 7

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

Probablemente encontrará que esto es más eficiente que hacer la división como lo ha hecho en su ejemplo.

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

Solo he estado echando un vistazo al manual de glibc . Hay una mención de una captura de desbordamiento de enteros ( FPE_INTOVF_TRAP ) como parte de SIGFPE . Eso sería ideal, aparte de los bits desagradables en el manual:

FPE_INTOVF_TRAP Desbordamiento de enteros (imposible en un programa C a menos que habilite la captura de desbordamiento de una manera específica del hardware).

Un poco de vergüenza realmente.

Answer 8

Necesitaba responder esta misma pregunta para los números de punto flotante, donde el enmascaramiento y desplazamiento de bits no parece prometedor. El enfoque que establecí funciona con números de coma flotante y sin signo, enteros y de 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. Calcula y compara los signos de los operandos.

   a. Si cualquiera de los valores es cero, entonces ni la suma ni la resta pueden desbordarse. Saltar pruebas restantes.

   segundo. Si los signos son opuestos, entonces la adición no puede desbordarse. Saltar pruebas restantes.

   do. Si los signos son los mismos, la resta no puede desbordarse. Saltar pruebas restantes.

3. Prueba de desbordamiento positivo de MAXVALUE.

   a. Si ambos signos son positivos y MAXVALUE - A <B, la adición se desbordará.

   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, 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 firmada, 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 con 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 dará como resultado cero o 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 es inferior a uno y el otro es mayor que uno, la multiplicación no puede desbordarse.

   re. Si las magnitudes son menores que uno, la división no puede desbordarse.

3. Prueba de desbordamiento positivo de MAXVALUE.

   a. Si ambos operandos son mayores que uno y MAXVALUE / A <B, entonces la multiplicación se desbordará.

   segundo. Si B es menor que uno y MAXVALUE * B <A, la división se desbordará.

4. De lo contrario, no hay desbordamiento.

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

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

Answer 9

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

Algunos compiladores le permiten insertar instrucciones de captura en el código. En GCC, la opción es -ftrapv (pero debo admitir que nunca la he usado. Lo verificaré después de la publicación).

Lo único que puedes hacer con un compilador y un dispositivo portátil independiente es verificar los desbordamientos por tu cuenta. Al igual que hiciste en tu ejemplo.

Editar:

Simplemente marcado: -ftrapv parece no hacer nada en x86 utilizando el último GCC. Supongo que es una sobra de una versión antigua o específica de alguna otra arquitectura. Esperaba que el compilador insertara un código de operación INTO después de cada adición. Lamentablemente no hace esto.

Answer 10

Para enteros sin signo, solo verifique que el resultado sea más pequeño 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 se pueden desbordar, y los enteros del mismo signo solo el resultado es de diferente signo:

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

Answer 11

Si tiene un tipo de datos que es más grande que el que desea probar (digamos que hace un agregado de 32 bits y tiene un tipo de 64 bits). Entonces esto detectará si se produjo un desbordamiento. Mi ejemplo es para un complemento de 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 en 0x80000000 y finalmente uint16_t convierte en uint64_t .

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

Answer 12

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

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

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

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

// for addition
#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 */;

// for subtraction
#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 */;

// for multiplication
#include <limits.h>
int a = <something>;
int x = <something>;
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 INT_MIN o INT_MAX .

Answer 13

Veo que mucha gente respondió la pregunta sobre el desbordamiento, pero quería abordar su problema original. Dijo que el problema era encontrar una ^b = c tal que todos los dígitos se usen sin repetir. Ok, eso no es lo que pidió en esta publicación, pero sigo pensando que era necesario estudiar el límite superior del problema y concluir que nunca tendría que calcular o detectar un desbordamiento (nota: no soy competente En matemáticas, 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 requiere el problema para a, b o c es 98.765.432. De todos modos, comenzando por dividir el problema en las partes triviales y no triviales:

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

Ahora solo tenemos que demostrar que ninguna otra solución es posible y que 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 para cada a y b). 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

Note, 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 puede verse, las combinaciones disponibles para probar ayb son realmente pequeñas. Para b == 14, debemos probar 2 y 3. Para b == 3, comenzamos en 2 y paramos en 462. Todos los resultados se otorgan para que sean menores que ~ 98M.

Ahora solo pruebe todas las combinaciones anteriores y busque las que no repiten ningún dígito:

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

Ninguno de ellos coincide con el problema (que también se puede ver con 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 necesite enteros de precisión arbitrarios (el código no calcula nada más que 98 millones), sino porque descubrimos que la cantidad de pruebas es tan pequeña que debemos usar un lenguaje de alto nivel para haga uso de sus contenedores y bibliotecas incorporadas (también tenga en cuenta: 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)

Answer 14

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

Para el 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í. Dado que a estos dos les gusta ser compatibles con __builtin , probablemente sea seguro asumir que así es como funciona Clang también.

Hay un __builtin para cada operación aritmética que puede desbordar (suma, resta, multiplicación), con variantes con signo y sin signo, para tamaños int, tamaños largos y largos largos. La sintaxis para el nombre es __builtin_[us](operation)(l?l?)_overflow :

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

Por lo tanto, para una adición de entero largo con signo comprobado, 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+ ofrecen además elementos genéricos que funcionan sin especificar el tipo de los valores: __builtin_add_overflow , __builtin_sub_overflow y __builtin_mul_overflow . Estos también funcionan en tipos más pequeños que int .

Las incorporaciones bajan a lo mejor para la plataforma. En x86, verifican las banderas de acarreo, desbordamiento y señalización.

El cl.exe de Visual Studio no tiene equivalentes directos. Para las adiciones y sustracciones sin firmar, incluyendo <intrin.h> 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 firmadas o multiplicaciones.

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

Answer 15

La captura de los Desbordamientos de enteros en C indica una solución más general que la que analiza CERT (es más general en términos de tipos manejados), incluso si requiere algunas extensiones GCC (no sé qué tan ampliamente soportadas son).

Answer 16

mozilla::CheckedInt<T>proporciona matemática de enteros verificados por desbordamiento para el tipo de entero T(usando los intrínsecos del compilador en clang y gcc, según estén disponibles). El código está bajo MPL 2.0 y depende de tres ( IntegerTypeTraits.h, Attributes.hy Compiler.h) otros encabezados de biblioteca no estándar de solo encabezado más la maquinaria de aserción específica de Mozilla . Probablemente quiera reemplazar la maquinaria de aserción si importa el código.

Answer 17

clang ahora admite comprobaciones dinámicas de desbordamiento para enteros con y sin signo. Ver -fsanitize=integer interruptor -fsanitize=integer . Por ahora, solo es un compilador de C ++ con verificación de desbordamiento dinámico totalmente compatible para propósitos de depuración.

Answer 18

@MSalters: Buena idea.

Si se requiere el cálculo de enteros (para precisión), pero el punto flotante está disponible, podría hacer algo como:

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
}
}

Answer 19

Para realizar una multiplicación sin firmar sin desbordarse de forma portátil, se puede utilizar lo siguiente:

... /* 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;
}

Answer 20

Pruebe esta macro para probar el bit de desbordamiento de las máquinas de 32 bits (adaptó la solución de Angel Sinigersky)

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

Lo definí como una macro porque, de lo contrario, el bit de desbordamiento se habría sobrescrito.

Posteriormente es una pequeña aplicación con el código de segmento anterior:

#include <cstddef>
#include <stdio.h>
#include <iostream>
#include <conio.h>
#if defined( _MSC_VER )
#include <intrin.h>
#include <oskit/x86>
#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);
}

Answer 21

Una forma limpia de hacerlo sería anular a todos los operadores (+ y * en particular) y verificar si hay un desbordamiento antes de realizar las operaciones.

Answer 22

CERT ha desarrollado un nuevo enfoque para detectar e informar sobre el desbordamiento de enteros con signo, el ajuste de enteros sin signo y el truncamiento de enteros utilizando el modelo de enteros (AIR) de rango infinito "como si". CERT ha publicado un informe técnico que describe el modelo y produjo un prototipo funcional basado en GCC 4.4.0 y GCC 4.5.0.

El modelo de enteros de AIR produce un valor equivalente a uno que se habría obtenido utilizando enteros de rango infinito o generará una infracción de restricción de tiempo de ejecución. A diferencia de los modelos de enteros anteriores, los enteros de AIR no requieren trampas precisas y, por consiguiente, no rompen ni inhiben la mayoría de las optimizaciones existentes.

Answer 23

Calcula los resultados con dobles. Tienen 15 dígitos significativos. Su requisito tiene un límite superior duro en c de 10 ⁸ : puede tener un máximo de 8 dígitos. Por lo tanto, el resultado será preciso si está dentro del rango y, de lo contrario, no se desbordará.

Answer 24

Depende para que lo uses. Al realizar una suma larga sin firmar (DWORD) o una multiplicación, la mejor solución es utilizar ULARGE_INTEGER.

ULARGE_INTEGER es una estructura de dos DWORD. Se puede acceder al valor completo como "QuadPart", mientras que se accede al hi DWORD como "HighPart" y al bajo DWORD se accede como "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)

// cualquier desbordamiento se almacena en a.HighPart (hasta 32 bits)

Answer 25

El conjunto de instrucciones x86 incluye una instrucción de multiplicación sin signo que almacena el resultado en dos registros. Para usar esa instrucción de C, se puede escribir el siguiente código en el programa de 64 bits (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;
}

Para el programa de 32 bits se necesita un resultado de 64 bits y los parámetros de 32 bits.

Alternativa es utilizar instintos dependientes del compilador para verificar el registro de bandera. La documentación de GCC para instintos de desbordamiento se puede encontrar en https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html

Answer 26

El ensamblaje en línea le permite verificar el bit de desbordamiento directamente. Si va a utilizar C ++, realmente debería aprender a ensamblar.

Answer 27

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

Este es un clangcompilador parcheado , que agrega cheques al código en tiempo de compilación. Así que obtienes una salida como esta:

CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow,
BINARY OPERATION: left (int32): 2147483647 right (int32): 1

Answer 28

Otra variante de solución que usa el ensamblador es un procedimiento externo. Este ejemplo para la multiplicación de enteros sin signo usando g ++ y fasm bajo linux x64.

Este procedimiento multiplica dos argumentos enteros sin signo (32 bits) (según la specification para amd64 (sección 3.2.3 Paso de parámetros)

Si la clase es INTEGER, se usa el siguiente registro disponible de la secuencia% rdi,% rsi,% rdx,% rcx,% r8 y% r9

(Edi y Esi se registran en mi código) y devuelve el resultado o 0 si se ha producido un desbordamiento.

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

prueba:

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;
}

Programa de enlace con archivo objeto asm. En mi caso en Qt Creator, agréguelo a LIBS en un archivo .pro.

Answer 29

Para ampliar la respuesta de Head Geek, hay una forma más rápida de hacerlo addition_is_safe;

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

Esto utiliza una arquitectura de máquina segura, ya que los enteros sin signo de 64 y 32 bits aún funcionarán bien. Básicamente, creo una máscara que enmascara todo menos el bit más significativo. Luego, enmascara ambos enteros, y si alguno de ellos no tiene ese bit establecido, entonces la adición es segura.

Esto sería incluso más rápido si preinicializa la máscara en algún constructor, ya que nunca cambia.

Answer 30

#include <stdio.h>
#include <stdlib.h>
#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: %d b: %d/n", a, b);
}
}