一. 用不溢出的整数

1.1 整数溢出

在计算机中的变量类型存储空间固定，能表示的数值范围有限。常见语言中int类型长度为32位，能表示的整数范围为-2147483648至2147483647。Python中的整数永远不会有溢出的现象。

1.2 实例对象结构

1.2.1 结构定义

int对象在include/longobject.h头文件中定义，

typedef struct _longobject PyLongObject; /* Revealed in longintrepr.h */

在include/longintrepr.h 中具体实现了int对象。

#if PYLONG_BITS_IN_DIGIT == 30
typedef uint32_t digit;
// ...
#elif PYLONG_BITS_IN_DIGIT == 15
typedef unsigned short digit;
// ...
#endif

struct _longobject {
    PyObject_VAR_HEAD
    digit ob_digit[1];
};

int对象是一个变长对象。除了变长对象都具有的公共头部，还有一个digit数组，整数值应该就存储在这个数组里面。

digit就是一个C语言整数，int对象是通过整数数组来实现大整数的。Python提供了两个整数数组版本，一个是 32位的uint32_t，一个是16位的unsigned short，编译Python解析器时可以通过宏定义指定选用的版本。对于范围不大的整数，用16位整数表示即可，用32位有点浪费。

Python中int对象的结构示意图如下，
Alt
如上图，较大的整数被拆成若干部分，保存在ob_digit数组中。在结构体定义中，ob_digit数组长度却固定为1是因为C语言中数组长度不是类型信息，可以根据实际需要为ob_digit数组分配足够的内存，并将其当成长度为n的数组操作。

1.2.2 大整数实现

整数分为正数、负数和0，不同整数在int对象中的存储方式可以总结如下：

整数绝对值根据实际情况分为若干部分，保存于ob_digit数组中
ob_digit数组长度保存于ob_size字段，负整数的ob_size为负
0以ob_size等于0来表示，ob_digit数组为空

整数1073741824( $2^{30}$ )，Python只使用32位整数的后30位(最大可表示 $2^{30}-1$ )，需要另一个整数才能存储，整数数组长度为2。绝对值计算方式如下，
$2^{30}\times1+2^0\times0=1073741824230\times1+1\times0=1073741824$
对于整数-4294967297(负的 $2^{32}+1$ )，ob_size字段为负。绝对值计算方式，
$2^{30}*4+2^0\times1=4294967297230\times4+1\times1=4294967297$

Python只用32位整数的后30位的原因，

如果32位都用来保存绝对值，为保证加法不溢出 (产生进位)，需要先强制转换成64位类型后在进行计算。牺牲最高1位后，加法运算便不担心进位溢出。
牺牲最高2位是为了和16位整数方案统一起来：如果选用16位整数作为数组，Python则只使用其中15位。

1.3 小整数静态对象池

整数对象是不可变对象，整数运算结果是以新对象返回。Python预先将常用的整数对象创建好以备后用，这就是小整数对象池。在objects/longobject.c中实现，

#ifndef NSMALLPOSINTS
#define NSMALLPOSINTS           257
#endif
#ifndef NSMALLNEGINTS
#define NSMALLNEGINTS           5
#endif

static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS]

NSMALLPOSINTS宏规定了对象池正数个数 (从0开始，包括0)，默认257个
NSMALLNEGINTS宏规定了对象池负数个数，默认 5 个
small_ints是一个整数对象数组，保存预先创建好的小整数对象

Python启动后静态创建一个包含262个元素的整数数组并依次初始化为-5到256。结构如下，
Alt
这个范围内的整数使用频率很高，而缓存这些小整数的内存开销相对可控。

二. 类型对象及大整数运算

2.1 整型对象

对象的行为由对象的类型决定。在objects/longobject.c中找到整数类型对象PyLong_Type的定义，

PyTypeObject PyLong_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "int",                                      /* tp_name */
    offsetof(PyLongObject, ob_digit),           /* tp_basicsize */
    sizeof(digit),                              /* tp_itemsize */
    long_dealloc,                               /* tp_dealloc */

    //...

    &long_as_number,                            /* tp_as_number */

    //...

    long_new,                                   /* tp_new */
    PyObject_Del,                               /* tp_free */
};

类型对象中，tp_as_number是一个指向PyNumberMethods结构体的字段。该结构体保存了各种数学运算的函数指针。整数对象所有数学运算的处理函数如下，

static PyNumberMethods long_as_number = {
    (binaryfunc)long_add,       /*nb_add*/
    (binaryfunc)long_sub,       /*nb_subtract*/
    (binaryfunc)long_mul,       /*nb_multiply*/
    long_mod,                   /*nb_remainder*/
    long_divmod,                /*nb_divmod*/
    long_pow,                   /*nb_power*/
    (unaryfunc)long_neg,        /*nb_negative*/
    (unaryfunc)long_long,       /*tp_positive*/
    (unaryfunc)long_abs,        /*tp_absolute*/
    (inquiry)long_bool,         /*tp_bool*/
    (unaryfunc)long_invert,     /*nb_invert*/
    long_lshift,                /*nb_lshift*/
    (binaryfunc)long_rshift,    /*nb_rshift*/
    long_and,                   /*nb_and*/
    long_xor,                   /*nb_xor*/
    long_or,                    /*nb_or*/
    long_long,                  /*nb_int*/
    // ...
};

Alt

2.2 加法运算

objects/longobject.c中long_add函数实现了两个整数对象链表加法，

static PyObject *
long_add(PyLongObject *a, PyLongObject *b)
{
    PyLongObject *z; // 变量z用于临时保存计算结果

    CHECK_BINOP(a, b);
	// 如果两个对象数组长度均不超过1，用MEDIUM_VALUE宏将其转化成C整数进行运算
    if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
        return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b));
    }
    
    if (Py_SIZE(a) < 0) {
        if (Py_SIZE(b) < 0) {
            // 两个整数均为负数，调用x_add 计算两者绝对值之和
            // 再将结果符号设置为负
            z = x_add(a, b);
            if (z != NULL) {
                assert(Py_REFCNT(z) == 1);
                Py_SIZE(z) = -(Py_SIZE(z));
            }
        }
        else
            // 如果a为负数，b为正数，调用x_sub计算b和a的绝对值之差
            z = x_sub(b, a);
    }
    else {
        // 如果a为正数，b为负数，调用x_sub计算a和b的绝对值之差
        if (Py_SIZE(b) < 0)
            z = x_sub(a, b);
        // 如果两个整数均为正数，调用x_add计算两个绝对值之和    
        else
            z = x_add(a, b);
    }
    return (PyObject *)z;
}

long_add函数将整数加法转换成绝对值加法(x_add)以及绝对值减法(x_sub)
Alt
由于绝对值加、减法不用考虑符号对计算结果的影响，实现更为简单，这是Python将整数运算转化成绝对值运算的缘由。

2.3 减法运算

static PyObject * long_sub(PyLongObject *a, PyLongObject *b)
{
    PyLongObject *z;

    CHECK_BINOP(a, b);
	// 如果a、b底层数组长度均不超过1，直接转换成C基本整数类型进行计算
    if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
        return PyLong_FromLong(MEDIUM_VALUE(a) - MEDIUM_VALUE(b));
    }
    if (Py_SIZE(a) < 0) {
        if (Py_SIZE(b) < 0)
            // 如果a、b均为负数，即-(|a|-|b|)
            z = x_sub(a, b);
        else
            // 如果a为负数，b为正数，结果为-(|a|+|b|)
            z = x_add(a, b);
        if (z != NULL) {
            assert(Py_SIZE(z) == 0 || Py_REFCNT(z) == 1);
            Py_SIZE(z) = -(Py_SIZE(z));
        }
    }
    else {
        if (Py_SIZE(b) < 0)
        	// 如果a为正数，b为负数，结果为|a|+|b|
            z = x_add(a, b);
        else
        	// 如果a、b均为正数，结果为|a|-|b|
            z = x_sub(a, b);
    }
    return (PyObject *)z;
}

基本逻辑与加法一样，都是转化为绝对值运算。

2.4 绝对值运算

2.4.1 x_add绝对值加法

绝对值加法的实现源码位于objects/longobject.c，

#define PyLong_SHIFT  15
#define PyLong_BASE ((digit)1 << PyLong_SHIFT)
#define PyLong_MASK ((digit)(PyLong_BASE - 1))

static PyLongObject * x_add(PyLongObject *a, PyLongObject *b)
{
	// 操作数a和b底层数组的长度
    Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
    PyLongObject *z;  // 分别是操作数a和b底层数组的长度
    Py_ssize_t i;	 // 用于遍历底层整数数组
    digit carry = 0; // 用于保存每个字部分运算的进位

    // 如果a数组长度比较小，将a、b交换
    if (size_a < size_b) {
        { PyLongObject *temp = a; a = b; b = temp; }
        { Py_ssize_t size_temp = size_a;
            size_a = size_b;
            size_b = size_temp; }
    }
    z = _PyLong_New(size_a+1); // 创建新整数对象，用于保存计算结果
    if (z == NULL)
        return NULL;
    // 遍历b底层数组，与a对应部分相加并保存到z中,需要注意进位计算
    for (i = 0; i < size_b; ++i) {
        carry += a->ob_digit[i] + b->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    // 遍历a底层数组剩余部分，与进位相加后保存到z中，同样需要注意进位计算
    for (; i < size_a; ++i) {
        carry += a->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    // 将进位写入z底层数组最高位单元中
    z->ob_digit[i] = carry;
    // 将进位写入z底层数组最高位单元中
    return long_normalize(z);
}

PyLong_MASK是 0b111111111111111，通过与它做位运算&的操作就能得到低位数。

Alt

2.4.2 x_sub绝对值减法

static PyLongObject *
x_sub(PyLongObject *a, PyLongObject *b)
{
    Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
    PyLongObject *z;
    Py_ssize_t i;
    int sign = 1;
    digit borrow = 0;

    /* Ensure a is the larger of the two: */
    if (size_a < size_b) {
        sign = -1;
        { PyLongObject *temp = a; a = b; b = temp; }
        { Py_ssize_t size_temp = size_a;
            size_a = size_b;
            size_b = size_temp; }
    }
    else if (size_a == size_b) {
        /* Find highest digit where a and b differ: */
        i = size_a;
        while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
            ;
        if (i < 0)
            return (PyLongObject *)PyLong_FromLong(0);
        if (a->ob_digit[i] < b->ob_digit[i]) {
            sign = -1;
            { PyLongObject *temp = a; a = b; b = temp; }
        }
        size_a = size_b = i+1;
    }
    z = _PyLong_New(size_a);
    if (z == NULL)
        return NULL;
    for (i = 0; i < size_b; ++i) {
        /* The following assumes unsigned arithmetic
           works module 2**N for some N>PyLong_SHIFT. */
        borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
        z->ob_digit[i] = borrow & PyLong_MASK;
        borrow >>= PyLong_SHIFT;
        borrow &= 1; /* Keep only one sign bit */
    }
    for (; i < size_a; ++i) {
        borrow = a->ob_digit[i] - borrow;
        z->ob_digit[i] = borrow & PyLong_MASK;
        borrow >>= PyLong_SHIFT;
        borrow &= 1; /* Keep only one sign bit */
    }
    assert(borrow == 0);
    if (sign < 0) {
        Py_SIZE(z) = -Py_SIZE(z);
    }
    return long_normalize(z);
}