詳解Python的整數(shù)是如何實(shí)現(xiàn)的

更新時間：2022年11月04日 10:01:07 作者：古明地覺

本文我們來聊一聊Python的整數(shù)，我們知道Python的整數(shù)是不會溢出的，換句話說，它可以計算無窮大的數(shù)，只要你的內(nèi)存足夠，它就能計算。但問題是，Python底層又是C實(shí)現(xiàn)的，那么它是怎么做到整數(shù)不溢出的呢？本文就來詳細(xì)說說

楔子

本次我想聊一聊 Python 的整數(shù)，我們知道 Python 的整數(shù)是不會溢出的，換句話說，它可以計算無窮大的數(shù)，只要你的內(nèi)存足夠，它就能計算。

而 C 顯然沒有這個特征，C 里面能表示的整數(shù)范圍是有限的。但問題是，Python 底層又是 C 實(shí)現(xiàn)的，那么它是怎么做到整數(shù)不溢出的呢？既然想知道答案，那么看一下整數(shù)在底層是怎么定義的就行了。

整數(shù)的底層實(shí)現(xiàn)

Python 整數(shù)在底層對應(yīng)的結(jié)構(gòu)體是 PyLongObject，我們看一下具體的定義，這里的源碼版本為最新的 3.11。

//?Include/cpython/longintrepr.h
struct?_longobject?{
????PyObject_VAR_HEAD
????digit?ob_digit[1];
};

//?Include/pytypedefs.h
typedef?struct?_longobject?PyLongObject;

//?將兩者合起來可以看成
typedef?struct?{
????PyObject_VAR_HEAD
????digit?ob_digit[1];
}?PyLongObject;

//?如果把這個PyLongObject?更細(xì)致的展開一下
typedef?struct?{
????//?引用計數(shù)??
????Py_ssize_t?ob_refcnt;?
????//?類型
????struct?_typeobject?*ob_type;?
????//?維護(hù)的元素個數(shù)
????Py_ssize_t?ob_size;
????//?digit?類型的數(shù)組，長度為?1?
????digit?ob_digit[1];?
}?PyLongObject;

別的先不說，就沖里面的 ob_size 我們就可以思考一番。首先 Python 的整數(shù)有大小、但應(yīng)該沒有長度的概念吧，那為什么會有一個 ob_size 呢？

從結(jié)構(gòu)體成員來看，這個 ob_size 指的應(yīng)該就是數(shù)組 ob_digit 的長度，而這個 ob_digit 顯然只能是用來維護(hù)具體的值了。而數(shù)組的長度不同，那么對應(yīng)的整數(shù)占用的內(nèi)存也不同。

所以答案出來了，整數(shù)雖然沒有我們生活中的那種長度的概念，但它是個變長對象，因?yàn)椴煌恼麛?shù)占用的內(nèi)存可能是不一樣的。因此這個 ob_size 指的是底層數(shù)組的長度，因?yàn)檎麛?shù)對應(yīng)的值在底層是使用數(shù)組來存儲的。盡管它沒有字符串、列表那種長度的概念，或者說無法對整數(shù)使用 len 函數(shù)，但它是個變長對象。

那么下面的重點(diǎn)就在這個 ob_digit 數(shù)組身上了，我們要從它的身上挖掘信息，看看一個整數(shù)是怎么放在這個數(shù)組里面的。不過首先我們要搞清楚這個 digit 是什么類型，它的定義同樣位于 longintrepr.h 中：

//?PYLONG_BITS_IN_DIGIT是一個宏
//?至于這個宏是做什么的我們先不管
//?總之，如果機(jī)器是?64?位的，那么它會被定義為?30
//?機(jī)器是?32?位的，則會被定義為?15
#if?PYLONG_BITS_IN_DIGIT?==?30
typedef?uint32_t?digit;
//?...
#elif?PYLONG_BITS_IN_DIGIT?==?15
typedef?unsigned?short?digit;
//?...
#endif

由于現(xiàn)在基本上都是 64 位機(jī)器，所以我們只考慮 64 位，顯然 PYLONG_BITS_IN_DIGIT 會等于 30。因此 digit 等價于 uint32_t，也就是 unsigned int，所以它是一個無符號 32 位整型。

因此 ob_digit 是一個無符號 32 位整型數(shù)組，長度為 1。當(dāng)然這個數(shù)組具體多長則取決于你要存儲的整數(shù)有多大，不同于 Golang，C 數(shù)組的長度不屬于類型信息。

雖然定義的時候，聲明數(shù)組的長度為 1，但你可以把它當(dāng)成任意長度的數(shù)組來用，這是 C 語言中常見的編程技巧。至于長度具體是多少，則取決于你的整數(shù)大小。顯然整數(shù)越大，這個數(shù)組就越長，占用的空間也就越大。

搞清楚了 PyLongObject 里面的所有成員，那么下面我們就來分析 ob_digit 是怎么存儲整數(shù)的，以及 Python 的整數(shù)為什么不會溢出。

不過說實(shí)話，關(guān)于整數(shù)不會溢出這個問題，相信很多人已經(jīng)有答案了。因?yàn)榈讓邮鞘褂脭?shù)組存儲的，而數(shù)組的長度又沒有限制，所以當(dāng)然不會溢出。另外，還存在一個問題，那就是 digit 是一個無符號 32 位整型，那負(fù)數(shù)怎么存儲呢？別著急，我們會舉例說明，將上面的疑問逐一解答。

整數(shù)是怎么存儲的

首先拋出一個問題，如果你是 Python 的設(shè)計者，要保證整數(shù)不會溢出，你會怎么辦？我們把問題簡化一下，假設(shè)有一個 8 位的無符號整數(shù)類型，我們知道它能表示的最大數(shù)字是 255，但這時候如果我想表示 256，要怎么辦？

可能有人會想，那用兩個數(shù)來存儲不就好了。一個存儲 255，一個存儲 1，將這兩個數(shù)放在數(shù)組里面。這個答案的話，雖然有些接近，但其實(shí)還有偏差：那就是我們并不能簡單地按照大小拆分，比如 256 拆分成 255 和 1，要是 265 就拆分成 255 和 10，不能這樣拆分。正確的做法是通過二進(jìn)制的方式，也就是用新的整數(shù)來模擬更高的位。

如果感到困惑的話沒有關(guān)系，我們就以 Python 整數(shù)的底層存儲為例，來詳細(xì)解釋一下這個過程。Python 底層也是通過我們上面說的這種方式，但是考慮的會更加全面一些。

整數(shù) 0

注意：當(dāng)表示的整數(shù)為 0 時，ob_digit 數(shù)組為空，不存儲任何值。而 ob_size 為 0，表示這個整數(shù)的值為 0，這是一種特殊情況。

整數(shù) 1

當(dāng)存儲的值為 1 時，此時 ob_digit 數(shù)組就是 [1]，顯然 ob_size 的值也是 1，因?yàn)樗S護(hù)的就是 ob_digit 數(shù)組的長度。

整數(shù) -1

我們看到 ob_digit 數(shù)組沒有變化，但是 ob_size 變成了 -1。沒錯，整數(shù)的正負(fù)號是通過這里的 ob_size 決定的。ob_digit存儲的其實(shí)是絕對值，無論整數(shù) n 是多少，-n 和 n 對應(yīng)的 ob_digit 是完全一致的，但是 ob_size 則互為相反數(shù)。所以 ob_size 除了表示數(shù)組的長度之外，還可以表示對應(yīng)整數(shù)的正負(fù)。

因此我們之前說整數(shù)越大，底層的數(shù)組就越長。更準(zhǔn)確地說是絕對值越大，底層數(shù)組就越長。所以 Python 在比較兩個整數(shù)的大小時，會先比較 ob_size，如果 ob_size 不一樣則可以直接比較出大小來。顯然 ob_size 越大，對應(yīng)的整數(shù)越大，不管 ob_size 是正是負(fù)，都符合這個結(jié)論，可以想一下。

整數(shù) 2**30 - 1

如果想表示 2的30次方減1，那么也可以使用一個 digit 表示。話雖如此，但為什么突然說這個數(shù)字呢？答案是：雖然 digit 是 4 字節(jié)、32 位，但是解釋器只用 30 個位。

之所以這么做是和加法進(jìn)位有關(guān)系，如果 32 個位全部用來存儲其絕對值，那么相加產(chǎn)生進(jìn)位的時候，可能會溢出。比如 2 ** 32 - 1，此時 32 個位全部占滿了，即便它只加上 1，也會溢出。那么為了解決這個問題，就需要先強(qiáng)制轉(zhuǎn)換為 64 位整數(shù)再進(jìn)行運(yùn)算，從而會影響效率。但如果只用 30 個位的話，那么加法是不會溢出的，或者說相加之后依舊可以用 32 位整數(shù)保存。

因?yàn)?30 個位最大就是 2的30次方減1，即便兩個這樣的值相加，結(jié)果也是 2的31次方減2。而 32 個位最大能表示的是 2的32次方減1，所以肯定不會溢出的。如果一開始 30 個位就存不下，那么數(shù)組中會有兩個 digit。

所以雖然將 32 位全部用完，可以只用一個 digit 表示更大的整數(shù)，但會面臨相加之后一個 digit 存不下的情況，于是只用 30 個位。如果數(shù)值大到 30 個位存不下的話，那么就會多使用一個 digit。

這里可能有人發(fā)現(xiàn)了，如果是用 31 個位的話，那么相加產(chǎn)生的最大值就是 2**32-2，結(jié)果依舊可以使用一個 32 位整型存儲啊，那 Python 為啥要犧牲兩個位呢？答案是為了乘法運(yùn)算。

為了方便計算乘法，需要多保留 1 位用于計算溢出。這樣當(dāng)兩個整數(shù)相乘的時候，可以直接按 digit 計算，并且由于兼顧了"溢出位"，可以把結(jié)果直接保存在一個寄存器中，以獲得最佳性能。

具體細(xì)節(jié)就不探究了，只需要知道整數(shù)在底層是使用 unsigned int 類型的數(shù)組來維護(hù)具體的值即可，并且雖然該類型的整數(shù)有 32 個位，但解釋器只用 30 個位。

然后還記得我們在看 digit 類型的時候，說過一個宏嗎？PYLONG_BITS_IN_DIGIT，在 64 位機(jī)器上為 30，32 位機(jī)器上為 15。相信這個宏表示的是啥你已經(jīng)清楚了，它代表的就是使用的 digit 的位數(shù)。

整數(shù) 2**30

問題來了，我們說 digit 只用 30 個位，所以 2 ** 30 - 1 是一個 digit 能存儲的最大值。而現(xiàn)在是 2**30，所以數(shù)組中就要有兩個 digit 了。

我們看到此時就用兩個 digit 來存儲了，此時的數(shù)組里面的元素就是 0 和 1，而且充當(dāng)高位的放在后面，因?yàn)槭鞘褂眯碌?digit 來模擬更高的位。

由于一個 digit 只用 30 位，那么數(shù)組中第一個 digit 的最低位就是 1，第二個 digit 的最低位就是 31，第三個 digit 的最低位就是 61，以此類推。

所以如果 ob_digit 為 [a, b, c]，那么對應(yīng)的整數(shù)就為：

如果 ob_digit 不止3個，那么就按照 30 個位往上加，比如 ob_digit 還有第四個元素 d，那么就再加上 d * 2 ** 90 即可。

以上就是 Python 整數(shù)的存儲奧秘，說白了就是串聯(lián)多個小整數(shù)來表達(dá)大整數(shù)。并且這些小整數(shù)之間的串聯(lián)方式并不是簡單的相加，而是將各自的位組合起來，共同形成一個具有高位的大整數(shù)，比如將兩個 8 位整數(shù)串聯(lián)起來，表示 16 位整數(shù)。

整數(shù)占的內(nèi)存大小是怎么計算的

下面我們再分析一下，一個整數(shù)要占用多大的內(nèi)存。

相信所有人都知道可以使用 sys.getsizeof 計算大小，但是這大小到底是怎么來的，估計會一頭霧水。因?yàn)?Python 中對象的大小，是根據(jù)底層的結(jié)構(gòu)體計算出來的。

由于 ob_refcnt、ob_type、ob_size 這三個是整數(shù)所必備的，它們都是 8 字節(jié)，加起來 24 字節(jié)。所以任何一個整數(shù)所占內(nèi)存都至少 24 字節(jié)，至于具體占多少，則取決于 ob_digit 里面的元素都多少個。

因此整數(shù)所占內(nèi)存等于 24 + 4 * ob_size(絕對值)

import?sys

#?如果是?0?的話,?ob_digit?數(shù)組為空
#?所以大小就是?24?字節(jié)
print(sys.getsizeof(0))??#?24

#?如果是?1?的話,?ob_digit?數(shù)組有一個元素
#?所以大小是?24?+?4?=?28?字節(jié)
print(sys.getsizeof(1))??#?28
#?同理
print(sys.getsizeof(2?**?30?-?1))??#?28

#?一個?digit?只用30位,?所以最大能表示?2?**?30?-?1
#?如果是?2?**?30,?那么就需要兩個元素
#?所以大小是?24?+?4?*?2?=?32?字節(jié)
print(sys.getsizeof(2?**?30))??#?32
print(sys.getsizeof(2?**?60?-?1))??#?32


#?如果是兩個?digit，那么能表示的最大整數(shù)就是?2?**?60?-?1
#?因此?2**60?次方需要三個digit，相信下面的不需要解釋了
print(sys.getsizeof(1?<<?60))??#?36
print(sys.getsizeof((1?<<?90)?-?1))??#?36

print(sys.getsizeof(1?<<?90))??#?40

所以整數(shù)的大小是這么計算的，當(dāng)然不光整數(shù)，其它的對象也是如此，計算的都是底層結(jié)構(gòu)體的大小。

另外我們也可以反推一下，如果有一個整數(shù) 88888888888，那么它對應(yīng)的底層數(shù)組ob_digit有幾個元素呢？每個元素的值又是多少呢？下面來分析一波。

import?numpy?as?np

#?假設(shè)占了?n?個位
#?由于?n?個位能表達(dá)的最大整數(shù)是?2**n?-?1
a?=?88888888888
#?所以只需要將?a+1、再以?2?為底求對數(shù)
#?即可算出?n?的大小
print(np.log2(a?+?1))??#?36.371284042320475

計算結(jié)果表明，如果想要存下這個整數(shù)，那么至少需要 37 個位。而 1 個 digit 用 30 個位，很明顯，我們需要兩個 digit。

如果ob_digit有兩個元素，那么對應(yīng)的整數(shù)就等于 ob_digit[0] 加上ob_digit[1]*2**30，于是結(jié)果就很好計算了。

a?=?88888888888
print(a?//?2?**?30)??#?82
print(a?-?82?*?2?**?30)??#?842059320

所以整數(shù) 88888888888 在底層對應(yīng)的 ob_digit 數(shù)組為 [842059320, 82]。我們修改解釋器，來驗(yàn)證這一結(jié)論。

我們看到結(jié)果和我們分析的是一樣的，但這種辦法有點(diǎn)麻煩。我們可以通過 ctypes 來構(gòu)造底層的結(jié)構(gòu)體，在 Python 的層面模擬 C 的行為。

from?ctypes?import?*

class?PyLongObject(Structure):
????_fields_?=?[
????????("ob_refcnt",?c_ssize_t),
????????("ob_type",?c_void_p),
????????("ob_size",?c_ssize_t),
????????("ob_digit",?c_uint32?*?2)
????]

a?=?88888888888
#?基于對象的地址構(gòu)造?PyLongObject?對象
long_obj?=?PyLongObject.from_address(id(a))
#?打印結(jié)果和我們預(yù)期的一樣
print(long_obj.ob_digit[0])??#?842059320
print(long_obj.ob_digit[1])??#?82

#?如果我們將?ob_digit[1]?改成?28
#?那么 a 會變成多少呢？
#?很簡單，算一下就知道了
long_obj.ob_digit[1]?=?28
print(842059320?+?28?*?2?**?30)??#?30906830392
#?那么a會不會也打印這個結(jié)果呢？
#?毫無疑問，肯定會的
print(a)??#?30906830392
#?并且前后a的地址沒有發(fā)生改變
#?因?yàn)槲覀冃薷牡牡讓訑?shù)組

通過打印 ob_digit 存儲的值，我們驗(yàn)證了得出的結(jié)論，原來 Python 是通過數(shù)組的方式來存儲的整數(shù)，并且數(shù)組的類型雖然是無符號 32 位整數(shù)，但是只用 30 個位。

當(dāng)然了，我們還通過修改 ob_digit，然后再打印 a 進(jìn)行了反向驗(yàn)證，而輸出內(nèi)容也符合我們的預(yù)期。并且在這個過程中，a 指向的對象的地址并沒有發(fā)生改變，也就是說，指向的始終是同一個對象。而內(nèi)容之所以會變，則因?yàn)槲覀兪峭ㄟ^修改 ob_digit 實(shí)現(xiàn)的。

因此所謂的可變和不可變，都只是根據(jù) Python 的表現(xiàn)抽象出來的。比如元組不支持本地修改，那么它就是 immutable，列表支持修改，它就是 mutable。但事實(shí)上真的如此嗎？元組真的不可變嗎？我們來打破這個結(jié)論。

from?ctypes?import?*

class?PyTupleObject(Structure):
????_fields_?=?[
????????("ob_refcnt",?c_ssize_t),
????????("ob_type",?c_void_p),
????????("ob_size",?c_ssize_t),
????????("ob_item",?py_object?*?3)
????]

tpl?=?(1,?2,?3)
#?構(gòu)造?PyTupleObject?實(shí)例
tuple_obj?=?PyTupleObject.from_address(id(tpl))
#?查看長度，len(元組)?本質(zhì)上就是獲取底層的?ob_size
#?所以這是一個時間復(fù)雜度為?O(1)?的操作
print(len(tpl),?tuple_obj.ob_size)??#?3?3

#?注意：重點(diǎn)來了，我們修改元組里的元素
print(f"-----?修改前?-----")
print(f"id(tpl):?{id(tpl)},?tpl:?{tpl}")

tuple_obj.ob_item[0]?=?py_object(3)
tuple_obj.ob_item[1]?=?py_object(2)
tuple_obj.ob_item[2]?=?py_object(1)

print(f"-----?修改后?-----")
print(f"id(tpl):?{id(tpl)},?tpl:?{tpl}")
"""
-----?修改前?-----
id(tpl):?2465780048640,?tpl:?(1,?2,?3)
-----?修改后?-----
id(tpl):?2465780048640,?tpl:?(3,?2,?1)
"""
#?我們看到前后的地址并沒有改變
#?但是元組卻發(fā)生了改變

因此所謂的 immutable 和 mutable 只是在使用 Python 時，抽象出來的這個一個東西。所以 immutable 類型的對象，本質(zhì)上也只是解釋器沒有將該對象的修改接口去暴露出來而已。

比如在 Python 中修改序列對象的某個元素時，會調(diào)用 __setitem__，但解釋器沒有為元組實(shí)現(xiàn)這個方法，所以元組是不可變對象；而解釋器為列表實(shí)現(xiàn)了，所以列表是可變對象。

而我們目前是模擬底層的結(jié)構(gòu)體實(shí)現(xiàn)的修改，所以繞過了解釋器的檢測?？傊€是那句話，可變和不可變都是針對 Python 的表現(xiàn)而抽象出來的，如果是站在解釋器的層面上看，沒啥可變或不可變，一切都由我們決定。

兩個整數(shù)是怎么比較大小的

到目前為止我們通過考察整數(shù)的具體實(shí)現(xiàn)，明白了它能夠保證不溢出的緣由。因?yàn)檎麛?shù)溢出導(dǎo)致的 BUG 非常多，而且不易發(fā)覺，為此 Python 設(shè)計出了不會溢出的整數(shù)，選擇從語言層面解決問題。

Python 的整數(shù)是串聯(lián)了多個 C 的 digit、即 uint32_t，在底層通過一個數(shù)組來實(shí)現(xiàn)整數(shù)的存儲。這么做的好處就是 Python 整數(shù)沒有長度限制了，因此不會溢出。而不會溢出的原因是數(shù)組是沒有長度限制的，所以只要你的內(nèi)存足夠，就可以算任意大的數(shù)。

Python 表示：存不下？會溢出？這都不是事兒，直接繼續(xù)往數(shù)組里面塞 digit 就 ok 了。另外數(shù)組存的是絕對值，符號是通過 ob_size 體現(xiàn)的。

不過說實(shí)話，用數(shù)組實(shí)現(xiàn)大整數(shù)的做法非常普遍，并沒有什么神秘的，就是將多個整數(shù)組合起來，模擬具有更高位的大整數(shù)。但這種實(shí)現(xiàn)方式的難點(diǎn)在于大整數(shù)的數(shù)學(xué)運(yùn)算，它們才是重點(diǎn)，實(shí)現(xiàn)的時候比較考驗(yàn)編程技巧以及思維邏輯。

因此 Python 的整數(shù)比浮點(diǎn)數(shù)要復(fù)雜的多，浮點(diǎn)數(shù)在底層直接用 C 的 double 來維護(hù)具體的值，因此運(yùn)算的話，比如相加，直接轉(zhuǎn)成 C 的 double 做加法即可。但整數(shù)就不行了，在底層不能簡單地將數(shù)組相加。

下面就來看看 Python 整數(shù)的運(yùn)算在底層是怎么做的？不過在看運(yùn)算之前，先來看看整數(shù)的大小比較。

首先整數(shù)在底層是通過數(shù)組存儲的，ob_size 的絕對值維護(hù)了數(shù)組的長度。顯然數(shù)組越長，整數(shù)的絕對值就越大，這是毫無疑問的。至于整數(shù)的正負(fù)，則由 ob_size 的正負(fù)來體現(xiàn)。那么兩個整數(shù)進(jìn)行比較時：

如果 ob_size 均為正，顯然 ob_size 越大，底層數(shù)組越長，對應(yīng)的整數(shù)越大；
如果 ob_size 均為負(fù)，顯然 ob_size 越大（越靠近0），底層數(shù)組越短，整數(shù)的絕對值越小。但因?yàn)槭秦?fù)數(shù)，還要乘上 -1，因此整數(shù)反而會越大；
如果 ob_size 一正一負(fù)，這個應(yīng)該就不必說了， ob_size 體現(xiàn)了整數(shù)的正負(fù)，正數(shù)肯定大于負(fù)數(shù)。

因此可以得出一個結(jié)論：當(dāng)兩個整數(shù)在比大小時，可以先比較各自的 ob_size。如果 ob_size 不一樣，那么可以直接比較出整數(shù)的大小，并且是 ob_size 越大，整數(shù)越大。不管 ob_size 的正負(fù)如何，這一結(jié)論都是成立的，上面已經(jīng)進(jìn)行了驗(yàn)證。

但如果兩個整數(shù)的 ob_size 一樣，那么就從數(shù)組 ob_digit 的尾部元素開始，不斷向前進(jìn)行比較。只要兩個整數(shù)的 ob_digit 中有一個對應(yīng)元素不相同，那么就可以比較出大小。

之所以從數(shù)組的尾部開始，是因?yàn)閿?shù)組元素的索引越大，那么充當(dāng)?shù)奈粩?shù)就越高，而在比較的時候顯然要從高位開始比。

#?ob_digit?=?[892311,?32,?3]
a1?=?3458764548181171607
#?ob_digit?=?[2296,?31,?3]
a2?=?3458764547106539768

我們以 a1 和 a2 為例，顯然 a1 大于 a2，那么在底層，它們是如何比較的呢？

當(dāng)然啦，我們圖中還少了一步，因?yàn)閿?shù)組反映的是絕對值的大小。所以圖中比較的是兩個整數(shù)的絕對值，只不過正數(shù)和它的絕對值相同；但如果是負(fù)數(shù)，那么絕對值越大，對應(yīng)的整數(shù)反而越小，因此比較之后的結(jié)果還要再乘上 -1。

比如將 a1 和 a2 都乘以 -1，那么它們的 ob_size 都為 -3，由于 ob_size 相同，于是比較絕對值的大小。a1 絕對值大于 a2 絕對值，但因?yàn)槭秦?fù)數(shù)，所以改變符號，結(jié)果是 a1 小于 a2。

但如果數(shù)組都遍歷完了，發(fā)現(xiàn)相同索引對應(yīng)的元素都是相同的，那么兩個整數(shù)就是相等的。

Python 底層也是按照上面這種方式比較的，先比較 ob_size，ob_size 不一樣則可以直接比較出大小。如果ob_size一樣的話，那么會從后往前挨個比較數(shù)組中的元素，確定整數(shù)絕對值的大小關(guān)系。最后再結(jié)合 ob_size 的正負(fù)，確定整數(shù)的大小關(guān)系。

整數(shù)的加減法運(yùn)算

因?yàn)閿?shù)組保存了整數(shù)的絕對值，所以 Python 將整數(shù)的運(yùn)算轉(zhuǎn)成了絕對值運(yùn)算。而底層有兩個函數(shù)專門用來做這件事情，分別是 x_add 和 x_sub。

x_add(a, b), 計算兩者的絕對值之和, 即:|a| + |b|；
x_sub(a, b), 計算兩者的絕對值之差, 即:|a| - |b|；

所以整數(shù)相加就可以這么做，假設(shè)兩個整數(shù) a 和 b 相加：

如果 a 和 b 均為負(fù)數(shù)，則通過 x_add 計算兩者絕對值之和，然后再取相反數(shù)；
如果 a 為負(fù)數(shù)，b 為正數(shù)，那么通過 x_sub 計算 b 和 a 絕對值之差即可；
如果 a 為正數(shù)，b 為負(fù)數(shù)，那么通過 x_sub 計算 a 和 b 絕對值之差即可；
如果 a 和 b 均為正數(shù)，那么通過 x_add 計算 a 和 b 絕對值之和即可；

而整數(shù)相減也是同理，還是整數(shù) a 和 b，兩者相減：

如果 a 為正數(shù)，b 為負(fù)數(shù)，則通過 x_add 計算兩者絕對值之和即可；
如果 a 為負(fù)數(shù)，b 為正數(shù)，則通過 x_add 計算兩者絕對值之和，然后再取相反數(shù)；
如果 a 和 b 均為正數(shù)，則通過 x_sub 計算 a 和 b 絕對值之差；
如果 a 和 b 均為負(fù)數(shù)，則通過 x_sub 計算 a 和 b 絕對值之差，然后再取相反數(shù)。因?yàn)?a 和 b 為負(fù)，所以 a - b 和 |a| - |b| 的符號是相反的。比如 -5 - -3 的結(jié)果是 -2，而 5 - 3 的結(jié)果是 2；

所以相加時，符號相同會調(diào)用 x_add、符號不同會調(diào)用 x_sub；相減時，符號相同會調(diào)用 x_sub、符號不同會調(diào)用 x_add。

所以這就是 Python 的設(shè)計，因?yàn)榻^對值的加減法不用考慮符號的影響，實(shí)現(xiàn)更為簡單，所以 Python 將整數(shù)運(yùn)算轉(zhuǎn)化成整數(shù)的絕對值運(yùn)算。

那么下面我們的重心就在 x_add 和 x_sub 上面了，看看它們是如何對大整數(shù)絕對值進(jìn)行運(yùn)算的。到這里你可能會有疑問，大整數(shù)運(yùn)算這么復(fù)雜，效率會差吧。顯然這是啃腚的，整數(shù)數(shù)值越大，整數(shù)對象的底層數(shù)組就越長，運(yùn)算開銷也就越大。

但 Python 底層有一個機(jī)制叫做快分支，因?yàn)橥ㄓ眠壿嬆芴幚硭星闆r，那么它的效率必然不高。而快分支則是對那些可以簡單運(yùn)算的情況提前進(jìn)行處理，比如在對 a 和 b 計算加減法的時候，底層會先判斷數(shù)組的長度是否均小于等于 1，如果是則說明數(shù)組中最多只有一個元素。這樣的話，可以直接拿出來轉(zhuǎn)成 C 的整數(shù)進(jìn)行運(yùn)算，這樣性能損耗就可以忽略不計。

并且整數(shù)不超過 2 ** 30 - 1，都可以走快分支，顯然這可以滿足我們絕大部分場景。那么下面我們來看通用邏輯 x_add 和 x_sub 的實(shí)現(xiàn)，首先是絕對值加法 x_add。

在介紹之前，我們不妨想象一下我們平時算加法的時候是怎么做的：

從最低位開始進(jìn)行相加，逢十進(jìn)一，ob_digit 也是同理。我們可以把數(shù)組中的每一個元素看成是一個整體，只不過它不再是逢十進(jìn)一，而是逢 2**30 進(jìn)一。

# 數(shù)組的每個元素最大能表示 2**30-1
# 把元素整體想象成我們生活中加法的個位、十位、百位...
# 然后對應(yīng)的位相加，逢 2**30 進(jìn)一
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

所以仍舊是對應(yīng)的位進(jìn)行相加，和我們生活中的加法并無本質(zhì)上的區(qū)別。只不過生活中的加法，每一位能表示 0~9，逢十進(jìn)一；而 Python 底層的加法，因?yàn)檎麛?shù)使用數(shù)組存儲，那么每一個位能表示 0 ~ 2**30-1，逢 2**30 進(jìn)一。

把 1024、342 想象成個位，把 22、18 想象成十位，并且此時不再是逢十進(jìn)一，而是逢 2**30 進(jìn)一。

a?=?[2?**?30?-?1,?16]
b?=?[2?**?30?-?1,?21]
#?a[0]?+?b[0]?超過了?2?**?30，要進(jìn)個?1
#?而逢十進(jìn)一之后，該位要減去十
#?那么逢?2**30?進(jìn)一之后，顯然要減去?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

還是不難理解的，就是把數(shù)組中每一個對應(yīng)的元素分別相加，逢 2**30 進(jìn) 1，可以通過編程實(shí)現(xiàn)一下。而 x_add 的源碼位于 longobject.c 中，也建議讀一讀。

然后是絕對值減法，和絕對值加法一樣，也可以類比生活中的減法，從低位到高位分別相減。如果某一位相減的時候發(fā)現(xiàn)不夠了，那么要向高位借一位。比如 27 - 9，7 比 9 小，因此向 2 借一位變成 17，減去 9，得 8。但 2 被借了一位，所以剩下 1，因此結(jié)果為 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]

#?驗(yàn)證一下
print(
????(a[0]?+?a[1]?*?2?**?30)
????-
????(b[0]?+?b[1]?*?2?**?30)
)??#?2147483647
print(
????result[0]?+?result[1]?*?2?**?30
)??#?2147483647

結(jié)果沒有問題，這里強(qiáng)烈建議看一下 x_add 和 x_sub 的底層實(shí)現(xiàn)，里面用了大量的位運(yùn)算，實(shí)現(xiàn)非常的巧妙。