How do I detect unsigned integer multiply overflow?

Question

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++.

Answer 1

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.