11

Suppose I have two size_t variables and I need to multiply them and get result as size_t.

size_t first = ...;
size_t second = ...;
size_t result = first * second;

They might overflow so I need to check for that.

The "clean" way would be to first check that multiplication is possible using division:

if( second != 0 && first > ((size_t)-1) / second ) {
   //handle overflow
}
//proceed with computing first * second

The seemingly less "clean" way is to first multiply and then check the result with division:

size_t result = first * second;
if( second != 0 && result / second != first )
   //handle overflow
}

However because unsigned numbers multiplication "safely overflows" by wrapping around zero this works just fine and looks like equivalent to the former code (which first checks, then multiplies).

Are there any potential problems with the second code? Will it always be as good as the first one?

sharptooth
  • 167,383
  • 100
  • 513
  • 979
  • 1
    This question reminded me of [this tweet](https://twitter.com/fugueish/status/637715389519015941) I saw a few days ago. – Borgleader Aug 31 '15 at 12:19
  • It may not be obvious to everyone that `-1` will [always convert to the max unsigned value](http://stackoverflow.com/q/22801069/1708801) – Shafik Yaghmour Aug 31 '15 at 12:20
  • The only thing I can see is in the second example you are unconditionally doing the multiplication so that could be extra overhead. – NathanOliver Aug 31 '15 at 12:23
  • A branch misprediction is probably more expensive than a multiplication these days. – Alan Stokes Aug 31 '15 at 12:31
  • 2
    [How to detect integer overflow in C/C++?](http://stackoverflow.com/q/199333/995714) – phuclv Aug 31 '15 at 12:45

3 Answers3

1

From a mathematical POV, if 

((a*b) mod (2^n)) / b == a

is true for some overflowing values (this implies a and b both not 0), then it´s a problem.
Accoring to Wolfram Alpha, it´s never true for overflows because to get a result, the bitlength
of the result variable n has to be bigger the the required bitlength of a*b (log[2](a*b)).

Code-wise, I can´t think of any problem just now either.

deviantfan
  • 11,268
  • 3
  • 32
  • 49
1

I would say that not only do you need to check the division, but you should also check the remainder too:

if( second != 0 && (result / second != first || (result % second) != 0))

If c=b*a, then there's only one value of c such as c/b=a. Trying to divide any other value by b will not produce a.

However that's not integer math, but real math. Since integer division rounds off, the formula won't technically be true, since, provided that b is at least 2, (c+1)/b would also be a, for some values of c.

Sam Varshavchik
  • 114,536
  • 5
  • 94
  • 148
  • 3
    He's trying to test for an overflow, not a buggy implementation of multiplication. Is there a case where the `%` test is needed? – ugoren Aug 31 '15 at 12:35
1

The first method you point above is definitelly incorrect. Casting a negative number to an unsigned type is incorrect as used above and deals to Undefined Behaviour.

The second method, as the only way a product can be different from the multiplication of two factors is having an overflow in the middle, would be correct, but again, overflow can deal to Undefined behaviour and as such, would be incorrect (You are implicitly thinking that the overflow will result from a multiplication modulo operation, and the result indeed is undefined).

One way to check for possible overflow could be:

if (MAX_UINT / one_of_the_factors < the_other_factor) ...

This is completely defined and allow you to detect the overflow before doing the actual multiplication in a portable way.

Luis Colorado
  • 10,974
  • 1
  • 16
  • 31
  • C++03 Standard 21.3.6 has this definition of `npos`: `static const size_type npos = -1` so I'm not sure this trick causes UB. – sharptooth Sep 02 '15 at 10:35
  • C++03 is not specifically addressed in my response. I tried to be completely portable, as the question was addressed with C, C++, numbers, multiplication tags. Also, `size_t` is not a C++ specific type. What is true is that converting a negative signed integer (whatever the type should be) to an unsigned one is undefined behaviour, either language. C uses `esize_t` to support signedness. – Luis Colorado Sep 02 '15 at 10:42