Mutliplication overflow test [duplicate]

Question

This question already has answers here:

How do I detect unsigned integer overflow? (30 answers)

Closed 9 years ago.

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.

Answer 1

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

Answer 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!

Answer 3

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

Answer 4

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.