Problem description

Given a 32 – bit signed integer, reverse the order of each digit

Case 1:

Input: 123 Output: 321Copy the code

Example 2:

Input: -123 Output: -321Copy the code

Example 3:

Input: 120 Output: 21Copy the code

Note:

Suppose we use a 32-bit system and can only processRange of integers. When an integer overflow occurs, your program returns 0

Problem of the difficulty

Easy

Their thinking

First of all, this is not a good problem to do in Python, because Python doesn’t behave as expected when faced with negative numbers, for example

>>> -31/10-3.1 >>> -31%10 9Copy the code

With a language like C++, this is what you get

int main() {
	cout << "Minus 3/10 =" << -3/10 << endl; 
	cout << "-3% 10 =" << -3%10 << endl; 
}
输出：
-3 / 10 = 0
-3 % 10 = -3
Copy the code

You can see that the latter is more in line with our expectations.

In addition, the key problem is how to solve the integer overflow, the idea is as follows:

Integer overflow cannot after happened to judge, but only in the event of a spill before judgment, our algorithm is that the original number is divided by 10, the remainder of constantly times ten again, so it can be the original number of “reverse”, we can image the divided by 10 as the original number of moves to the right, and the number of times 10 as a new move to the left, Since we want to determine before overflow, we need to divide the maximum or minimum value of the integer by 10, then compare the result with that value, and return 0 if we find that further operations will overflow.

For a positive number, we know that the maximum is zeroSo if the resultIf it is greater than 214748364 before the next “left shift”, then overflow must occur; The special case isIt is equal to 214748364 before “left shift”. At this time, it is also necessary to determine whether the next remainder exceeds 7. If so, it can also determine that it will overflow.

Similarly, negative numbers can be evaluated in this way, so that we can write a program:

#include <iostream> #include <climits> using namespace std; int integer_reverse(long x) { int result = 0; while (x ! = 0) { int remainder = x % 10; x = x / 10; if (result > INT_MAX/10 || (result == INT_MAX/10 && remainder > 7)) return 0; if (result < INT_MIN/10 || (result == INT_MIN/10 && remainder < -8)) return 0; result = result * 10 + remainder; } return result; }Copy the code

As you can see, the two if statements handle both positive and negative cases respectively, and the condition in the if contains the two overflow cases described earlier.

The original link