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

Estaba escribiendo un programa en C ++ para encontrar todas las soluciones de una ^b = c , donde un , b y c juntos utilizan todos los dígitos 0-9 exactamente una vez. El programa enlazadas sobre los valores de una y B , y se pasó una rutina de conteo de dígitos cada vez en una , b y un ^b para comprobar si la condición dígitos se mostró satisfecho.

Sin embargo, se pueden generar soluciones espurias cuando una ^b desborda 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 un desbordamiento, pero nunca lo he visto 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 el desbordamiento int firmado antes de la adición, consulte Detección del desbordamiento firmado en C / C ++ .

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 ... por lo tanto, al menos para C, su punto es discutible :)

Con enteros con signo, una vez que se ha desbordado, se ha producido un comportamiento indefinido (UB) y su programa puede hacer cualquier cosa (por ejemplo: hacer que las pruebas no sean 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>;
// There may be a need to check for -1 for two's complement machines.
// If one number is -1 and another is INT_MIN, multiplying them we get abs(INT_MIN) which is 1 higher than INT_MAX
if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */
if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */
// general case
if (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;

Para la división (excepto para el INT_MINy -1caso especial), no hay ninguna posibilidad de pasar por encima INT_MINo INT_MAX.

No es una forma de determinar si una operación es probable que rebose, utilizando las posiciones de los uno-bits más significativos de los operandos y un poco de conocimiento básico binario-matemáticas.

Además, cualquiera de los dos operandos dará 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, cualquiera de los dos operandos dará 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);
}

Del mismo modo, puede estimar el tamaño máximo del resultado aa la potencia de besta manera:

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 entero objetivo, por supuesto).

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

Clang 3.4+ y GCC 5+ ofrecen funciones aritméticas comprobadas. Ofrecen una solución muy rápida a este problema, especialmente en comparación con las comprobaciones 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_testcontiene el resultado desbordado si ocurrió un desbordamiento, pero la documentación de GCC dice que sí. Dado que a estos dos les gusta ser __builtincompatibles, probablemente sea seguro asumir que así es como funciona Clang.

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

• upara no firmado o spara firmado ;
• la operación es uno de add, subo mul;
• sin lsufijo significa que los operandos son ints; uno lmedio long; dos ls significan long long.

Entonces, para una suma de enteros largos marcados y marcados, 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, órdenes internas genéricos que funcionan sin especificar el tipo de los valores: __builtin_add_overflow, __builtin_sub_overflowy __builtin_mul_overflow. Estos también funcionan en tipos más pequeños que int.

Los componentes se reducen a lo que es mejor para la plataforma. En x86, verifican el acarreo, desbordamiento y firman banderas.

El cl.exe de Visual Studio no tiene equivalentes directos. Para sumas y restas sin firmar, incluso <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 transporte / 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 la producción (lo suficientemente bueno para Chrome), por lo que también podría ser una opción.

Algunos compiladores 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 comprobación de desbordamiento al compilar con -O2. La opción -Wallle 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 del CERT , y esto sería increíblemente tedioso de usar sistemáticamente.

Compilar con -fwrapvresuelve el problema, pero deshabilita algunas optimizaciones.

Necesitamos desesperadamente una mejor solución. Creo que el compilador debería emitir una advertencia por defecto al hacer una optimización que se basa en que no se produzca un desbordamiento. La situación actual le permite al compilador 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. Consulte el modificador -fsanitize = integer . Por ahora, es el único compilador de C ++ con comprobación de desbordamiento dinámico totalmente compatible con fines de depuración.

Veo que muchas personas respondieron la pregunta sobre el desbordamiento, pero quería abordar su problema original. Dijo que el problema era encontrar a ^b = c de modo que todos los dígitos se usen 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 hice esto 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 dividiendo 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 mostrar que no hay otra solución 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 ayb). Este límite superior es solo para c porque los límites para ayb deben ser mucho más bajos debido al crecimiento exponencial, como podemos calcular, variando b de 2 al 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 ayb son realmente pequeñas. Para b == 14, necesitamos probar 2 y 3. Para b == 3, comenzamos en 2 y terminamos en 462. Todos los resultados se otorgan a menos de ~ 98M.

Ahora solo pruebe todas las combinaciones anteriores y busque las que no repitan 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 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 necesite 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 haga uso de sus contenedores y bibliotecas incorporados (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)

Aquí hay una solución "no portátil" a la pregunta. Las CPU Intel x86 y x64 tienen el denominado registro EFLAGS , que el procesador completa después de cada operación aritmética de enteros. Omitiré una descripción detallada aquí. Las banderas relevantes son la Bandera de "Desbordamiento" (máscara 0x800) y la Bandera de "Llevar" (máscara 0x1). Para interpretarlos correctamente, uno debe considerar si los operandos son de tipo con signo o sin signo.

Aquí hay una forma práctica de verificar las banderas desde C / C ++. El siguiente código funcionará en Visual Studio 2005 o posterior (tanto de 32 como de 64 bits), así como en GNU C / C ++ de 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 multiplicaron sin desbordamiento, obtendría un valor de retorno de 0 query_intel_eflags(0x801), es decir, no se establecen ni los indicadores de acarreo ni de desbordamiento. En el código de ejemplo proporcionado de main (), se produce un desbordamiento y los dos indicadores se establecen en 1. Esta comprobación no implica ningún cálculo adicional, por lo que debería ser bastante rápido.

Si tiene un tipo de datos que es más grande que el que desea probar (digamos que agrega 32 bits y tiene un tipo de 64 bits), esto detectará si ocurrió 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, se 0xFFconvierte 0xFFFFFFFFy se 0x80convierte 0x80000000y finalmente se uint16_tconvierte en a uint64_t.

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

La forma más simple es convertir su unsigned longs en unsigned long longs, 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 hizo en su ejemplo.

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

Acabo de leer el 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 programa en C a menos que habilite la captura de desbordamiento de una manera específica de hardware).

Un poco de vergüenza realmente.

Aquí hay una manera realmente rápida de detectar el desbordamiento de al menos las adiciones, lo que podría dar lugar a la multiplicación, división y potencia de.

La idea es que exactamente porque el procesador simplemente permitirá 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 el otro no, entonces el desbordamiento no se detectará falsamente y es significativamente más rápido que muchas operaciones NOT / XOR / AND / test como se sugirió anteriormente.

Como se señaló, este enfoque, aunque es 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;
const bool overflow = value < x; // Alternatively "value < y" should also work

Una forma más eficiente y económica de detectar el desbordamiento de multiplicación es:

uint32_t x, y;
const bool overflow = (x >> 16U) * (y >> 16U);
uint32_t value = overflow ? UINT32_MAX : x * y;

Esto da como resultado UINT32_MAX en desbordamiento o el resultado de la multiplicación. Es un comportamiento estrictamente indefinido permitir que la multiplicación proceda para enteros con signo en este caso.

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.

Lo único que puede hacer independientemente del compilador portátil y es verificar los desbordamientos por su cuenta. Tal como lo hiciste en tu ejemplo.

Sin embargo, -ftrapvparece no hacer nada en x86 usando el último GCC. Supongo que es un remanente de una versión anterior 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.

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 pueden desbordarse, y los enteros del mismo signo se desbordan solo si el resultado es de un signo diferente:

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

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

Prueba de desbordamiento firmada, 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 suma ni la resta pueden desbordarse. Omita las pruebas restantes.

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

   C. Si los signos son iguales, entonces 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 <B, entonces la adición se desbordará.

   si. Si el signo de B es negativo y MAXVALUE - A <-B, entonces 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á.

   si. Si el signo de A es negativo y MINVALUE - A> B, entonces 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 producirá cero o un infinito.

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

   C. 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 menos de 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á.

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

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, tendremos algunos falsos positivos raros.

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

El CERT ha desarrollado un nuevo enfoque para detectar e informar el desbordamiento de enteros firmados, el ajuste de enteros sin firmar y el truncamiento de enteros utilizando el modelo de enteros de rango infinito "AIR". El 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 entero AIR produce un valor equivalente a uno que se habría obtenido usando enteros de rango infinito o da como resultado una violación de restricción de tiempo de ejecución. A diferencia de los modelos enteros anteriores, los enteros AIR no requieren trampas precisas y, en consecuencia, no rompen ni inhiben la mayoría de las optimizaciones existentes.

Otra herramienta interesante es IOC: un comprobador de desbordamiento de enteros para C / C ++ .

Este es un compilador de Clang parcheado , que agrega controles al código en tiempo de compilación.

Obtiene 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

Otra variante de una solución, usando lenguaje ensamblador, es un procedimiento externo. Este ejemplo para la multiplicación de enteros sin signo usando g ++ y fasm en Linux x64.

Este procedimiento multiplica dos argumentos enteros sin signo (32 bits) (de acuerdo con la especificación para amd64 (sección 3.2.3 Paso de parámetros ).

Si la clase es INTEGER, se utiliza 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;
}

Enlace el programa con el archivo de objeto asm. En mi caso, en Qt Creator , agréguelo a LIBSun archivo .pro.

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

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.

Posterior es una pequeña aplicación con el segmento de código 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);
}

Catching Integer Overflows en C señala una solución más general que la discutida por CERT (es más general en términos de tipos manejados), incluso si requiere algunas extensiones de GCC (no sé cuán ampliamente son compatibles).

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

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

Mira info asy info gcc.

Para ampliar la respuesta de Head Geek, hay una forma más rápida de hacer el 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 bits y 32 bits seguirán funcionando bien. Básicamente, creo una máscara que enmascarará todo menos el bit más significativo. Luego, enmascaro ambos enteros, y si alguno de ellos no tiene ese bit establecido, entonces la suma es segura.

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

mozilla::CheckedInt<T>proporciona matemática de enteros con desbordamiento para el tipo de entero T(utilizando intrínsecos del compilador en clang y gcc según esté disponible). El código es bajo MPL 2.0 y depende de tres ( IntegerTypeTraits.h, Attributes.hy Compiler.h) otros sólo de encabezado no estándar cabeceras Library Plus Mozilla específica maquinaria afirmación . Probablemente desee reemplazar la maquinaria de aserción si importa el código.

La respuesta de MSalter es una buena idea.

Si se requiere el cálculo de enteros (para precisión), pero el punto flotante está disponible, puede 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
    }
}

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 un programa de 64 bits (GCC):

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

Para un programa de 32 bits, uno necesita hacer que el resultado sea de 64 bits y los parámetros de 32 bits.

Una alternativa es utilizar el intrínseco dependiente del compilador para verificar el registro del indicador. La documentación de GCC para el desbordamiento intrínseco se puede encontrar en 6.56 Funciones incorporadas para realizar operaciones aritméticas con verificación de desbordamiento .

#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);

    }
}

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

Depende de para qué lo uses. Al realizar sumas o multiplicaciones largas sin signo (DWORD), la mejor solución es usar ULARGE_INTEGER.

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

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

Para realizar una multiplicación sin signo 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;
}

La forma sencilla de probar el desbordamiento es validar comprobando si el valor actual es menor que el valor anterior. Por ejemplo, suponga que tiene un bucle para imprimir las potencias de 2:

long lng;
int n;
for (n = 0; n < 34; ++n)
{
   lng = pow (2, n);
   printf ("%li\n", lng);
}

Agregar desbordamiento comprobando la forma en que describí los resultados en esto:

long signed lng, lng_prev = 0;
int n;
for (n = 0; n < 34; ++n)
{
    lng = pow (2, n);
    if (lng <= lng_prev)
    {
        printf ("Overflow: %i\n", n);
        /* Do whatever you do in the event of overflow.  */
    }
    printf ("%li\n", lng);
    lng_prev = lng;
}

Funciona tanto para valores sin signo como para valores con signo positivo y negativo.

Por supuesto, si quisiera hacer algo similar para disminuir los valores en lugar de aumentar los valores, voltearía el <=signo para hacerlo >=, suponiendo que el comportamiento del desbordamiento sea el mismo que el del desbordamiento. Honestamente, eso es lo más portátil posible sin acceso al indicador de desbordamiento de una CPU (y eso requeriría un código de ensamblaje en línea, lo que hace que su código no sea portátil en todas las implementaciones de todos modos).