您现在的位置是：网站首页> 编程资料编程资料

详解Python的整数是如何实现的_python_

2023-05-25 331人已围观

简介详解Python的整数是如何实现的_python_

楔子

本次我想聊一聊 Python 的整数，我们知道 Python 的整数是不会溢出的，换句话说，它可以计算无穷大的数，只要你的内存足够，它就能计算。

而 C 显然没有这个特征，C 里面能表示的整数范围是有限的。但问题是，Python 底层又是 C 实现的，那么它是怎么做到整数不溢出的呢？既然想知道答案，那么看一下整数在底层是怎么定义的就行了。

整数的底层实现

Python 整数在底层对应的结构体是 PyLongObject，我们看一下具体的定义，这里的源码版本为最新的 3.11。

// Include/cpython/longintrepr.h struct _longobject {     PyObject_VAR_HEAD     digit ob_digit[1]; }; // Include/pytypedefs.h typedef struct _longobject PyLongObject; // 将两者合起来可以看成 typedef struct {     PyObject_VAR_HEAD     digit ob_digit[1]; } PyLongObject; // 如果把这个PyLongObject 更细致的展开一下 typedef struct {     // 引用计数       Py_ssize_t ob_refcnt;      // 类型     struct _typeobject *ob_type;      // 维护的元素个数     Py_ssize_t ob_size;     // digit 类型的数组，长度为 1      digit ob_digit[1];  } PyLongObject;

别的先不说，就冲里面的 ob_size 我们就可以思考一番。首先 Python 的整数有大小、但应该没有长度的概念吧，那为什么会有一个 ob_size 呢？

从结构体成员来看，这个 ob_size 指的应该就是数组 ob_digit 的长度，而这个 ob_digit 显然只能是用来维护具体的值了。而数组的长度不同，那么对应的整数占用的内存也不同。

所以答案出来了，整数虽然没有我们生活中的那种长度的概念，但它是个变长对象，因为不同的整数占用的内存可能是不一样的。因此这个 ob_size 指的是底层数组的长度，因为整数对应的值在底层是使用数组来存储的。尽管它没有字符串、列表那种长度的概念，或者说无法对整数使用 len 函数，但它是个变长对象。

那么下面的重点就在这个 ob_digit 数组身上了，我们要从它的身上挖掘信息，看看一个整数是怎么放在这个数组里面的。不过首先我们要搞清楚这个 digit 是什么类型，它的定义同样位于 longintrepr.h 中：

// PYLONG_BITS_IN_DIGIT是一个宏 // 至于这个宏是做什么的我们先不管 // 总之，如果机器是 64 位的，那么它会被定义为 30 // 机器是 32 位的，则会被定义为 15 #if PYLONG_BITS_IN_DIGIT == 30 typedef uint32_t digit; // ... #elif PYLONG_BITS_IN_DIGIT == 15 typedef unsigned short digit; // ... #endif

由于现在基本上都是 64 位机器，所以我们只考虑 64 位，显然 PYLONG_BITS_IN_DIGIT 会等于 30。因此 digit 等价于 uint32_t，也就是 unsigned int，所以它是一个无符号 32 位整型。

因此 ob_digit 是一个无符号 32 位整型数组，长度为 1。当然这个数组具体多长则取决于你要存储的整数有多大，不同于 Golang，C 数组的长度不属于类型信息。

虽然定义的时候，声明数组的长度为 1，但你可以把它当成任意长度的数组来用，这是 C 语言中常见的编程技巧。至于长度具体是多少，则取决于你的整数大小。显然整数越大，这个数组就越长，占用的空间也就越大。

搞清楚了 PyLongObject 里面的所有成员，那么下面我们就来分析 ob_digit 是怎么存储整数的，以及 Python 的整数为什么不会溢出。

不过说实话，关于整数不会溢出这个问题，相信很多人已经有答案了。因为底层是使用数组存储的，而数组的长度又没有限制，所以当然不会溢出。另外，还存在一个问题，那就是 digit 是一个无符号 32 位整型，那负数怎么存储呢？别着急，我们会举例说明，将上面的疑问逐一解答。

整数是怎么存储的

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

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

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

整数 0

注意：当表示的整数为 0 时，ob_digit 数组为空，不存储任何值。而 ob_size 为 0，表示这个整数的值为 0，这是一种特殊情况。

整数 1

当存储的值为 1 时，此时 ob_digit 数组就是 [1]，显然 ob_size 的值也是 1，因为它维护的就是 ob_digit 数组的长度。

整数 -1

我们看到 ob_digit 数组没有变化，但是 ob_size 变成了 -1。没错，整数的正负号是通过这里的 ob_size 决定的。ob_digit存储的其实是绝对值，无论整数 n 是多少，-n 和 n 对应的 ob_digit 是完全一致的，但是 ob_size 则互为相反数。所以 ob_size 除了表示数组的长度之外，还可以表示对应整数的正负。

因此我们之前说整数越大，底层的数组就越长。更准确地说是绝对值越大，底层数组就越长。所以 Python 在比较两个整数的大小时，会先比较 ob_size，如果 ob_size 不一样则可以直接比较出大小来。显然 ob_size 越大，对应的整数越大，不管 ob_size 是正是负，都符合这个结论，可以想一下。

整数 2**30 - 1

如果想表示 2的30次方减1，那么也可以使用一个 digit 表示。话虽如此，但为什么突然说这个数字呢？答案是：虽然 digit 是 4 字节、32 位，但是解释器只用 30 个位。

之所以这么做是和加法进位有关系，如果 32 个位全部用来存储其绝对值，那么相加产生进位的时候，可能会溢出。比如 2 ** 32 - 1，此时 32 个位全部占满了，即便它只加上 1，也会溢出。那么为了解决这个问题，就需要先强制转换为 64 位整数再进行运算，从而会影响效率。但如果只用 30 个位的话，那么加法是不会溢出的，或者说相加之后依旧可以用 32 位整数保存。

因为 30 个位最大就是 2的30次方减1，即便两个这样的值相加，结果也是 2的31次方减2。而 32 个位最大能表示的是 2的32次方减1，所以肯定不会溢出的。如果一开始 30 个位就存不下，那么数组中会有两个 digit。

所以虽然将 32 位全部用完，可以只用一个 digit 表示更大的整数，但会面临相加之后一个 digit 存不下的情况，于是只用 30 个位。如果数值大到 30 个位存不下的话，那么就会多使用一个 digit。

这里可能有人发现了，如果是用 31 个位的话，那么相加产生的最大值就是 2**32-2，结果依旧可以使用一个 32 位整型存储啊，那 Python 为啥要牺牲两个位呢？答案是为了乘法运算。

为了方便计算乘法，需要多保留 1 位用于计算溢出。这样当两个整数相乘的时候，可以直接按 digit 计算，并且由于兼顾了"溢出位"，可以把结果直接保存在一个寄存器中，以获得最佳性能。

具体细节就不探究了，只需要知道整数在底层是使用 unsigned int 类型的数组来维护具体的值即可，并且虽然该类型的整数有 32 个位，但解释器只用 30 个位。

然后还记得我们在看 digit 类型的时候，说过一个宏吗？PYLONG_BITS_IN_DIGIT，在 64 位机器上为 30，32 位机器上为 15。相信这个宏表示的是啥你已经清楚了，它代表的就是使用的 digit 的位数。

整数 2**30

问题来了，我们说 digit 只用 30 个位，所以 2 ** 30 - 1 是一个 digit 能存储的最大值。而现在是 2**30，所以数组中就要有两个 digit 了。

我们看到此时就用两个 digit 来存储了，此时的数组里面的元素就是 0 和 1，而且充当高位的放在后面，因为是使用新的 digit 来模拟更高的位。

由于一个 digit 只用 30 位，那么数组中第一个 digit 的最低位就是 1，第二个 digit 的最低位就是 31，第三个 digit 的最低位就是 61，以此类推。

所以如果 ob_digit 为 [a, b, c]，那么对应的整数就为：

如果 ob_digit 不止3个，那么就按照 30 个位往上加，比如 ob_digit 还有第四个元素 d，那么就再加上 d * 2 ** 90 即可。

以上就是 Python 整数的存储奥秘，说白了就是串联多个小整数来表达大整数。并且这些小整数之间的串联方式并不是简单的相加，而是将各自的位组合起来，共同形成一个具有高位的大整数，比如将两个 8 位整数串联起来，表示 16 位整数。

整数占的内存大小是怎么计算的

下面我们再分析一下，一个整数要占用多大的内存。

相信所有人都知道可以使用 sys.getsizeof 计算大小，但是这大小到底是怎么来的，估计会一头雾水。因为 Python 中对象的大小，是根据底层的结构体计算出来的。

由于 ob_refcnt、ob_type、ob_size 这三个是整数所必备的，它们都是 8 字节，加起来 24 字节。所以任何一个整数所占内存都至少 24 字节，至于具体占多少，则取决于 ob_digit 里面的元素都多少个。

因此整数所占内存等于 24 + 4 * ob_size(绝对值)

import sys # 如果是 0 的话, ob_digit 数组为空 # 所以大小就是 24 字节 print(sys.getsizeof(0))  # 24 # 如果是 1 的话, ob_digit 数组有一个元素 # 所以大小是 24 + 4 = 28 字节 print(sys.getsizeof(1))  # 28 # 同理 print(sys.getsizeof(2 ** 30 - 1))  # 28 # 一个 digit 只用30位, 所以最大能表示 2 ** 30 - 1 # 如果是 2 ** 30, 那么就需要两个元素 # 所以大小是 24 + 4 * 2 = 32 字节 print(sys.getsizeof(2 ** 30))  # 32 print(sys.getsizeof(2 ** 60 - 1))  # 32 # 如果是两个 digit，那么能表示的最大整数就是 2 ** 60 - 1 # 因此 2**60 次方需要三个digit，相信下面的不需要解释了 print(sys.getsizeof(1 << 60))  # 36 print(sys.getsizeof((1 << 90) - 1))  # 36 print(sys.getsizeof(1 << 90))  # 40

所以整数的大小是这么计算的，当然不光整数，其它的对象也是如此，计算的都是底层结构体的大小。

另外我们也可以反推一下，如果有一个整数 88888888888，那么它对应的底层数组ob_digit有几个元素呢？每个元素的值又是多少呢？下面来分析一波。

import numpy as np # 假设占了 n 个位 # 由于 n 个位能表达的最大整数是 2**n - 1 a = 88888888888 # 所以只需要将 a+1、再以 2 为底求对数 # 即可算出 n 的大小 print(np.log2(a + 1))  # 36.371284042320475

计算结果表明，如果想要存下这个整数，那么至少需要 37 个位。而 1 个 digit 用 30 个位，很明显，我们需要两个 digit。

如果ob_digit有两个元素，那么对应的整数就等于 ob_digit[0] 加上ob_digit[1]*2**30，于是结果就很好计算了。

a = 88888888888 print(a // 2 ** 30)  # 82 print(a - 82 * 2 ** 30)  # 842059320

所以整数 88888888888 在底层对应的 ob_digit 数组为 [842059320, 82]。我们修改解释器，来验证这一结论。

我们看到结果和我们分析的是一样的，但这种办法有点麻烦。我们可以通过 ctypes 来构造底层的结构体，在 Python 的层面模拟 C 的行为。

from ctypes import * class PyLongObject(Structure):     _fields_ = [         ("ob_refcnt", c_ssize_t),         ("ob_type", c_void_p),         ("ob_size", c_ssize_t),         ("ob_digit", c_uint32 * 2)     ] a = 88888888888 # 基于对象的地址构造 PyLongObject 对象 long_obj = PyLongObject.from_address(id(a)) # 打印结果和我们预期的一样 print(long_obj.ob_digit[0])  # 842059320 print(long_obj.ob_digit[1])  # 82 # 如果我们将 ob_digit[1] 改成 28 # 那么 a 会变成多少呢？ # 很简单，算一下就知道了 long_obj.ob_digit[1] = 28 print(842059320 + 28 * 2 ** 30)  # 30906830392 # 那么a会不会也打印这个结果呢？ # 毫无疑问，肯定会的 print(a)  # 30906830392 # 并且前后a的地址没有发生改变 # 因为我们修改的底层数组

通过打印 ob_digit 存储的值，我们验证了得出的结论，原来 Python 是通过数组的方式来存储的整数，并且数组的类型虽然是无符号 32 位整数，但是只用 30 个位。

当然了，我们还通过修改 ob_digit，然后再打印 a 进行了反向验证，而输出内容也符合我们的预期。并且在这个过程中，a 指向的对象的地址并没有发生改变，也就是说，指向的始终是同一个对象。而内容之所以会变，则因为我们是通过修改 ob_digit 实现的。

因此所谓的可变和不可变，都只是根据 Python 的表现抽象出来的。比如元组不支持本地修改，那么它就是 immutable，列表支持修改，它就是 mutable。但事实上真的如此吗？元组真的不可变吗？我们来打破这个结论。

from ctypes import * class PyTupleObject(Structure):     _fields_ = [         ("ob_refcnt", c_ssize_t),         ("ob_type", c_void_p),         ("ob_size", c_ssize_t),         ("ob_item", py_object * 3)     ] tpl = (1, 2, 3) # 构造 PyTupleObject 实例 tuple_obj = PyTupleObject.from_address(id(tpl)) # 查看长度，len(元组) 本质上就是获取底层的 ob_size # 所以这是一个时间复杂度为 O(1) 的操作 print(len(tpl), tuple_obj.ob_size)  # 3 3 # 注意：重点来了，我们修改元组里的元素 print(f"----- 修改前 -----") print(f"id(tpl): {id(tpl)}, tpl: {tpl}") tuple_obj.ob_item[0] = py_object(3) tuple_obj.ob_item[1] = py_object(2) tuple_obj.ob_item[2] = py_object(1) print(f"----- 修改后 -----") print(f"id(tpl): {id(tpl)}, tpl: {tpl}") """ ----- 修改前 ----- id(tpl): 2465780048640, tpl: (1, 2, 3) ----- 修改后 ----- id(tpl): 2465780048640, tpl: (3, 2, 1) """ # 我们看到前后的地址并没有改变 # 但是元组却发生了改变

因此所谓的 immutable 和 mutable 只是在使用 Python 时，抽象出来的这个一个东西。所以 immutable 类型的对象，本质上也只是解释器没有将该对象的修改接口去暴露出来而已。

比如在 Python 中修改序列对象的某个元素时，会调用 __setitem__，但解释器没有为元组实现这个方法，所以元组是不可变对象；而解释器为列表实现了，所以列表是可变对象。