leetcode——Reverse Integer

2019-08-28 本文已影响0人 WinterPrince

前言

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