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

Question 1

Estaba escribiendo un programa en C++ para encontrar todas las soluciones de a^B = Cdonde a, B y C juntos usen todos los dígitos 0-9 exactamente una vez. El programa recorrió los valores de a y By ejecutó una rutina de conteo de dígitos cada vez en a, B y a^B para comprobar si se cumplió 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

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

cuidado con eso firmado int el desbordamiento es un comportamiento indefinido en C y C++, y por lo tanto tienes que detectarlo sin causarlo realmente. Para el desbordamiento de int firmado antes de la adición, consulte Detección de desbordamiento firmado en C/C++.

Question 2

Starting with C23, the standard header <stdckdint.h> provides the following three function-like macros:

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

where type1, type2 and type3 are any integer type. These functions respectively add, subtract or multiply a and b with arbitrary precision and store the result in *result. If the result cannot be represented exactly by type1, the function returns true (“calculation has overflowed”). (Arbitrary precision is an illusion; the calculations are very fast and almost all hardware available since the early 1990s can do it in just one or two instructions.)

Rewriting OP’s example:

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 contains the potentially-overflowed result of the multiplication in all cases.

Long before C23, GCC 5+ and Clang 3.8+ offer built-ins that work the same way, except that the result pointer is passed last instead of first: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow. These also work on types smaller than 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+ introduced arithmetic-overflow builtins with fixed types, but they are much less flexible and Clang 3.8 has been available for a long time now. Look for __builtin_umull_overflow if you need to use this despite the more convenient newer alternative.

Visual Studio‘s cl.exe doesn’t have direct equivalents. For unsigned additions and subtractions, including <intrin.h> will allow you to use addcarry_uNN and subborrow_uNN (where NN is the number of bits, like addcarry_u8 or subborrow_u64). Their signature is a bit obtuse:

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 is the carry/borrow flag on input, and the return value is the carry/borrow on output. It does not appear to have equivalents for signed operations or multiplications.

Otherwise, Clang for Windows is now production-ready (good enough for Chrome), so that could be an option, too.

Question 3

Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn’t standard.

You could also test for the possibility of overflow before you perform the multiplication:

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

Question 4

Warning: GCC can optimize away an overflow check when compiling with -O2.
The option -Wall will give you a warning in some cases like

if (a + b < a) { /* Deal with overflow */ }

but not in this example:

b = abs(a);
if (b < 0) { /* Deal with overflow */ }

The only safe way is to check for overflow before it occurs, as described in the CERT paper, and this would be incredibly tedious to use systematically.

Compiling with -fwrapv solves the problem, but disables some optimizations.

We desperately need a better solution. I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring. The present situation allows the compiler to optimize away an overflow check, which is unacceptable in my opinion.

Question 5

Clang now supports dynamic overflow checks for both signed and unsigned integers. See the -fsanitize=integer switch. For now, it is the only C++ compiler with fully supported dynamic overflow checking for debug purposes.

¿Ha sido útil esta solución?