专栏首页Python七号Python 内部是如何实现整数相加不溢出的?

Python 内部是如何实现整数相加不溢出的?

说实话昨天的文章划水了,阅读量就是最好的证明。这里读者的水平还是很高的,一看就看出了我的偷懒,标题 Python 的整数有边界么?肯定没有啊,于是就不打开看了。不过今天,我想接着昨天的话题,聊一聊 Python 是如何实现整数相加而不溢出的?

1、如何表示一个整数

要想了解这个,那就需要看 Python 的源代码[1],Python中的整数底层对应的结构体是PyLongObject,它位于 longobject.h[2] 中。

逐步展开如下:

//longobject.h
typedef struct _longobject PyLongObject; /* Revealed in longintrepr.h */
 
//longintrepr.h
struct _longobject {
    PyObject_VAR_HEAD
    digit ob_digit[1];
};
 
//合起来可以看成
typedef struct {
    PyObject_VAR_HEAD
    digit ob_digit[1];
} PyLongObject;

再把宏定义 PyObject_VAR_HEAD 展开:

typedef struct {
    PyObject_HEAD
    int ob_size;
    digit ob_digit[1];
} PyLongObject;

再把宏定义 PyObject_HEAD 展开,结构体中的变量我已经作了注释:

typedef struct {
    int ob_refcnt;    //引用计数
    struct _typeobject *ob_type; //变量类型
    int ob_size;       //用来指明变长对象中一共容纳了多少个元素
    digit ob_digit[1]; //digit类型的数组,长度为1
} PyLongObject;

这里面的 ob_size 用来指明变长对象中一共容纳了多少个元素,也就是 ob_digit 数组的长度,而这个 ob_digit 数组显然只能是用来维护具体的值。

到这里已经很明显了,Python 将大整数切割后存在 ob_digit,这个数组的长度是可变的,数据越大,数组越长,只要内存够用,存多大的数都可以。

那么下面的重点就在这个 ob_digit 数组了,我们看看 Python 中整数对应的值,比如 256,是怎么放在这个数组里面的。不过首先我们要看看这个digit 是个什么类型,它同样定义在 longintrepr.h 中

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

PYLONG_BITS_IN_DIGIT 是一个宏,如果你的机器是 64 位的,那么它会被定义为 30,32 位机器则会被定义为 15。

而我们的机器现在基本上都是 64 位的,所以 PYLONG_BITS_IN_DIGIT会等于 30,因为 digit 等价于 uint32_t(unsigned int),所以它是一个无符号 32 位整型。

所以 ob_digit 这个数组是一个无符号 32 位整型数组,长度为 1。当然这个数组具体多长则取决于你要存储的 Python 整数有多大,因为 C 中数组的长度不属于类型信息,你可以看成是长度 n,而这个 n 是多少要取决于你的整数大小。显然整数越大,这个数组就越长,那么占用空间就越大。

为了说明 256 是如何存放在 ob_digit 里的,我们来简化下,这里假如 ob_digit 这个数组是一个无符号 8 位整型数组,8 位二进制,最大只能表示 255,我们要表示 256,那就只能再申请一个 8 位,也许你认为再申请一个 8 位来表示 1,其实不是的,是使用一个新的 8 位整数来模拟更高的位,如下所示:

255 = [255]
256 = [1,1]

256 = [1,1] 的形式也不是真实情况,为了你理解,先这样写,它表达的意思就是 256 = 1 + 1 * (2^8 - 1) = 1 + 1 * 255 = 256。

也就是说 ob_digit 表示 x 进制数,ob_digit[0] 是低位,ob_digit[1] 是高位,具体 x 是多少,取决于 ob_digit 的类型,这里 8 位,就是 255 进制。

刚才提到 256 = [1,1] 的形式也不是真实情况,因为 PyLongObject 不仅仅是为了存储大整数,也需要参与运算,具体怎么运算呢,那就是 ob_digit 逐位相加即可。

既然是相加,即又可能溢出,比如 [255 , 1] + [255, 1] = [510,2]

这里的 510 就超出了 8 位,为了简化处理,只要我们不用满 8 位,就不会溢出,也就是说,比如说只用 7 位,那最大也就是 [127,...] + [127,...] = [254,...] 也就不会溢出了。

到这里,你会明白,为什么 digit 虽然是无符号 32 位整数,却只使用 30 位了吧:

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

聪明的你,可能会问,31 位就可以保证不溢出,为啥牺牲两位,用 30 位,答案我也不知道,可能是因为 64 是 32 的两倍, 30 也是 15 的两倍,这样看起来更舒服吧。

那如何表示负数呢,其实负数的话,就是 ob_size 变成了负的,其他没变。整数的正负号是通过这里的 ob_size 决定的。ob_digit 存储的其实是绝对值,无论 n 取多少,-n 和 n 对应的 ob_digit 是完全一致的,但是ob_size 则互为相反数。所以 ob_size 除了表示数组的长度之外,还可以表示对应整数的正负。

所以 Python 在比较两个整型的大小时,会先比较 ob_size,如果 ob_size 不一样则可以直接比较出大小来。

总结一下,就是当 PYLONG_BITS_IN_DIGIT == 30 的时候,整数 = ob_digit[0] + ob_digit[1] * 2 ** 30 + ob_digit[2] * 2 ** 60 + ...

2、整数占用内存大小

理解了这一点,我们再看一下这个结构体:

typedef struct {
    int ob_refcnt;    //引用计数
    struct _typeobject *ob_type; //变量类型
    int ob_size;       //用来指明变长对象中一共容纳了多少个元素
    digit ob_digit[1]; //digit类型的数组,长度为1
} PyLongObject;

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

现在的你不难理解以下结果:

3、整数池

此外 Python 中的整数属于不可变对象,运算之后会创建新的对象:

>>> a = 300
>>> id(a)
140220663619152
>>> a += 1
>>> id(a)
140220663619408
>>>

这样就势必会有性能缺陷,因为程序运行时会有对象的创建和销毁,就是涉及内存的申请和垃圾回收,一个常用的手段就是使用对象池,将频率高的整数预先创建好,而且都是单例模式,需要使用时直接返回。

小整数对象池的实现位于 pycore_interp.h[3] 中:

验证一下:

>>> a = -6
>>> b = -6
>>> a is b
False
>>> a = -5
>>> b = -5
>>> a is b
True
>>> a = 256
>>> b = 256
>>> a is b
True
>>> a = 257
>>> b = 257
>>> a is b
False
>>>

不同的版本可能会不同,我这里 Python3.8,区间为 [-5,257)。

4、整数加减法

有了前面的铺垫,现在我们来看下 Python 中大整数是如何相加的,源代码 longobject.c : long_add 函数[4]

可以看到 long_add 根据 ob_size 的正或负来调用 x_add 或 x_sub。

现在看一下 x_add 的源代码:

可以看到,Python 大整数的相加就是底层数组的相加,当然还会涉及到进位等操作:

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

x_sub 的源代码:

4、整数乘法

Python 整数乘法使用的是 Karatsuba multiplication[5] 算法进行的大数乘法,感兴趣的可以研究一下。

最后的话

源码之下无秘密,看源码会比较辛苦,却可以学到精髓和本质,本文通过源码逐层展开,带你了解了下 Python 整数对象的实现、整数内存大小的计算,整数池,整数加减法源码,相信你已经知道了 Python 是如何实现整数想加而不溢出的。如果有收获,还请点在、点赞、转发,感谢一路的支持和陪伴。

都看到这里了,你确定不关注一下:

留言讨论

参考资料

[1]

源代码: https://github.com/python/cpython

[2]

longobject.h: https://github.com/python/cpython/blob/main/Include/longobject.h

[3]

pycore_interp.h: https://github.com/python/cpython/blob/main/Include/internal/pycore_interp.h

[4]

longobject.c : long_add 函数: https://github.com/python/cpython/blob/main/Objects/longobject.c

[5]

Karatsuba multiplication: https://en.wikipedia.org/wiki/Karatsuba_algorithm

本文分享自微信公众号 - Python七号(PythonSeven),作者:somenzz

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-08-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python 的整数与 Numpy 的数据溢出

    看了图,我第一感觉就是数据溢出了。数据超出能表示的最大值,就会出现奇奇怪怪的结果。

    Python猫
  • 闯缸鱼:看懂python如何实现整数加和,再决定是否自学编程

    玩鱼缸的新手都知道有一种鱼叫“闯缸鱼”,皮实好养,帮助新手判断鱼缸环境是否准备好。这篇笔记,最初用来解答一个编程新手的疑问,后来我发现,整理一下也可当做有兴趣自...

    刘娟娟PRESSone
  • Python 的算术运算符

    所谓算术运算,是指初等数学中常见的计算,如加、减、乘、除、乘方等。在数学上,每种计算都使用规定的符号实现,形式上简洁明了,Python 语言也继承了此光荣传统。...

    老齐
  • 基于 CPython 解释器,为你深度解

    在python2时代,整型有 int 类型和 long 长整型,长整型不存在溢出问题,即可以存放任意大小的整数。在python3后,统一使用了长整型。这也是吸引...

    py3study
  • 深度剖析为什么 Python 中整型不会溢出?

    花下猫语:前不久,我应读者提问而写了一篇《Python 的整数与 Numpy 的数据溢出》,简要介绍过 Python 中的整数表示法与数据溢出问题。那篇文章的猎...

    Python猫
  • 3 Python 基础: Python函数及递归函数知识点梳理

    函数的英文是function,所以,通俗地来讲,函数就是功能的意思。函数是用来封装特定功能的,比如,在Python里面,len()是一个函数,len()这个函数...

    小Gy
  • 深度剖析为什么Python中整型不会溢出

    在python2时代,整型有 int 类型和 long 长整型,长整型不存在溢出问题,即可以存放任意大小的整数。在python3后,统一使用了长整型。这也是吸引...

    Python中文社区
  • 007. 整数反转 | Leetcode题解

    假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为[−231, 231− 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

    苏南
  • 3 Python 基础: Python函数及递归函数知识点梳理

    函数的英文是function,所以,通俗地来讲,函数就是功能的意思。函数是用来封装特定功能的,比如,在Python里面,len()是一个函数,len()这个函数...

    小Gy
  • Python 的整数

    就返回了所输入的数字,这说明 Python 解释器接受了所输入的那个数字,并且认识了它。

    老齐
  • Python 数字类型,稍不注意就歪。

    这里的“对象”不是你的对象,是编程语言的对象(Object),你可以把它理解为一块内存,保存的是它们所代表的值。

    编程文青李狗蛋
  • LeetCode小白菜笔记2:Reverse Integer

    LeetCode小白菜笔记[2]:Reverse Integer7. Reverse Integer [Easy] 题目: Given a 32-bit sig...

    企鹅号小编
  • 【Python】04、python基础数

              就是说不能再重新赋值,很像shell中的只读变量,python中不存在常量

    py3study
  • C语言 | C++ 基础栈溢出及保护机制

    如果你学的第一门程序语言是C语言,那么下面这段程序很可能是你写出来的第一个有完整的 “输入---处理---输出” 流程的程序:

    小林C语言
  • Python令人难以置信的增长

    群内不定时分享干货,包括最新的python企业案例学习资料和零基础入门教程,欢迎初学和进阶中的小伙伴入群学习交流 我们最近探讨了富裕国家(世界银行定义为高收入国...

    企鹅号小编
  • 基本算法之-递归

    俗话说,大事化小。递归算法也是分治的思想。我国古代的愚公移山,就是这种递归。子又生孙,孙又生子。

    赵云龙龙
  • 爬虫问题一:栈溢出(stack overflow)问题解决方案

    Fatal Python error: Cannot recover from stack overflow

    K同学啊
  • jupyter notebook 使用过程中python莫名崩溃的原因及解决方式

    最近在使用 Python notebook时老是出现python崩溃的现象,如下图,诱发的原因是“KERNELBASE.dll”,异常代码报“40000015”...

    砸漏
  • 栈上内存溢出漏洞利用之Return Address

    程序员大多都碰到过栈上内存溢出,最常见的结果是导致程序Crash,有时候也有可能因为覆盖栈上的信息导致程序执行一些意想不到的逻辑,这种情况往往比起Crash更加...

    河边一枝柳

扫码关注云+社区

领取腾讯云代金券