7. Reverse Integer 整数反转

题目

给定一个 32 位有符号整数，将其位数逆转

解析

不需要进行负数转换，难点在于判断溢出

代码1

func reverse(x int) int {
    var x32 int32
    var rst int32
    var overflow bool
    
    x32 = int32(x)
    
    for ; x32 != 0; {
        rem := x32%10
        x32  = x32/10
        rst,overflow = mul10Add(rst, rem)
        if overflow {
            return 0
        }
    }
    return int(rst)
}

func mul10Add(a int32, b int32) (int32, bool) {
    var rst int32
    var overflow bool
    for i:=0;i<10;i++ {
        rst,overflow = add(rst,a)
        if overflow {
            return 0,true
        }
    }
    return add(rst,b)
}

func add(a,b int32) (int32, bool) {
    rst := a + b
    if a > 0 && b > 0 && rst < 0 {
        return 0, true
    }
    if a < 0 && b < 0 && rst > 0 {
        return 0,true
    }
    return rst,false
}

上边这个答案能过，问题在于溢出判断很难看，如果不考虑溢出，对于一个 x 来说

rst = 0
for ; x != 0;
  rem = x%10
  x = x/10
  rst = rst*10+rem

最终 rst 就是结果，如何判断 num *10 + rem 是否溢出，我们知道32位整数的范围是 -2147483648 ~ 2147483647
首先，根据情况分向上溢出和向下溢出
如果 num > 0 只能向上溢出，那么计算 max / 10，那么溢出的情况是 num > max/10 或者 num = max / 10 并且 rem > 7
如果 num <0 只能向下溢出，那么计算 min / 10，溢出的常见是 num < min / 10 或者num = min /10 并且 rem < -8

这样我们就能简化溢出判断。

代码2

func reverse(x int) int {
    x32 := int32(x)
    var rst int32
    for ; x32!=0; {
        rem := x32%10
        x32 = x32/10
        if rst > (1<<31 -1) / 10 || (rst == (1<<31 -1) / 10 && rem > 7) {
            return 0
        }
        if rst < (-1<<31) / 10 || (rst == (-1<<31) / 10 && rem < -8) {
            return 0
        }
        rst = rst*10 + rem
    }
    return int(rst)
}

上边数据具有特殊性，因为我们已知其中一个数字为 10，加法数字不会大于 10,更一般的解法是

func reverse(x int) int {
    x32 := int32(x)
    var rst int32
    for ; x32!=0; {
        rem := x32%10
        x32 = x32/10
        if rst > 0 && (rst > (1<<31 -1) / 10 || rst*10 > (1<<31 -1)-rem) {
            return 0
        }
        if rst < 0 && (rst < (-1<<31) / 10 || rst*10 < -1<<31 - rem) {
            return 0
        }
        rst = rst*10 + rem
    }
    return int(rst)
}