How do I detect unsigned integer multiply overflow?

I was writing a program in C++ to find all solutions of a^b = c, where a, b and c together use all the digits 0-9 exactly once. The program looped over values of a and b, and it ran a digit-counting routine each time on a, b and a^b to check if the digits condition was satisfied.

However, spurious solutions can be generated when a^b overflows the integer limit. I ended up checking for this using code like:

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

Is there a better way of testing for overflow? I know that some chips have an internal flag that is set when overflow occurs, but I've never seen it accessed through C or C++.

Beware that signed int overflow is undefined behaviour in C and C++, and thus you have to detect it without actually causing it. For signed int overflow before addition, see Detecting signed overflow in C/C++.

I see you're using unsigned integers. By definition, in C (I don't know about C++), unsigned arithmetic does not overflow ... so, at least for C, your point is moot :)

With signed integers, once there has been overflow, undefined behaviour (UB) has occurred and your program can do anything (for example: render tests inconclusive). 

#include <limits.h>

int a = <something>;
int x = <something>;
a += x;              /* UB */
if (a < 0) {         /* Unreliable test */
  /* ... */
}

To create a conforming program, you need to test for overflow before generating said overflow. The method can be used with unsigned integers too:

// 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 */;

For division (except for the INT_MIN and -1 special case), there isn't any possibility of going over INT_MIN or INT_MAX.

Clang 3.4+ and GCC 5+ offer checked arithmetic builtins. They offer a very fast solution to this problem, especially when compared to bit-testing safety checks.

For the example in OP's question, it would work like this:

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
}

The Clang documentation doesn't specify whether c_test contains the overflowed result if an overflow occurred, but the GCC documentation says that it does. Given that these two like to be __builtin-compatible, it's probably safe to assume that this is how Clang works too.

There is a __builtin for each arithmetic operation that can overflow (addition, subtraction, multiplication), with signed and unsigned variants, for int sizes, long sizes, and long long sizes. The syntax for the name is __builtin_[us](operation)(l?l?)_overflow:

• u for unsigned or s for signed;
• operation is one of add, sub or mul;
• no l suffix means that the operands are ints; one l means long; two ls mean long long.

So for a checked signed long integer addition, it would be __builtin_saddl_overflow. The full list can be found on the Clang documentation page.

GCC 5+ and Clang 3.8+ additionally offer generic builtins that work without specifying the type of the values: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow. These also work on types smaller than int.

The builtins lower to what's best for the platform. On x86, they check the carry, overflow and sign flags.

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.

There is a way to determine whether an operation is likely to overflow, using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge.

For addition, any two operands will result in (at most) one bit more than the largest operand's highest one-bit. For example:

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

For multiplication, any two operands will result in (at most) the sum of the bits of the operands. For example:

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

Similarly, you can estimate the maximum size of the result of a to the power of b like this:

bool exponentiation_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a);
    return (a_bits*b<=32);
}

(Substitute the number of bits for your target integer, of course.)

I'm not sure of the fastest way to determine the position of the highest one-bit in a number, here's a brute-force method:

size_t highestOneBitPosition(uint32_t a) {
    size_t bits=0;
    while (a!=0) {
        ++bits;
        a>>=1;
    };
    return bits;
}

It's not perfect, but that'll give you a good idea whether any two numbers could overflow before you do the operation. I don't know whether it would be faster than simply checking the result the way you suggested, because of the loop in the highestOneBitPosition function, but it might (especially if you knew how many bits were in the operands beforehand).