C++ understanding integer overflow

Question

After solving some C++ problems from LeetCode I came across to the Reverse Integer and realized I can not really grasp how to deal with integer overflow.

The problem is simple and consists in reversing an integer number (e.g. 123 -> 321). Now, the difficult part is complying with the following limitation:

Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2³¹, 2³¹ − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows

What I did was the following:

int reverse(int x) {
   int temp = 0;
   while(x != 0){
       // pop
       int pop = x%10;
       x /= 10;

       if(temp < (INT_MIN - pop)/10 || temp > (INT_MAX - pop)/10){
          return 0;
       }
       else{
           // push
           temp = temp*10 + pop;
      }
   }

   return temp;
}

Unfortunately, the code does not prevent the overflow. What am I doing wrong?

Answer 1

The sign of pop is implementation-defined (before C++11), and INT_MIN - pop will cause an overflow if it is negative. So let's first reduce the problem to positive integers only:

if (x == INT_MIN)    // INT_MIN cannot be inverted, handle it separately
    return 0;
const int sign = (x < 0) ? -1 : 1;
x *= sign;

The overflow condition is:

10 * temp + pop > INT_MAX

After simple math, we get:

temp > (INT_MAX - pop) / 10

Here pop is always non-negative, so INT_MAX - pop cannot overflow. The final result is sign * temp. Because temp is positive, -temp cannot overflow (it could overflow if temp were negative).