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?

You can't use an overflow to fix an overflow. If you check whether something is bigger than INT_MAX, it's never going to be because INT_MAX is, by definition, the biggest. — Silvio Mayolo
– Silvio Mayolo, Commented Jun 15, 2019 at 20:52
Significant edits of questions are problematic notably for code: answers could refer to the old version. Please don't change your code such that answers are invalidated; if you want to fix code, label the versions. — curiousguy
– curiousguy, Commented Jun 15, 2019 at 23:30

Evg · Accepted Answer · 2019-06-16 11:02:52Z

7

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

edited Jun 16, 2019 at 11:02

answered Jun 15, 2019 at 21:15

Evg

26.6k5 gold badges45 silver badges94 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

eduardogfma Over a year ago

Could you elaborate on the following notation const int sign = (x < 0) ? -1 : 1;? What does the ? does? It's my first time seeing such a notation. Does it define -1 for false and 1 for true, is it?

Evg Over a year ago

@eduardogfma, exactly. It's called a ternary conditional operator.

Evg Over a year ago

@eduardogfma, correction: -1 for true, 1 for false. Sign of sign = sign of x.

eduardogfma · Accepted Answer · 2019-06-15 22:09:19Z

0

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

answered Jun 15, 2019 at 22:09

eduardogfma

1034 bronze badges

3 Comments

Evg Over a year ago

1) For negative integers x % 10 can be positive. Its sign is implementation defined, and you can't rely on it being negative. (I suppose your goal is to write correct programs, and not just get the "Success" result on LeetCode.) 2) In general, you need pop in the condition. Consider the case when temp = 214748364 and pop = 8: the condition temp > (INT_MAX) / 10 is false, but temp * 10 + pop overflows. Yes, you can't have 8463847412 as an input, but suppose you work with 64-bit signed integers. You code will cause an overflow for x = 8085774586302733229 (<= INT64_MAX).

eduardogfma Over a year ago

@Evg I appreciate the comment, and of course I am interested in getting correct code. Actually, what I was really hoping to learn was about overflowing in C++, I wasn't that interested in LeetCode, they just have interesting problems. Anyway, could you elaborate on the 1st point? How is it possible for x % 10 to return a positive integer for negative x?

Evg Over a year ago

Let a = -3 and b = 2. What is a % b? The definition is: (a / b) * b + a % b == a. What is a / b? In C++11 the rule is: "the fractional part is discarded", so the value is -1, and (-3) % 2 == -1 for all standard-conforming implementations. But before C++11 there is no such rule, rounding is implementation-defined, so we could have (-3) / 2 == -2. Then we would have (-3) % 2 == 1. I can't name any implementation that would give this result, but you can't rely on what is not in the standard.

mcvkr · Accepted Answer · 2020-12-29 17:50:51Z

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

Collectives™ on Stack Overflow

C++ understanding integer overflow

3 Answers 3

3 Comments

3 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

3 Comments

Comments

Related