在Go中检测有符号整数溢出

Question

我正在构建一个Lisp，如果计算会导致32位整数溢出，我希望它们自动转换为64位整数。同样地，对于64位溢出，也要切换到任意大小的整数。

我的问题是，我不知道检测整数溢出的“正确”方法是什么。

a, b := 2147483647, 2147483647
c := a + b

如何有效地检查 c 是否发生了溢出？

我考虑过始终将值转换为64位进行计算，然后在可能的情况下再次缩小大小，但这似乎对于像基本算术这样作为语言的基础和核心的东西来说过于昂贵且浪费内存。

- d11wtq

---

我认为打包是你最好的选择。语言中没有精确保持加法速度的机制。 - captncraig

我认为在大多数现代系统中，使用64位整数而不是32位整数所增加的额外4个字节几乎可以忽略不计（除了大型数组等特殊情况）。至于运行时自动检测溢出而不需要使用汇编语言，并且如果您的环境没有抛出异常可以捕获，这并不是一件容易的事。在我看来。 - Alderin

仅为计算而转换为64位基本上没有内存影响，因为您每次只保留一定数量的升级值。例如，这就是OpenJDK的Math.multiplyExact(int, int)所做的。 - user2357112

@captncraig 这可以做到零开销（除了代码略丑）。 处理器已经在每次加法运算中免费计算溢出位；你所需要的只是一种告诉编译器你对此感兴趣的方法。现今GCC有 __builtin_add_overflow，并且 if(__builtin_add_overflow(a,b,c)) { ... 可以直接编译成一个 add 和一个 jo 或者其他给定平台的内容。 - hobbs

@d11wtq 说实话，在这里明智的做法是始终使用64位。32位CPU正在迅速消失，而在64位机器上使用64位整数没有CPU成本，并且与系统其他部分的开销相比，内存成本可能微不足道。 - hobbs

在检查溢出时要注意边角情况。例如，在检查乘法溢出时，math.MinInt8 / -1 本身就会导致溢出。 - user539810

Answer 1

例如，要检测加法的32位整数溢出，

package main

import (
    "errors"
    "fmt"
    "math"
)

var ErrOverflow = errors.New("integer overflow")

func Add32(left, right int32) (int32, error) {
    if right > 0 {
        if left > math.MaxInt32-right {
            return 0, ErrOverflow
        }
    } else {
        if left < math.MinInt32-right {
            return 0, ErrOverflow
        }
    }
    return left + right, nil
}
func main() {
    var a, b int32 = 2147483327, 2147483327
    c, err := Add32(a, b)
    if err != nil {
        // handle overflow
        fmt.Println(err, a, b, c)
    }
}

输出:

integer overflow 2147483327 2147483327 0

- peterSO

---

谢谢！我认为我可能有一个更短的解决方案，但不确定是否存在它无法工作的边缘情况：((c < a) != (b < 0))，其中 c := a + b。 - d11wtq

Answer 2

对于32位整数，标准的方法就像你所说的那样，将其转换为64位，然后再缩小尺寸[1]:

package main

func add32(x, y int32) (int32, int32) {
   sum64 := int64(x) + int64(y)
   return x + y, int32(sum64 >> 31)
}

func main() {
   {
      s, c := add32(2147483646, 1)
      println(s == 2147483647, c == 0)
   }
   {
      s, c := add32(2147483647, 1)
      println(s == -2147483648, c == 1)
   }
}

然而，如果您不喜欢这样做，可以使用一些位运算 [2]:

func add32(x, y int32) (int32, int32) {
   sum := x + y
   return sum, x & y | (x | y) &^ sum >> 30
}

1. https://github.com/golang/go/blob/go1.16.3/src/math/bits/bits.go#L368-L373
2. https://github.com/golang/go/blob/go1.16.3/src/math/bits/bits.go#L380-L387

- Zombo