前言
本次分析基于 CPython 解释器，python3.x版本
在python2时代，整型有 int 类型和 long 长整型，长整型不存在溢出问题，即可以存放任意大小的整数。在python3后，统一使用了长整型。这也是吸引科研人员的一部分了，适合大数据运算，不会溢出，也不会有其他语言那样还分短整型，整型，长整型...因此python就降低其他行业的学习门槛了。
那么，不溢出的整型实现上是否可行呢？
不溢出的整型的可行性
尽管在 C 语言中，整型所表示的大小是有范围的，但是 python 代码是保存到文本文件中的，也就是说，python代码中并不是一下子就转化成 C 语言的整型的，我们需要重新定义一种数据结构来表示和存储我们新的“整型”。
怎么来存储呢，既然我们要表示任意大小，那就得用动态的可变长的结构，显然，数组的形式能够胜任:
1. `[longintrepr.h]`
2. `struct _longobject {`
3. `PyObject_VAR_HEAD`
4. `int *ob_digit;`
5. `};`
长整型的保存形式
长整型在python内部是用一个 int 数组( ob_digit[n] )保存值的. 待存储的数值的低位信息放于低位下标, 高位信息放于高下标.比如要保存 123456789 较大的数字,但我们的int只能保存3位(假设):
1. `ob_digit[0] = 789;`
2. `ob_digit[1] = 456;`
3. `ob_digit[2] = 123;`
低索引保存的是地位，那么每个 int 元素保存多大的数合适？有同学会认为数组中每个int存放它的上限(2^31 - 1)，这样表示大数时，数组长度更短，更省空间。但是，空间确实是更省了，但操作会代码麻烦，比方大数做乘积操作，由于元素之间存在乘法溢出问题，又得多考虑一种溢出的情况。
怎么来改进呢？在长整型的 ob_digit 中元素理论上可以保存的int类型有 32 位，但是我们只保存 15位，这样元素之间的乘积就可以只用 int 类型保存即可, 对乘积结果做位移操作就能得到尾部和进位 carry了，因此定义位移长度为 15：
1. `#define PyLong_SHIFT 15`
2. `#define PyLong_BASE ((digit)1 << PyLong_SHIFT)`
3. `#define PyLong_MASK ((digit)(PyLong_BASE - 1))`
PyLong\_MASK 也就是 0b111111111111111 ,通过与它做位运算 与 的操作就能得到低位数。
有了这种存放方式，在内存空间允许的情况下，我们就可以存放任意大小的数字了。
长整型的运算
加法与乘法运算都可以使用我们小学的竖式计算方法，例如对于加法运算:
为方便理解，表格展示的是数组中每个元素保存的是 3 位十进制数，计算结果保存在变量z中，那么 z 的数组最多只要 size\_a+1 的空间（两个加数中数组较大的元素个数 + 1），因此对于加法运算，处理过程就是各个对应位置的元素进行加法运算，计算过程就是竖式计算的方式:
1. `[longobject.c]`
2. `static PyLongObject * x_add(PyLongObject *a, PyLongObject *b) {`
3. `int size_a = len(a), size_b = len(b);`
4. `PyLongObject *z;`
5. `int i;`
6. `int carry = 0; // 进位`
7.
8. `// 确保a是两个加数中较大的一个`
9. `if (size_a < size_b) {`
10. `// 交换两个加数`
11. `swap(a, b);`
12. `swap(&size_a, &size_b);`
13. `}`
14.
15. `z = _PyLong_New(size_a + 1); // 申请一个能容纳size_a+1个元素的长整型对象`
16. `for (i = 0; i < size_b; ++i) {`
17. `carry += a->ob_digit[i] + b->ob_digit[i];`
18. `z->ob_digit[i] = carry & PyLong_MASK; // 掩码`
19. `carry >>= PyLong_SHIFT; // 移除低15位, 得到进位`
20. `}`
21. `for (; i < size_a; ++i) { // 单独处理a中高位数字`
22. `carry += a->ob_digit[i];`
23. `z->ob_digit[i] = carry & PyLong_MASK;`
24. `carry >>= PyLong_SHIFT;`
25. `}`
26. `z->ob_digit[i] = carry;`
27. `return long_normalize(z); // 整理元素个数`
28.
29. `}`
这部分的过程就是，先将两个加数中长度较长的作为第一个加数，再为用于保存结果的 z 申请空间，两个加数从数组从低位向高位计算，处理结果的进位，将结果的低 15 位赋值给 z 相应的位置。最后的 long\_normalize(z)是一个整理函数，因为我们 z 申请了 a\_size+1 的空间，但不意味着 z 会全部用到，因此这个函数会做一些调整，去掉多余的空间，数组长度调整至正确的数量。
若不方便理解，附录将给出更利于理解的 python 代码。
竖式计算不是按个位十位来计算的吗，为什么这边用整个元素？
竖式计算方法适用与任何进制的数字，我们可以这样来理解，这是一个 32768 (2的15次方) 进制的，那么就可以把数组索引为 0 的元素当做是 “个位”，索引 1 的元素当做是 “十位”。
乘法运算
乘法运算一样可以用竖式的计算方式，两个乘数相乘，存放结果的 z 的元素个数为 size\_a+size\_b即可：
这里需要主意的是，当乘数 b 用索引 i 的元素进行计算时，结果 z 也是从 i 索引开始保存。先创建 z 并初始化为 0，这 z 进行累加，加法运算则可以利用前面的 x_add 函数：
1. `// 为方便理解，会与cpython中源码部分稍有不同`
2. `static PyLongObject * x_mul(PyLongObject *a, PyLongObject *b)`
3. `{`
4. `int size_a = len(a), size_b = len(b);`
5. `PyLongObject *z = _PyLong_New(size_a + size_b);`
6. `memset(z->ob_digit, 0, len(z) * sizeof(int)); // z 的数组清 0`
7.
8. `for (i = 0; i < size_b; ++i) {`
9. `int carry = 0; // 用一个int保存元素之间的乘法结果`
10. `int f = b->ob_digit[i]; // 当前乘数b的元素`
11.
12. `// 创建一个临时变量，保存当前元素的计算结果，用于累加`
13. `PyLongObject *temp = _PyLong_New(size_a + size_b);`
14. `memset(temp->ob_digit, 0, len(temp) * sizeof(int)); // temp 的数组清 0`
15.
16. `int pz = i; // 存放到临时变量的低位`
17.
18. `for (j = 0; j < size_a; ++j) {`
19. `carry = f * a[j] + carry;`
20. `temp[pz] = carry & PyLong_MASK; // 取低15位`
21. `carry = carry >> PyLong_SHIFT; // 保留进位`
22. `pz ++;`
23. `}`
24. `if (carry){ // 处理进位`
25. `carry += temp[pz];`
26. `temp[pz] = carry & PyLong_MASK;`
27. `carry = carry >> PyLong_SHIFT;`
28. `}`
29. `if (carry){`
30. `temp[pz] += carry & PyLong_MASK;`
31. `}`
32. `temp = long_normalize(temp);`
33. `z = x_add(z, temp);`
34. `}`
35.
36. `return z`
37.
38. `}`
这大致就是乘法的处理过程，竖式乘法的复杂度是n^2，当数字非常大的时候（数组元素个数超过 70 个）时，python会选择性能更好，更高效的 Karatsuba multiplication 乘法运算方式，这种的算法复杂度是 3nlog3≈3n1.585，当然这种计算方法已经不是今天讨论的内容了。有兴趣的小伙伴可以去了解下。
总结
要想支持任意大小的整数运算，首先要找到适合存放整数的方式，本篇介绍了用 int 数组来存放，当然也可以用字符串来存储。找到合适的数据结构后，要重新定义整型的所有运算操作，本篇虽然只介绍了加法和乘法的处理过程，但其实还需要做很多的工作诸如减法，除法，位运算，取模，取余等。
python代码以文本形式存放，因此最后，还需要一个将字符串形式的数字转换成这种整型结构:
1. `[longobject.c]`
2. `PyObject * PyLong_FromString(const char *str, char **pend, int base)`
3. `{`
4. `}`
这部分不是本篇的重点，有兴趣的同学可以看看这个转换的过程，这个过程还是比较繁琐的，因为它还要处理进制问题,能够处理 0xfff3 或者 0b1011 等情况。
参考
1. `https
:
//github.com/python/cpython/blob/master/Objects/longobject.c`
附录
1. `# 例子中的表格中，数组元素最多存放3位整数，因此这边设置1000`
2. `# 对应的取低位与取高位也就变成对 1000 取模和取余操作`
3. `PyLong_SHIFT = 1000`
4. `PyLong_MASK = 999`
5.
6. `# 以15位长度的二进制`
7. `# PyLong_SHIFT = 15`
8. `# PyLong_MASK = (1 << 15) - 1`
9.
10. `def long_normalize(num):`
11. `"""`
12. `去掉多余的空间，调整数组的到正确的长度`
13. `eg: [176, 631, 0, 0] ==> [176, 631]`
14. `:param num:`
15. `:return:`
16. `"""`
17. `end = len(num)`
18. `while end >= 1:`
19. `if num[end - 1] != 0:`
20. `break`
21. `end -= 1`
22.
23. `num = num[:end]`
24. `return num`
25.
26. `def x_add(a, b):`
27. `size_a = len(a)`
28. `size_b = len(b)`
29. `carry = 0`
30.
31. `# 确保 a 是两个加数较大的，较大指的是元素的个数`
32. `if size_a < size_b:`
33. `size_a, size_b = size_b, size_a`
34. `a, b = b, a`
35.
36. `z = [0] * (size_a + 1)`
37. `i = 0`
38. `while i < size_b:`
39. `carry += a[i] + b[i]`
40. `z[i] = carry % PyLong_SHIFT`
41. `carry //= PyLong_SHIFT`
42. `i += 1`
43.
44. `while i < size_a:`
45. `carry += a[i]`
46. `z[i] = carry % PyLong_SHIFT`
47. `carry //= PyLong_SHIFT`
48. `i += 1`
49. `z[i] = carry`
50.
51. `# 去掉多余的空间，数组长度调整至正确的数量`
52. `z = long_normalize(z)`
53.
54. `return z`
55.
56. `def x_mul(a, b):`
57. `size_a = len(a)`
58. `size_b = len(b)`
59. `z = [0] * (size_a + size_b)`
60.
61. `for i in range(size_b):`
62. `carry = 0`
63. `f = b[i]`
64.
65. `# 创建一个临时变量`
66. `temp = [0] * (size_a + size_b)`
67. `pz = i # 元素计算结果从 i 索引开始保存`
68. `for j in range(size_a):`
69. `carry += f * a[j]`
70. `temp[pz] = carry % PyLong_SHIFT`
71. `carry //= PyLong_SHIFT`
72. `pz += 1`
73.
74. `if carry:`
75. `carry += temp[pz]`
76. `temp[pz] = carry % PyLong_SHIFT`
77. `carry //= PyLong_SHIFT`
78. `pz += 1`
79.
80. `if carry:`
81. `temp[pz] += carry % PyLong_SHIFT`
82. `temp = long_normalize(temp)`
83. `z = x_add(z, temp)`
84.
85. `return z`
86.
87. `a = [543, 934, 23]`
88. `b = [632, 454]`
89. `print(x_add(a, b))`
90. `print(x_mul(a, b))`
❈
博 客： https://www.hongweipeng.com/
❈
赞赏作者
Python中文社区作为一个去中心化的全球技术社区，以成为全球20万Python中文开发者的精神部落为愿景，目前覆盖各大主流媒体和协作平台，与阿里、腾讯、百度、微软、亚马逊、开源中国、CSDN等业界知名公司和技术社区建立了广泛的联系，拥有来自十多个国家和地区数万名登记会员，会员来自以公安部、工信部、清华大学、北京大学、北京邮电大学、中国人民银行、中科院、中金、华为、BAT、谷歌、微软等为代表的政府机关、科研单位、金融机构以及海内外知名公司，全平台近20万开发者关注。
▼ 点击下方 阅读原文 ， 免费成为 社区会员