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?

user_1625187 · Answer

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).

user_11333920 · Answer

It seems the problem was bad logic. Since temp is initialised to 0, there is no need for the pop to enter the condition. Thus, it suffices to write if(temp < (INT_MIN)/10 || temp > (INT_MAX)/10).

The final code is as follows,

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

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

   return temp;
}

user_2815227 · Answer

I find showing the Two’s Complement representation on a disc very helpful.

Here is a representation for 4-bit integers. The maximum value is 2^3-1 = 7.

For 32 bit integers, we will see the maximum value is 2^31-1.

When we add 1 to 2^31-1 : Clockwise we move by one and it is clearly -2^31 which is called integer overflow

In your case, the overflow happens when you have reverse of 2^31, when you reverse that you need to get 2^31, but it does not exist and you need to return 0 (as asked in the question instructions)

Ref : https://courses.cs.washington.edu/courses/cse351/17wi/sections/03/CSE351-S03-2cfp_17wi.pdf

C++ understanding integer overflow

3 Answers