好记性不如烂笔头

0%

判断两个有符号整数相加是否溢出

Posted on Edited on In Disqus:

在Python，默认的整数是long型的，也就是机器字长，32位的最大有符号整数为0x7fffffff，64位最大有符号整数为0x7fffffffffffffff。

而在Python，支持任意大整数的运算，也就是，当我们的long型整数（在Python对象中type为int）溢出的时候，Python会自动将其变成大整数（在Python对象中type为long），也就是和Java中的BigInteger一样，支持任意位数的整数计算，不过更加方便。

我的系统是64位的，最大符号整数为0x7fffffffffffffff，我们来看看两个0x7fffffffffffffff相加会发生什么事情。

我们可以看到c的值已经超越C语言中long能够表示的最大整数了，所以Python将其变成了type为long的类型。那么什么时候需要转换呢？

答案是，当溢出的时候。但是我们怎么知道何时溢出？

我们来看一下Python中对于加法的实现。

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

case BINARY_ADD:
    w = POP();
    v = TOP();
    if (PyInt_CheckExact(v) && PyInt_CheckExact(w)) {
        /* INLINE: int + int */
        register long a, b, i;
        a = PyInt_AS_LONG(v);
        b = PyInt_AS_LONG(w);
        /* cast to avoid undefined behaviour
           on overflow */
        i = (long)((unsigned long)a + b);
        if ((i^a) < 0 && (i^b) < 0)
            goto slow_add;
        x = PyInt_FromLong(i);
    }
    else if (PyString_CheckExact(v) &&
             PyString_CheckExact(w)) {
        x = string_concatenate(v, w, f, next_instr);
        /* string_concatenate consumed the ref to v */
        goto skip_decref_vx;
    }
    else {
      slow_add:
        x = PyNumber_Add(v, w);
    }
    Py_DECREF(v);
  skip_decref_vx:
    Py_DECREF(w);
    SET_TOP(x);
    if (x != NULL) continue;
    break;

可见，当

if ((i^a) < 0 && (i^b) < 0) goto slow_add;

为真的时候就是发生溢出了，所以去到了慢速加法通道。
那我们有

i = a + b

什么时候溢出呢？在a、b都为正数的时候和为负数（正正负）或者a、b都为负数的时候和为正数（负负正）。
所以当 (i^a) < 0 && (i^b) < 0 为 true 的时候溢出了，因为它们的最高位都符合正正负或负负正。