本次分析基于 CPython 解释器，python3.x版本
在python2时代，整型有 int 类型和 long 长整型，长整型不存在溢出问题，即可以存放任意大小的整数。在python3后，统一使用了长整型。这也是吸引科研人员的一部分了，适合大数据运算，不会溢出，也不会有其他语言那样还分短整型，整型，长整型...因此python就降低其他行业的学习门槛了。
那么，不溢出的整型实现上是否可行呢？
不溢出的整型的可行性
尽管在 C 语言中，整型所表示的大小是有范围的，但是 python 代码是保存到文本文件中的，也就是说，python代码中并不是一下子就转化成 C 语言的整型的，我们需要重新定义一种数据结构来表示和存储我们新的“整型”。
怎么来存储呢，既然我们要表示任意大小，那就得用动态的可变长的结构，显然，数组的形式能够胜任:
[longintrepr.h]
struct _longobject {
PyObject_VAR_HEAD
int *ob_digit;
};
长整型的保存形式
长整型在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 ,通过与它做位运算 与 的操作就能得到低位数。
有了这种存放方式，在内存空间允许的情况下，我们就可以存放任意大小的数字了。
长整型的运算
加法与乘法运算都可以使用我们小学的竖式计算方法，例如对于加法运算:
| ob_digit[2] | ob_digit[1] | ob_digit[0] | ||
|---|---|---|---|---|
| 加数a | 23 | 934 | 543 | |
| 加数b | + |
学习交流
热门图片
猜你喜欢的新闻
新闻热点  2020-02-16 09:52:44
 2020-02-15 15:53:44
 2020-02-11 22:02:38
 2020-02-11 21:45:12
 2020-02-07 10:36:18
 2020-02-06 12:16:44
疑难解答 |
