整数反转（Reverse Interger） #

一.题目 #

这个题目是leetcode上的一道算法题，题目如下。

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0. Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

翻译：给一个有符号的32位整数，返回它的数字反转后的整数。如果反转后的数值溢出，即超出了32位整数范围[-2^31, 2^31 - 1]，返回0。限制：不允许存储64位整数。

例如：

Input: x = 123
Output: 321

Input: x = -123
Output: -321

二.分析 #

最近一年我都在从事JavaScript的工作，C++、C#接触少了，所以看到这种题目，突然有一种陌生感。这个算法题目原本就是为强类型语言程序员设计的，如果是没有接触过强类型语言（C++、C#、Java等）的JavaScript程序员看到这种题目，也许题目都看不大懂。

首先解释下一些概念。

signed: 符号，强类型语言中，数值类型都分为有符号和无符号两种，有符号数的二进制最后一位存储的是符号位，在这道题目中你不需要关心二进制的符号位，只需要知道题目表示的是正负整数。
32-bit: int类型是4字节的，一个字节占8位，所以32-bit的整数范围为[-2^31, 2^31 - 1]，即[-2147483648, 2147483647]。

假设有输入1111111119，反转整数为9111111111，结果超出了32-bit整数范围，所以应该返回0。

题目还限制不允许使用64位整数，所以不允许使用long类型（long类型是8个字节，64位）数值。

如果不考虑题目限制，可以很自然的写出如下解法：

// c++，使用了long类型，不符合题意
class Solution {
public:
    int reverse(int x) {
        long result = 0;
        while (x != 0) {
            result = 10 * result + x % 10;
            x /= 10;
        }
        return (result > INT_MAX || result < INT_MIN) ? 0 : res;
    }
};

令我惊讶的是，上面的题目竟然通过了，leetcode并没有检测是否使用了long类型。

三.最佳解法 #

上面的解法使用了long类型数据，显然不符合题意。在网上找到了另一种解法，如下：

class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while (x != 0) {
            if (abs(res) > INT_MAX / 10) return 0;
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
};

与第一种解法很相似，但是没有用到long类型。它用了一种很巧妙的方法，避免了使用long类型。

通过abs(res) > INT_MAX / 10，检测结果是否溢出。为什么可以使用这种方式呢？

首先，输入的整数x也是一个32-bit整数，所以范围应该在[-2147483648, 2147483647]内。分以下两种情况讨论：

x位数等于10位：那么x的第一位只能为1或者2，反转后的值（不包含正负号）为xxxxxxxxx1和xxxxxxxxx2。
x位数小于10位：那么反转后的值肯定也在32-bit范围内，直接返回反转后的值。

当x位数等于10位时，设反转后的值为rx，我们只需要判断abs(rx / 10) > INT_MAX / 10即可判断数值是否溢出，因为rx个位数值只可能为1或者2，不需要判断。

（完）