探究 Python 整数的加减法，感受大整数的运算哲学与魅力
楔子
本篇文章来探讨一下整数的加减法是怎么做的，因为整数在底层采用数组进行存储，所以它的加减法就不像浮点数那么简单。
在介绍浮点数的时候说过，对于数值型对象，它的类型一定实现了 tp_as_number 字段，该字段指向了 PyNumberMethods 结构体实例。结构体里面的每个字段都是一个函数指针，对应数值型对象的一个操作。
比如 nb_add 负责加法操作，nb_substract 负责减法操作等等，本篇文章就来探讨一下。首先整数支持的操作非常多，这里我们只探讨加减法。
整数加减法运算原理
整数的加法和减法分别由 long_add 和 long_sub 实现，但运算的核心却不在这两个函数上，它们内部会调用另外两个函数。因为数组保存了整数的绝对值，所以 Python 将整数的运算转成了绝对值运算，而底层有两个函数专门用来做这件事情，分别是 x_add 和 x_sub。
-
x_add(a, b), 计算 a 和 b 的绝对值之和；
-
x_sub(a, b), 计算 a 和 b 的绝对值之差；
所以整数相加就可以这么做，假设两个整数 a 和 b 相加：
-
如果 a 和 b 均为负数，那么通过 x_add 计算两者的绝对值之和，然后再取相反数；
-
如果 a 为负数，b 为正数，那么通过 x_sub 计算 b 和 a 的绝对值之差即可；
-
如果 a 为正数，b 为负数，那么通过 x_sub 计算 a 和 b 的绝对值之差即可；
-
如果 a 和 b 均为正数，那么通过 x_add 计算 a 和 b 的绝对值之和即可；
而整数相减也是同理，还是整数 a 和 b，两者相减：
-
如果 a 为正数，b 为负数，那么通过 x_add 计算两者的绝对值之和即可；
-
如果 a 为负数，b 为正数，那么通过 x_add 计算两者的绝对值之和，然后再取相反数；
-
如果 a 和 b 均为正数，那么通过 x_sub 计算 a 和 b 的绝对值之差即可；
-
如果 a 和 b 均为负数，那么通过 x_sub 计算 b 和 a 的绝对值之差即可；
所以相加时，符号相同会调用 x_add、符号不同会调用 x_sub；相减时，符号相同会调用 x_sub、符号不同会调用 x_add。
这就是 Python 的设计，因为绝对值的加减法不用考虑符号的影响，实现更为简单，所以 Python 将整数运算转化成整数的绝对值运算。那么下面我们的重心就在 x_add 和 x_sub 上面了，看看它们是如何对大整数绝对值进行运算的。
虽然大整数运算较为复杂，同时伴随着效率不高，毕竟是基于数组实现的。但底层有一个机制叫做快分支，可以对简单运算的情况提前进行处理，并且命中率也很高。比如在对 a 和 b 计算加减法的时候，底层会先判断数组的长度是否均等于 1，如果是则说明数组中只有一个元素。这样的话，可以直接拿出来转成 C 的整数进行运算，从而将性能损耗降到最低。
只要整数不超过 2 ** 30 - 1，都可以走快分支，显然这可以满足绝大部分场景，因为这个数字已经很大了。至于 x_add 和 x_sub 则属于通用逻辑，而通用也意味着平庸，但如果快分支没有命中，那么就只能走通用逻辑了。
而我们的重点就是要研究 x_add 和 x_sub 的实现，感受大整数运算的魅力。不过在介绍之前，不妨想象一下我们平时将两个整数相加的时候是怎么做的。
从最低位开始进行相加，逢十进一，ob_digit 也是同理。我们可以把数组中的每一个元素看成是一个整体，只不过它不再是逢十进一，而是逢 2**30 进一。
# 数组的每个元素最大能表示 2 ** 30 - 1
# 把元素整体想象成我们生活中加法的个位、十位、百位...
# 然后对应的位相加，逢 2 ** 30 进一
a = [1024, 22]
b = [342, 18]
c = [1024 + 342, 22 + 18] # [1366, 40]
print(
a[0] + a[1] * 2 ** 30
+
b[0] + b[1] * 2 ** 30
==
c[0] + c[1] * 2 ** 30
) # True
所以仍旧是对应的位进行相加，和我们生活中的加法并无本质上的区别。只不过生活中的加法，每一位能表示 0~9，逢十进一；而 Python 底层的加法，因为整数使用数组存储，那么每一个位能表示 0 ~ 2**30-1，逢 2**30 进一。
把 1024、342 想象成个位，把 22、18 想象成十位，并且此时不再是逢十进一，而是逢 2**30 进一。
a = [2 ** 30 - 1, 16]
b = [2 ** 30 - 1, 21]
# 由于 a[0] + b[0] 达到了 2 ** 30，所以要进个 1
# 如果是逢十进一，之后该位要减去十
# 那么逢 2**30 进一，之后显然要减去 2 ** 30
c = [a[0] + b[0] - 2 ** 30,
a[1] + b[1] + 1]
print(
a[0] + a[1] * 2 ** 30
+
b[0] + b[1] * 2 ** 30
==
c[0] + c[1] * 2 ** 30
) # True
还是不难理解的，就是把数组中每一个对应的元素分别相加，逢 2**30 进 1。
然后是绝对值减法，和绝对值加法一样，也可以类比生活中的减法，从低位到高位分别相减。如果某一位相减的时候发现不够了，那么要向高位借一位。比如 27 - 9，由于 7 比 9 小，因此向 2 借一位变成 17，减去 9，得 8。但 2 被借了一位，所以剩下 1，因此结果为 18。
a = [5, 3]
b = [6, 1]
result = []
# 如果计算 a - b，整个过程是怎样的呢？
# 首先是 a[0] - b[0]，由于 a[0] < b[0]
# 所以要向高位借一位，而一位是 2 ** 30
result.append(a[0] + 2 ** 30 - b[0])
# 然后是 a[1] - b[1]
# 由于 a[1] 被借走了一个位，因此要减 1
result.append(a[1] - 1 - b[1])
print(result) # [1073741823, 1]
# 验证一下
print(
(a[0] + a[1] * 2 ** 30)
-
(b[0] + b[1] * 2 ** 30)
) # 2147483647
print(
result[0] + result[1] * 2 ** 30
) # 2147483647
结果没有问题，以上我们就从原理上介绍了大整数的加减法，下面再看一下源码实现。
