1

How to correctly check if overflow occurs in integer multiplication?

int i = X(), j = Y();
i *= j;

How to check for overflow, given values of i, j and their type? Note that the check must work correctly for both signed and unsigned types. Can assume that both i and j are of the same type. Can also assume that the type is known while writing the code, so different solutions can be provided for signed / unsigned cases (no need for template juggling, if it works in "C", it is a bonus).

EDIT: Answer of @pmg is the correct one. I just couldn't wrap my head around its simplicity for a while so I will share with you here. Suppose we want to check:

i * j > MAX

But we can't really check because i * j would cause overflow and the result would be incorrect (and always less or equal to MAX). So we modify it like this:

i > MAX / j

But this is not quite correct, as in the division, there is some rounding involved. Rather, we want to know the result of this:

i > floor(MAX / j) + float(MAX % j) / j

So we have the division itself, which is implicitly rounded down by the integer arithmetics (the floor is no-op there, merely as an illustration), and we have the remainder of the division which was missing in the previous inequality (which evaluates to less than 1).

Assume that i and j are two numbers at the limit and if any of them increases by 1, an overflow will occur. Assuming none of them is zero (in which case no overflow would occur anyway), both (i + 1) * j and i * (j + 1) are both more than 1 + (i * j). We can therefore safely ignore the roundoff error of the division, which is less than 1.

Alternately, we can reorganize as such:

i - floor(MAX / j) > float(MAX % j) / j

Basically, this tells us that i - floor(MAX / j) must be greater than a number in a [0, 1) interval. That can be written exactly, as:

i - floor(MAX / j) >= 1

Because 1 is just after the interval. We can rewrite as:

i - floor(MAX / j) > 0

Or as:

i > floor(MAX / j)

So we have shown equivalence of the simple test and the floating-point version. It is because the division does not cause significant roundoff error. We can now use the simple test and live happily ever after.

the swine
  • 10,713
  • 7
  • 58
  • 100
  • 2
    Sound like an assignment, did you try anything, do you have any thoughs on the problem? – this Apr 08 '14 at 13:43
  • In a general way it is impossible. If you know on which Microcontroller you will be working there might be a way. – RedX Apr 08 '14 at 13:43
  • 2
    Since it is UB to "overflow" signed multiplication, you need to detect it before it happens. – PlasmaHH Apr 08 '14 at 13:44
  • http://stackoverflow.com/questions/199333/best-way-to-detect-integer-overflow-in-c-c – Arvind Apr 08 '14 at 13:45
  • @PlasmaHH yes, detecting before is imperative. I would not try to detect correctness from the result, modulo arithmetics had taught me better. – the swine Apr 08 '14 at 14:59

4 Answers4

7

You cannot test afterwards. If the multiplication overflows, it triggers Undefined Behaviour which can render tests inconclusive.

You need to test before doing the multiplication

if (INT_MAX / x > y) /* multiplication of x and y will overflow */;
pmg
  • 106,608
  • 13
  • 126
  • 198
  • This is a start, although it misbehaves for `x == 0` and if `x` or `y` is a large negative number. – M.M Apr 08 '14 at 13:58
  • Yes, this is the kind of answer I was expecting, although this does not always work. Checking before is crucial. The nonzeroedness of at least one operand is implied in some cases so it is not such an issue (and it is easily fixed, as if either of operands is zero, no overflow will ever occur). This is probably easily extended to work reliably for unsigned types as `if(y && (x > UINT_MAX / y || (x == UINT_MAX / y && UINT_MAX % y > 0)))`. – the swine Apr 08 '14 at 14:54
  • For unsigned numbers you should use `UINT_MAX` instead. – pmg Apr 08 '14 at 16:00
  • Oh, actually sorry about that, `if(y && UINT_MAX / x > y)` totally works for unsigned numbers. What I proposed in the previous comment would break the test. – the swine Apr 08 '14 at 16:57
2

If your compiler has a type that is at least twice as big as int then you can do this:

long long r = 1LL * x * y;
if ( r > INT_MAX || r < INT_MIN )
    // overflowed...
else
    x = r;

For portability you should STATIC_ASSERT( sizeof(long long) >= 2 * sizeof(int) ); or something similar but more extreme if you're worried about padding bits!

M.M
  • 138,810
  • 21
  • 208
  • 365
  • Well, this is very nice, as it is easy to understand and quite reliable. There is the downside of needing to have twice as large data type for the multiplication. In my case I'm already using 64-bit integer as I expect the values to be large so I would have to have a 128-bit integer for the check. On the other hand, if I had a 128-bit integer, I would use that in the first place and then I would need a 256-bit one for checking, and so on. Nice, but not practical in this particular case. – the swine Apr 08 '14 at 14:49
1

Try this

bool willoverflow(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), 
    size_t b_bits=highestOneBitPosition(b);
    return (a_bits+b_bits<=32);
}
06needhamt
  • 1,555
  • 2
  • 19
  • 38
  • Wow, it never occurred to me that I could use base 2 logarithm. This is tricky with signed numbers though. – the swine Apr 08 '14 at 14:55
0

It is possible to see if overflow occured postfacto by using a division. In the case of unsigned values, the multiplication z=x*y has overflowed if y!=0 and: bool overflow_occured = (y!=0)? z/y!=x : false; (if y did equal zero, no overflow occured). For the case of signed values, it is a little trickier.
if(y!=0){ bool overflow_occured = (y<0 && x=2^31) | (y!=0 && z/y != x); } We need the first part of the expression because the first test will fail if x=-2^31 and y=-1. In this case the multiplication overflows, but the machine may give a result of -2^31. Therefore we test for it seperately.

This is true for 32 bit values. Extending the code to the 64 bit case is left as an exercise for the reader.

Spacemoose
  • 3,856
  • 1
  • 27
  • 48