Pregunta ¿Cómo detectar el desbordamiento de enteros?


Estaba escribiendo un programa en C ++ para encontrar todas las soluciones de unsegundo = do, dónde un, segundo y do juntos usan todos los dígitos 0-9 exactamente una vez. El programa enlazó valores de un y segundo, y ejecutó una rutina de conteo de dígitos cada vez que un, segundo y unsegundo para verificar si se cumplió la condición de los dígitos.

Sin embargo, se pueden generar soluciones falsas cuando unsegundo 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 el desbordamiento, pero nunca lo he visto acceder a través de C o C ++.


512
2017-10-13 22:53


origen


Respuestas:


Ahí es una forma 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 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 al poder de b Me gusta esto:

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 objetivo, 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 ciclo en el highestOneBitPosition función, pero podría (especialmente si sabía cuántos bits había en los operandos de antemano).


159
2017-10-13 23:44



Veo que estás usando enteros sin signo. Por definición,  (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 ha habido desbordamiento, Comportamiento indefinido ha ocurrido y su programa puede hacer cualquier cosa (por ejemplo: las pruebas de rendición no son concluyentes).

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

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

// 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 INT_MIN y -1 caso especial) no hay posibilidad de repasar INT_MIN o INT_MAX.


156
2017-10-03 17:15



Clang 3.4+ y GCC 5+ ofrecemos builtins aritméticos revisados. 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 ocurre un desbordamiento, pero la documentación de GCC dice que sí. Dado que a estos dos les gusta ser __builtin-compatible, probablemente sea seguro suponer que así es como funciona Clang también.

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

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

Entonces, para una adición de entero largo y marcado, sería __builtin_saddl_overflow. La lista completa se puede encontrar en 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 <intrin.h> te permitirá usar addcarry_uNN y subborrow_uNN (donde NN es el número de bits, como addcarry_u8 o 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_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.


111
2018-01-06 18:28



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

49
2017-10-13 23:02



Advertencia: GCC puede optimizar una verificación de desbordamiento al compilar 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 Papel CERT, y esto sería increíblemente tedioso de usar sistemáticamente.

Compilando con -fwrapv resuelve el problema pero deshabilita algunas optimizaciones.

Necesitamos desesperadamente una mejor solución. Creo que el compilador 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 compilador optimizar una verificación de desbordamiento, lo cual es inaceptable en mi opinión.


35
2017-07-25 21:40



sonido metálico ahora admite comprobaciones dinámicas de desbordamiento para enteros con y sin signo. Ver -fsanitize = entero cambiar. Por ahora, es solo un compilador de C ++ con comprobación de desbordamiento dinámico totalmente soportado para fines de depuración.


27
2018-01-28 17:51



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 es llenado por el procesador después de cada operación aritmética entera. 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 <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 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.


20
2017-12-07 13:48



Veo que mucha gente respondió la pregunta sobre el desbordamiento, pero quería abordar su problema original. Dijo que el problema era encontrar unsegundo= c tal que todos los dígitos se usan 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:

  • X0 == 1 (todas las permutaciones de 9, 8, 7, 6, 5, 4, 3, 2 son soluciones)
  • X1 == x (no hay solución posible)
  • 0segundo == 0 (no hay solución posible)
  • 1segundo == 1 (no hay solución posible)
  • unsegundo, 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)

19
2018-03-11 01:57



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 se convierte 0xffffffff y 0x80 se convierte 0x80000000 y finalmente uint16_t se convierte en un uint64_t.

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


18
2017-10-14 01:05



La forma más sencilla es convertir su unsigned longs en unsigned long longs, haz tu multiplicación y compara el resultado con 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 echar un vistazo a la 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 C a menos que active el reventado de desbordamiento de forma específica para el hardware).

Un poco de vergüenza realmente.


16
2017-10-13 22:59