深度剖析凭什么python中整型不会溢出

阳光穿透心脏的1/2处 2022-12-10 03:41 140阅读 0赞

转载来源：[深度剖析凭什么python中整型不会溢出][python]

## 前言 ##

*本次分析基于 CPython 解释器，python3.x版本*

在python2时代，整型有 `int` 类型和 `long` 长整型，长整型不存在溢出问题，即可以存放任意大小的整数。在python3后，统一使用了长整型。这也是吸引科研人员的一部分了，适合大数据运算，不会溢出，也不会有其他语言那样还分短整型，整型，长整型…因此python就降低其他行业的学习门槛了。

那么，不溢出的整型实现上是否可行呢？

## 不溢出的整型的可行性 ##

尽管在 C 语言中，整型所表示的大小是有范围的，但是 python 代码是保存到文本文件中的，也就是说，python代码中并不是一下子就转化成 C 语言的整型的，我们需要重新定义一种数据结构来表示和存储我们新的“整型”。

怎么来存储呢，既然我们要表示任意大小，那就得用动态的可变长的结构，显然，数组的形式能够胜任:

[longintrepr.h]
    struct _longobject {
        PyObject_VAR_HEAD
        int *ob_digit;
    };

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xOkRIahP-1600850099881)(https://segmentfault.com/img/remote/1460000015284476 “ea1cca01427d4ab8b7fb65d19426fcce.png”)\]

## 长整型的保存形式 ##

长整型在python内部是用一个 `int` 数组( `ob_digit[n]` )保存值的. 待存储的数值的低位信息放于低位下标, 高位信息放于高下标.比如要保存 `123456789` 较大的数字,但我们的int只能保存3位(假设):

ob_digit[0] = 789;
    ob_digit[1] = 456;
    ob_digit[2] = 123;

低索引保存的是地位，那么每个 `int` 元素保存多大的数合适？有同学会认为数组中每个int存放它的上限(2^31 - 1)，这样表示大数时，数组长度更短，更省空间。但是，空间确实是更省了，但操作会代码麻烦，比方大数做乘积操作，由于元素之间存在乘法溢出问题，又得多考虑一种溢出的情况。

怎么来改进呢？在长整型的 `ob_digit` 中元素理论上可以保存的int类型有 `32` 位，但是我们只保存 `15` 位，这样元素之间的乘积就可以只用 `int` 类型保存即可, 结果做位移操作就能得到尾部和进位 `carry` 了，定义位移长度为 `15`：

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

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

有了这种存放方式，在内存空间允许的情况下，我们就可以存放任意大小的数字了。

[python]: https://segmentfault.com/a/1190000015284473