Python整数加法溢出

Python整数加法溢出的判断

Python解释器里对整数加法溢出的判断源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
// Python解释器是C语言实现的
static PyObject *
int_add(PyIntObject *v, PyIntObject *w)
{
register long a, b, x;
CONVERT_TO_LONG(v, a);
CONVERT_TO_LONG(w, b);
/* casts in the line below avoid undefined behaviour on overflow */
x = (long)((unsigned long)a + b); // 重点是这行
if ((x^a) >= 0 || (x^b) >= 0) // 和这行
return PyInt_FromLong(x);
return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
}

((x^a) >= 0 || (x^b) >= 0)如果是false,就是发生了溢出。这段代码咋看跟溢出没关系,细看还是挺有名堂的。这个if要判断的是符号位。我们知道,整型的最后一个bit如果是0,那么这个数大于等于0;如果是1,这个数小于0。这个表达式的>= 0判断的就是是否最后一个bit是否是0。

^为异或运算:

1
2
3
4
0 ^ 0 == 0
0 ^ 1 == 1
1 ^ 0 == 1
1 ^ 1 == 0

两个bit相同得0,两个bit不同得1。也就是说((x^a) >= 0 || (x^b) >= 0)判断的是x与a的符号位相同或x与b的符号位相同。换而言之,x只要跟a和b任意一个数的符号位相同则为true

一个long能表达的数的范围是有限制的,两个long相加的情况不外乎下面6种:

1
2
3
4
5
6
7
8
9
//  没有溢出的情况
非负数 + 非负数 = 非负数
非负数 + 负数 = 负/非负数
负数 + 非负数 = 负/非负数
负数 + 负数 = 负数

// 溢出的情况
非负数 + 非负数 = 负数
负数 + 负数 = 非负数

可以看到,没有溢出的情况刚好x和a、b其中一个的符号位相同,而溢出的情况x跟a、b的符号位都不同。所以((x^a) >= 0 || (x^b) >= 0)就刚好能判断出来a+b有没有溢出。

非常神奇的实现。

代码中的注释了:casts in the line below avoid undefined behaviour on overflow。在wikipedia上看到的解释是这样的:

Since an arithmetic operation may produce a result larger than the maximum representable value, a potential error condition may result. In the C programming language, signed integer overflow causes undefined behavior, while unsigned integer overflow causes the number to be reduced modulo a power of two, meaning that unsigned integers “wrap around” on overflow.

如果是a和b都是signed long,溢出后结果是不确定的,看编译器的实现。如果a或b是unsigned long(相加时另一个也会转成unsigned long),相加结果再转回long跟上面讨论的6种情况就一样了。


转载来源:

  1. Python判断整数相加溢出
如果文章对您有帮助,感谢您的赞助支持!