Wie erkenne ich einen vorzeichenlosen Integer-Multiplikationsüberlauf?

Question 1

Ich habe ein Programm in C++ geschrieben, um alle Lösungen von zu finden ein^B = Cwo ein, B und C zusammen alle Ziffern 0-9 genau einmal verwenden. Das Programm hat Werte von durchlaufen ein und Bund es wurde jedes Mal eine Ziffernzählroutine ausgeführt ein, B und ein^B um zu prüfen, ob die Ziffernbedingung erfüllt ist.

Es können jedoch falsche Lösungen erzeugt werden, wenn ein^B überschreitet die ganzzahlige Grenze. Am Ende habe ich dies mit Code wie folgt überprüft:

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

Gibt es eine bessere Möglichkeit, auf Überlauf zu testen? Ich weiß, dass einige Chips ein internes Flag haben, das gesetzt wird, wenn ein Überlauf auftritt, aber ich habe noch nie gesehen, dass darauf über C oder C++ zugegriffen wurde.

Hüten Sie sich davor unterzeichnet int Überlauf ist ein undefiniertes Verhalten in C und C++, und daher müssen Sie es erkennen, ohne es tatsächlich zu verursachen. Informationen zum Signed-Int-Überlauf vor dem Hinzufügen finden Sie unter Vorzeichenüberlauf in C/C++ erkennen.

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.