Python 的整数是怎么设计的，为什么它不会溢出？

楔子

本篇文章来分析一下 Python 整数的实现原理，我们知道 Python 整数是不会溢出的，换句话说它可以计算无穷大的数。只要你的内存足够，它就能计算，但对于 C 来说显然是不行的，C 能保存的整数范围是有限的。

但问题是，Python 的底层又是 C 实现的，那么它是怎么做到整数不溢出的呢？既然想知道答案，那么看一下整数在底层是怎么定义的就行了。

整数的底层结构

Python 整数在底层由 PyLongObject 结构体负责承载，看一下它的定义。

// Include/pytypedefs.h  
typedef struct _longobject PyLongObject;  
  
// Include/cpython/longintrepr.h  
typedef struct _PyLongValue {  
    uintptr_t lv_tag;   
    digit ob_digit[1];  
} _PyLongValue;  
  
struct _longobject {  
    PyObject_HEAD  
    _PyLongValue long_value;  
};

如果将这些定义合在一起，则类似于下面这样：

typedef struct {  
    Py_ssize_t ob_refcnt;  
    PyTypeObject *ob_type;  
    uintptr_t lv_tag;  
    digit ob_digit[1];  
} PyLongObject;

里面的每个字段的含义如下：

• ob_refcnt：对象的引用计数；

• ob_type：对象的类型；

• lv_tag：维护数组 ob_digit 的长度，但 lv_tag 不直接等于数组长度，而是要经过一系列位运算；

• ob_digit：digit 类型的数组；

相信你已经猜到 Python 整数不会溢出的秘密了，因为它内部通过数组来存储整数，所以可以存储无限大的数。因此答案出来了，虽然整数没有我们生活中的那种长度的概念，但它是个变长对象，因为不同的整数占用的内存可能是不一样的。

所以尽管整数不能像字符串、列表那样使用 len 函数计算长度，但它是个变长对象，而 lv_tag 则负责记录数组 ob_digit 的长度。

另外在 3.8 的时候，PyLongObject 是这么定义的。

// 将结构体展开之后，等价于如下  
typedef struct {  
    Py_ssize_t ob_refcnt;   
    PyTypeObject *ob_type;   
    Py_ssize_t ob_size;  
    digit ob_digit[1];   
} PyLongObject;

我们看到数组的长度由 ob_size 字段负责维护，但 3.12 的时候换成了 lv_tag。可能官方也觉得使用 ob_size 不太合适，因为整数不具备长度的概念，所以换了个名字，否则容易和字符串、列表等对象的 ob_size 产生歧义。

探究整数的秘密

接下来的重点就是这个 ob_digit 数组，我们要从它的身上挖掘信息，看看整数是怎么放在里面的，不过首先我们要搞清楚这个 digit 是什么类型。

// Include/cpython/longintrepr.h  
#if PYLONG_BITS_IN_DIGIT == 30  
typedef uint32_t digit;  
#elif PYLONG_BITS_IN_DIGIT == 15  
typedef unsigned short digit;

PYLONG_BITS_IN_DIGIT 是一个宏，这个宏是做什么的我们先不管，总之如果你的机器是 64 位的，那么它会被定义为 30，机器是 32 位的，则会被定义为 15。

而现在的机器基本都是 64 位的，所以 PYLONG_BITS_IN_DIGIT 等于 30。因此 digit 等价于 uint32_t，即 unsigned int，是一个无符号 32 位整型。

因此 ob_digit 是一个无符号 32 位整型数组，至于长度，虽然声明为 1，但其实没有限制，你可以当成任意长度的数组来用，这是 C 语言的一个常见特性。和 Go 不同，C 数组的长度不属于类型信息。至于数组具体多长，取决于存储的整数有多大，显然整数越大，这个数组就越长，占用的空间也就越大。

了解了 ob_digit 数组之后，来分析一下它是怎么存储整数的？

首先抛出一个问题，如果你是 Python 的设计者，要保证整数不会溢出，你会怎么办？我们不妨再把问题简化一下，假设有一个 8 位无符号整数类型，我们知道它能表示的最大数字是 255，但这时候如果我想表示 256，要怎么办？

可能有人会想，那用两个数来存储不就好了，一个存储 255，一个存储 1，然后将这两个数放在数组里面。这个答案虽然有些接近，但其实还有偏差：就是我们并不能简单地按照大小拆分，比如 256 拆分成 255 和 1，要是 265 就拆分成 255 和 10，不能这样拆分，而是要通过二进制的方式，也就是用新的整数来模拟更高的位。

如果感到困惑的话没有关系，我们以 Python 整数的底层存储为例，来详细解释一下这个过程。解释器实现整数也是通过我们上面说的这种方式，但考虑的会更加全面一些。

整数 0

当整数为 0 时，ob_digit 数组就是 [0]，lv_tag 为 1。

整数 1

当整数为 1 时，ob_digit 数组就是 [1]，但 lv_tag 的值却是 8。咦，为啥是 8 呢？ob_digit 明明只有 1 个元素啊。很简单，当整数大于 0 时，lv_tag 等于 ob_digit 数组的长度左移三位。

因为整数 1 大于 0，数组长度为 1，那么 lv_tag 就等于 1 << 3，所以结果为 8。

整数 2 ** 30 - 1