¿Cómo detecto el desbordamiento de enteros sin signo?

Estaba escribiendo un programa en C++ para encontrar todas las soluciones de a ^b = c , donde a , b y c juntos usan todos los dígitos del 0 al 9 exactamente una vez. El programa recorrió 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 dígitos.

Sin embargo, se pueden generar soluciones espurias cuando a ^b sobrepasa el límite de enteros. Terminé comprobando 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

¿Existe 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 he visto que se acceda a él a través de C o C++.

Tenga en cuenta que el desbordamiento firmado int es un comportamiento indefinido en C y C++ y, por lo tanto, debe detectarlo sin causarlo. Para conocer el desbordamiento de int firmado antes de la adición, consulte Detección de desbordamiento firmado en C/C++ .

Oct 14 '08 05:10 Chris Johnson

A partir de C23, el encabezado estándar <stdckdint.h>proporciona las siguientes tres macros similares a funciones:

bool ckd_add(type1 *result, type2 a, type3 b);
bool ckd_sub(type1 *result, type2 a, type3 b);
bool ckd_mul(type1 *result, type2 a, type3 b);

donde type1y son cualquier tipo de número entero type2. type3Estas funciones suman, restan o multiplican respectivamente a y b con precisión arbitraria y almacenan el resultado en formato *result. Si el resultado no se puede representar exactamente con type1, la función devuelve true("el cálculo se ha desbordado"). (La precisión arbitraria es una ilusión; los cálculos son muy rápidos y casi todo el hardware disponible desde principios de la década de 1990 puede hacerlo con sólo una o dos instrucciones).

Reescribiendo el ejemplo de OP:

unsigned long b, c, c_test;
// ...
if (ckd_mul(&c_test, c, b))
{
    // returned non-zero: there has been an overflow
}
else
{
    c = c_test; // returned 0: no overflow
}

c_test contiene el resultado potencialmente desbordado de la multiplicación en todos los casos.

Mucho antes de C23, GCC 5+ y Clang 3.8+ ofrecen funciones integradas que funcionan de la misma manera, excepto que el puntero de resultado se pasa en último lugar en lugar de primero __builtin_add_overflow: __builtin_sub_overflowy __builtin_mul_overflow. Estos también funcionan en tipos más pequeños que int.

unsigned long b, c, c_test;
// ...
if (__builtin_mul_overflow(c, b, &c_test))
{
    // returned non-zero: there has been an overflow
}
else
{
    c = c_test; // returned 0: no overflow
}

Clang 3.4+ introdujo funciones integradas de desbordamiento aritmético con tipos fijos, pero son mucho menos flexibles y Clang 3.8 ha estado disponible desde hace mucho tiempo. Busque __builtin_umull_overflowsi necesita utilizar esto a pesar de la alternativa más nueva y más conveniente.

cl.exe de Visual Studio no tiene equivalentes directos. Para sumas y restas sin signo, incluir <intrin.h>le permitirá usar addcarry_uNNy subborrow_uNN(donde NN es el número de bits, como addcarry_u8o subborrow_u64). 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_ines el indicador de acarreo/préstamo en la entrada, y el valor de retorno es el indicador de acarreo/préstamo en la salida. No parece tener equivalentes para operaciones con signo o multiplicaciones.

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

Jan 06 '2014 18:01 zneak

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

Para la suma, dos operandos cualesquiera darán como resultado (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, dos operandos cualesquiera darán como resultado (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);
}

De manera similar, puedes estimar el tamaño máximo del resultado de aa la potencia de basí:

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 por el número entero objetivo, por supuesto).

No estoy seguro de cuál es la forma más rápida de determinar la posición del bit más alto de 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 te dará una buena idea de si dos números cualesquiera 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 highestOneBitPositionfunción, pero podría serlo (especialmente si supiera de antemano cuántos bits había en los operandos).

Oct 13 '2008 23:10 Head Geek