整数反转及问题解析_给出一个32位的有符号整数n,请将该数进行反转(正负符号不变,其余数字反转)。反转

作者：数据灵魂 | 2024-02-05 10:37:31

踩

给出一个32位的有符号整数n,请将该数进行反转(正负符号不变,其余数字反转)。反转

一、算法题

LeetCode中有这样一个算法：


    
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
 
 
示例 1:
    输入: 123
    输出: 321
 
示例 2:
    输入: -123
    输出: -321
 
示例 3:
    输入: 120
    输出: 21
注意:
 
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,  231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

二、算法分析

个人解法

当第一次看到这个算法的时候，其实是不知道该如何做的，自己勉强使用了最笨的办法来实现，大致思路是，首先将int类型的整数变为字符串，然后通过不断的截取字符串来实现整数的反转，反转后的值先用long来接收，然后判断是否溢出了int的最大范围，最后将值再转换成int类型。

高人的解法

直接看图了:

其大致的思路就是通过不断递归整数整除10取余来获取最后一位数字，从而实现整体的整数的反转。

三、算法实现

按照大神的思路，自己来实现的第一版


 
public static int reverse(int x) {
    int res=0;
    while (x!=0){
        res=res*10+x%10;
        x=x/10;
    }
    return res;
}

问题：在程序运行的时候发现，如果入参的值比较大，如int值为-2^31时，会发生题目中所说的整数溢出情况。

所谓的整数溢出就是，整数值超出了int类型的最大范围。具体就是-2^31=-2147483648，当程序遍历到846384741之后，再将最后一位“2”反转的时候，反转后的值应该为-8463847412，此时的值超出了范围，最终的值变成了126087182。那么问题来了，为什么执行846384741*10的操作后结果为126087182？此处先卖一个关子，稍后再解释。

2. 第二版


        
public static int reverse(int x) {
    long res=0;
    while (x!=0){
        res=res*10+x%10;
        x=x/10;
    }
    return ((int) res) == res ? (int)res:0;
}

在程序中首先通过long类型来处理数据，防止整数溢出问题，最后通过long类型和int类型转换来判断是否发生了溢出。

四、遇到的问题

现在回答刚刚的问题“为什么执行846384741*10的操作后结果为126087182？”

这个需要从计算机的原理说起，在计算机中，乘法和除法运算是通过位移运算的到的。而针对我们这次的乘法运算就是通过对被乘数做左移来实现的。举个例子，比如：5*3，在计算机中的实现如下：

将5和3分别转化成二进制，0101和0011
由于乘数3的二进制表示中，只有第0位和第1位是“1”，所以对被乘数分别左移0位和1位，得到的结果为0101和1010
将左移后的数相加，得到1111，转化成十进制就是15

针对本次问题中，846384741*10，转化成二进制为：11001101100011010011000110011011和1010，所以对被乘数左移1位和3位得到110011011000110100110001100110110和11001101100011010011000110011011000，两个二进制值相加的结果为100000000111100000111111000000001110， 由于此时的结果已经超过了int类型的范围，所以计算机将默认截取后32位，即00000000111100000111111000000001110，此时将值转换为十进制后为：126087182

五、参考资料

java int溢出，结果只会保留低32位，高位会抛弃掉：h ttps://blog.csdn.net/u010002184/article/details/86368598
java int溢出总结： https://njucz.github.io/2017/08/16/java-int%E6%BA%A2%E5%87%BA%E6%80%BB%E7%BB%93/
计算机计算乘除法的原理： https://blog.csdn.net/qq_40316686/article/details/78370204

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/数据灵魂/article/detail/60477

整数反转及问题解析_给出一个32位的有符号整数n,请将该数进行反转(正负符号不变,其余数字反转)。 反转

整数反转及问题解析_给出一个32位的有符号整数n,请将该数进行反转(正负符号不变,其余数字反转)。反转