Best way to detect integer overflow

On assignment C-bootcamp1, we were asked to write a factorial function.
The difficult part is how to detect integer overflow.

Defective idea
After some research with Google, I found a post on StackOverflow.com, which guides me to fault. I can’t find the original post though.

It says, when integer overflow occurs, the result(n * (n-1)) is smaller than n.
Because, int, on a 32 bit machine, is 32bits, the return value is truncated when it needs more bits, namely when it isgreater than 2^32 -1.

int factorial(int n) {
  if (n == 1)
    return 1;
  else if (n <= 0)
    return -1;
  else
  {
    int result = n * factorial(n-1);
    if (result < n)
      return -2; // overflow
    else
      return result;
  }
}

 

This works in some cases but not all.

The best approach:
The best approach is to set the result as a double, and see if the value keeps the same when it is casted to an int.

  • set result as double or long double: so that it has enough bits to hold the real return value.
  • cast it to an int: the value will be truncated if it is more than 32 bits (space of an int), and lose its precision, so be different from the original.

So the right code should look like this:

int factorial(int n) {
  // TODO: Fill in this function
  if (n == 1)
    return 1;
  else if (n <=0)
    return -1;
  else
  {
    long double result = (double)n * factorial(n-1);
    if (result != (int)result) // compare its value with that when it is casted to an int
      return -2; //overflow
    else
      return result;
  }
}

 

Conclusion:
I’m lucky that I did it the defective way and get 2.5 points off, since it fails the prof’s test with ’13’.
I’m glad, and feeling very lucky, because I know this method has defects and so I’ll never commit this fault in my future job(and cause loss and trouble for the company).

Mistakes make me stronger.

Leave a Reply