最近突然涌起兴趣去阅读 CPython 源码，网上也看了不少解析的文章，后来网上看到《Python源码剖析》评价不错，可惜现在已经绝版，只能从豆瓣阅读购买了一本电子书观摩 。

我从网上下载的是最新的 Python 2.7 源码，这本书配套的解说代码是 Python 2.5 的，这是一个遗憾，但是大体上相差不大，刚好昨天遇到一处。

昨天看到 Python int 实现的原理，这里不详细表述，有兴趣的可以去看看书。其中整数加法 (int_add) 的实现，虽然代码只有几行，但是其中隐藏的知识点还是非常多的，花了点时间回顾了一些基础知识，在这里也简单总结下。

以下是 2.5 里面加法的实现，也是书中提供的例子，这里直接引用过来作为参考对比，注释是作者加入的。

static PyObject* int_add(PyIntObject *v, PyIntObject *w)
{
    register long a, b, x;
    CONVERT_TO_LONG(v, a);
    CONVERT_TO_LONG(w, b);
    x = a + b;
    //[1] : 检查加法结果是否溢出
    if ((x^a) >= 0 || (x^b) >= 0)
        return PyInt_FromLong(x);
    return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
}

下面是 2.7 中的代码对比，大体都没有变化：

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);
}

在此之前，先简单介绍下上面的逻辑：
1）首先 int_add 函数是 Python 中 int 加法的实现函数，参数是两个 Python 整数对象，PyIntObject；
2）接着使用预先定义好的宏（不是重点，这里不具体展开），从整数对象中取出 value，这个value就是整数的值，类型是 long；
3）接下来做整数加法，判断是否溢出，如果没有发生溢出，则将新建一个整数对象，最后结果返回；
4）如果加法过程中发生溢出，则使用更长的类型（PyLong_Type）来做这个加法运算；

这个函数的精髓在与加法的处理，不是简单求和返回，可以看出 2.5 和 2.7代码的区别：

// 2.5
x = a + b;

// 2.7
x = (long)((unsigned long)a + b);

为什么 2.7 要搞得怎么复杂，又是转换成 unsigned long 最后又转换为 long，实际上原因是因为一个历史包袱，在C语言的定义中有符号数（signed）的加法溢出是 undefined behavior，所以这里先变成无符号数的加法，如果溢出就是简单做个截断（取模）。注意，无符号数和有符号数运算，有符号数会隐式转换成无符号数。

接下来我们看对溢出额判断，(x^a) >= 0 || (x^b) >= 0，为什么使用异或来判断。这里先梳理下，什么情况下会发生加法溢出:
1）如果两个不同符号的数字相加，不会发生溢出，比如 5 + (-128）；
2）如果两个相同符号的数字相加，可能会发生溢出，比如正正相加溢出后变成负数，负负相加后变成整数；
这里实际上就是利用了这两点来作为判断依据，如果加法运算结果和原来的任意一个数字符号一致就没有溢出，使用异或来判断性能更好。关于溢出的判断还有其他方法，网上也有不少小伙伴提供了更多思路。

这里还有一个隐含的点，在 Python 里整数对象是不可变的，这个要注意，相加之后是返回一个新的对象：

>>> a = 1
>>> id(a)
38821992L
>>> a += 1
>>> id(a)
38821968L

继续看书。

转载请注明转自: 团子的小窝 , 本文固定链接: CPython 源码中整数加法的实现

与

相关的文章