leetcode——Reverse Integer

前言

leetcode的刷题记录，整理思路和一些理论细节。

Question

给出一个32比特大小的整数，对其逆序。

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

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

题目分析

题目的意思就是将一个4字节的整数逆序。这个整数存储在计算机中的最高位是符号位，后面是有效位。题目要求如果逆序之后的整数溢出了，那么返回0。

思路

Note 1:题目限制了整数大小是4字节的有符号整数，而我们逆序之后的整数有可能会超过题目限制的整数范围，因此在逆序过程中要对整数进行判断，如果它超过了范围，那么返回0。

Note 2: 如何提取出整数的个、十、百、千...位呢？可以使用求余数的方法来得到。即取余和求商交替进行，就可以从低到高依次得到整数各位上的数。之后依次相加即可。

整数溢出

计算机是用二进制来存储整数的。为了存储不同大小的整数，C语言将整数分为了short int ,int,long int,long long int四种类型。其中short类型大小<=int类型大小，int<=long。

又有unsigned，signed标识符用来表示无符号或者有符号。它们能与上述四种类型自由组合。c语言中定义整数时如果省略了上述符号标识符则默认整数为signed。

现代计算机中通常是long long占64位，long占32位，short占16位，int占16位或32位（依计算机的自然字长而定）。

整数在计算机内存中是用二进制来存储的。如果是有符号整数signed，那么存储方法通常为二进制补码（具体依赖于硬件实现，与c语言无关）。对于无符号整数unsigned，使用二进制码来存储。整数常量通常被视为是signed int类型，如果不够则编译器会从小到大依次尝试使用一个更大的类型。如unsigned int，signed long。

整数有可能会超出某个已经定义好的类型的范围。此时会发生“整数溢出”的问题。

无符号整数的溢出

上溢

一个整数通过运算（赋值），超过了它能表示的上限，则会变成一个很小的数。

对于unsigned整数而言，假设int类型占32位，则其最大取值是4294967295，最小取值是0。定义unsigned int i = 4294967295;。如果超出了此范围，例如i+1，则其实际值为0。规律是当达到所能表示的最大值时，unsigned变量从0开始递增。

因为无符号整数没有符号位，最大无符号整数的二进制位必然是全为1的，再加上某个数例如1后，使用二进制加法逢2进1。最终变为了全为0。即十进制的0。相当于重新开始计数。

因此对于无符号整数而言，如果超可以认为它是不会有溢出的，仅仅是重新从0开始计数。

下溢

一个整数通过运算（赋值），低于它能表示的下限，则会变成一个很大的数。

无符号整数最小取值为0，如果将一个负数赋给它，例如unsigned int i = -1;那么按照二进制码的表示方式，其不存在符号位，它会表示成一个较大的数。

有符号整数的溢出

有符号整数是用二进制补码的形式存储的，它的表示是二进制码按位取反然后+1。计算机会根据数的二进制补码表示来计算，如果存在溢出现象，则计算出的值会是一个错误值。

溢出的三种情况

以下来源于整数溢出。
a.有符号整数之间的比较

从汇编中可以看到，当两个有符号整数比较大小时，是将两数作差，若结果为正则显示被减数大，若结果为负则显示减数大。

当两个有符号整数作差时出现上溢或下溢时，比较结果会与事实相反。

例如，short类型的32767与-5比较大小时，由例1可知，在计算机中，short类型的32767-（-5） =-32764<0，从而得出32767<-5的错误结论。

b.有符号整数的运算

当两个有符号整数运算时，有可能发生上溢或者下溢。

c.无符号整数和有符号整数的比较（运算）

当无符号整数和有符号整数进行比较或运算时，会将有符号整数转化成无符号整数之后进行比较或运算，从而导致上溢下溢以及与事实相反的结论。

例如，short类型的-5与unsigned short类型的13比较大小时，-5转化成无符号整数后等于65531>13，与事实相反。

解决方案

int reverse(int x) //从个位开始考虑
{
    int rev = 0;

    while (x)
    {
        int pop = x % 10;  //依次得到个、十、百、千、万...位上的值
        x = x / 10;  

        if (rev > INT_MAX / 10 || rev == INT_MAX/10 && pop > 7)
            return 0;
        if (rev < INT_MIN / 10 || rev == INT_MIN/10 && pop < -8)
            return 0;
        rev = rev * 10 + pop;
    }
    return rev;
}

代码分析

对于代码中判断整数溢出的条件，依据如下：

$INT\_MAX=(INT\_MAX/10)*10+INT\_MAX \% 10$

以下来自于C / C ++和应用程序中的INT_MAX和INT_MIN

大多数时候，在竞争性编程中，需要分配数据类型可以容纳的变量，最大值或最小值，但是记住如此大而精确的数字是一项困难的工作。因此，C 有一些宏来表示这些数字，因此可以直接将这些宏分配给变量，而无需实际输入整数。

INT_MAX是一个宏，指定整数变量不能存储超出此限制的任何值。
INT_MIN指定整数变量不能存储低于此限制的任何值。

INT_MAX和INT_MIN的值可能不同，取决于编译器的具体实现。
以下是编译器中整数的典型值，使用32位存储。

INT_MAX的值为+2147483647。
INT_MIN的值为-2147483648。

因为是对整数 $x$ 中的个十百千万等等位的个数进行循环，有几位就循环几次，所以时间复杂度为 $O(log(x))$ ，每一个 $x$ 大概有 $log_{10}(x)$ 位。空间复杂度为 $O(1)$ 。