詳解Python的整數是如何實現的

2022-11-05 14:01:09

楔子

本次我想聊一聊 Python 的整數，我們知道 Python 的整數是不會溢位的，換句話說，它可以計算無窮大的數，只要你的記憶體足夠，它就能計算。

而 C 顯然沒有這個特徵，C 裡面能表示的整數範圍是有限的。但問題是，Python 底層又是 C 實現的，那麼它是怎麼做到整數不溢位的呢？既然想知道答案，那麼看一下整數在底層是怎麼定義的就行了。

整數的底層實現

Python 整數在底層對應的結構體是 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 更細緻的展開一下
typedef struct {
    // 參照計數  
    Py_ssize_t ob_refcnt; 
    // 型別
    struct _typeobject *ob_type; 
    // 維護的元素個數
    Py_ssize_t ob_size;
    // digit 型別的陣列，長度為 1 
    digit ob_digit[1]; 
} PyLongObject;

別的先不說，就衝裡面的 ob_size 我們就可以思考一番。首先 Python 的整數有大小、但應該沒有長度的概念吧，那為什麼會有一個 ob_size 呢？

從結構體成員來看，這個 ob_size 指的應該就是陣列 ob_digit 的長度，而這個 ob_digit 顯然只能是用來維護具體的值了。而陣列的長度不同，那麼對應的整數佔用的記憶體也不同。

所以答案出來了，整數雖然沒有我們生活中的那種長度的概念，但它是個變長物件，因為不同的整數佔用的記憶體可能是不一樣的。因此這個 ob_size 指的是底層陣列的長度，因為整數對應的值在底層是使用陣列來儲存的。儘管它沒有字串、列表那種長度的概念，或者說無法對整數使用 len 函數，但它是個變長物件。

那麼下面的重點就在這個 ob_digit 陣列身上了，我們要從它的身上挖掘資訊，看看一個整數是怎麼放在這個陣列裡面的。不過首先我們要搞清楚這個 digit 是什麼型別，它的定義同樣位於 longintrepr.h 中：

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

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

因此 ob_digit 是一個無符號 32 位整型陣列，長度為 1。當然這個陣列具體多長則取決於你要儲存的整數有多大，不同於 Golang，C 陣列的長度不屬於型別資訊。

雖然定義的時候，宣告陣列的長度為 1，但你可以把它當成任意長度的陣列來用，這是 C 語言中常見的程式設計技巧。至於長度具體是多少，則取決於你的整數大小。顯然整數越大，這個陣列就越長，佔用的空間也就越大。

搞清楚了 PyLongObject 裡面的所有成員，那麼下面我們就來分析 ob_digit 是怎麼儲存整數的，以及 Python 的整數為什麼不會溢位。

不過說實話，關於整數不會溢位這個問題，相信很多人已經有答案了。因為底層是使用陣列儲存的，而陣列的長度又沒有限制，所以當然不會溢位。另外，還存在一個問題，那就是 digit 是一個無符號 32 位整型，那負數怎麼儲存呢？彆著急，我們會舉例說明，將上面的疑問逐一解答。

整數是怎麼儲存的

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

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

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

整數 0

注意：當表示的整數為 0 時，ob_digit 陣列為空，不儲存任何值。而 ob_size 為 0，表示這個整數的值為 0，這是一種特殊情況。

整數 1

當儲存的值為 1 時，此時 ob_digit 陣列就是 [1]，顯然 ob_size 的值也是 1，因為它維護的就是 ob_digit 陣列的長度。

整數 -1

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

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

整數 2**30 - 1

如果想表示 2的30次方減1，那麼也可以使用一個 digit 表示。話雖如此，但為什麼突然說這個數位呢？答案是：雖然 digit 是 4 位元組、32 位，但是直譯器只用 30 個位。

之所以這麼做是和加法進位有關係，如果 32 個位全部用來儲存其絕對值，那麼相加產生進位的時候，可能會溢位。比如 2 ** 32 - 1，此時 32 個位全部佔滿了，即便它只加上 1，也會溢位。那麼為了解決這個問題，就需要先強制轉換為 64 位整數再進行運算，從而會影響效率。但如果只用 30 個位的話，那麼加法是不會溢位的，或者說相加之後依舊可以用 32 位整數儲存。

因為 30 個位最大就是 2的30次方減1，即便兩個這樣的值相加，結果也是 2的31次方減2。而 32 個位最大能表示的是 2的32次方減1，所以肯定不會溢位的。如果一開始 30 個位就存不下，那麼陣列中會有兩個 digit。

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

這裡可能有人發現了，如果是用 31 個位的話，那麼相加產生的最大值就是 2**32-2，結果依舊可以使用一個 32 位整型儲存啊，那 Python 為啥要犧牲兩個位呢？答案是為了乘法運算。

為了方便計算乘法，需要多保留 1 位用於計算溢位。這樣當兩個整數相乘的時候，可以直接按 digit 計算，並且由於兼顧了"溢位位"，可以把結果直接儲存在一個暫存器中，以獲得最佳效能。

具體細節就不探究了，只需要知道整數在底層是使用 unsigned int 型別的陣列來維護具體的值即可，並且雖然該型別的整數有 32 個位，但直譯器只用 30 個位。

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

整數 2**30

問題來了，我們說 digit 只用 30 個位，所以 2 ** 30 - 1 是一個 digit 能儲存的最大值。而現在是 2**30，所以陣列中就要有兩個 digit 了。

我們看到此時就用兩個 digit 來儲存了，此時的陣列裡面的元素就是 0 和 1，而且充當高位的放在後面，因為是使用新的 digit 來模擬更高的位。

由於一個 digit 只用 30 位，那麼陣列中第一個 digit 的最低位就是 1，第二個 digit 的最低位就是 31，第三個 digit 的最低位就是 61，以此類推。

所以如果 ob_digit 為 [a, b, c]，那麼對應的整數就為：

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

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

整數佔的記憶體大小是怎麼計算的

下面我們再分析一下，一個整數要佔用多大的記憶體。

相信所有人都知道可以使用 sys.getsizeof 計算大小，但是這大小到底是怎麼來的，估計會一頭霧水。因為 Python 中物件的大小，是根據底層的結構體計算出來的。

由於 ob_refcnt、ob_type、ob_size 這三個是整數所必備的，它們都是 8 位元組，加起來 24 位元組。所以任何一個整數所佔記憶體都至少 24 位元組，至於具體佔多少，則取決於 ob_digit 裡面的元素都多少個。

因此整數所佔記憶體等於 24 + 4 * ob_size(絕對值)

import sys

# 如果是 0 的話, ob_digit 陣列為空
# 所以大小就是 24 位元組
print(sys.getsizeof(0))  # 24

# 如果是 1 的話, ob_digit 陣列有一個元素
# 所以大小是 24 + 4 = 28 位元組
print(sys.getsizeof(1))  # 28
# 同理
print(sys.getsizeof(2 ** 30 - 1))  # 28

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


# 如果是兩個 digit，那麼能表示的最大整數就是 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

所以整數的大小是這麼計算的，當然不光整數，其它的物件也是如此，計算的都是底層結構體的大小。

另外我們也可以反推一下，如果有一個整數 88888888888，那麼它對應的底層陣列ob_digit有幾個元素呢？每個元素的值又是多少呢？下面來分析一波。

import numpy as np

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

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

如果ob_digit有兩個元素，那麼對應的整數就等於 ob_digit[0] 加上ob_digit[1]*2**30，於是結果就很好計算了。

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

所以整數 88888888888 在底層對應的 ob_digit 陣列為 [842059320, 82]。我們修改直譯器，來驗證這一結論。

我們看到結果和我們分析的是一樣的，但這種辦法有點麻煩。我們可以通過 ctypes 來構造底層的結構體，在 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
# 基於物件的地址構造 PyLongObject 物件
long_obj = PyLongObject.from_address(id(a))
# 列印結果和我們預期的一樣
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會不會也列印這個結果呢？
# 毫無疑問，肯定會的
print(a)  # 30906830392
# 並且前後a的地址沒有發生改變
# 因為我們修改的底層陣列

通過列印 ob_digit 儲存的值，我們驗證了得出的結論，原來 Python 是通過陣列的方式來儲存的整數，並且陣列的型別雖然是無符號 32 位整數，但是隻用 30 個位。

當然了，我們還通過修改 ob_digit，然後再列印 a 進行了反向驗證，而輸出內容也符合我們的預期。並且在這個過程中，a 指向的物件的地址並沒有發生改變，也就是說，指向的始終是同一個物件。而內容之所以會變，則因為我們是通過修改 ob_digit 實現的。

因此所謂的可變和不可變，都只是根據 Python 的表現抽象出來的。比如元組不支援本地修改，那麼它就是 immutable，列表支援修改，它就是 mutable。但事實上真的如此嗎？元組真的不可變嗎？我們來打破這個結論。

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)
# 構造 PyTupleObject 範例
tuple_obj = PyTupleObject.from_address(id(tpl))
# 檢視長度，len(元組) 本質上就是獲取底層的 ob_size
# 所以這是一個時間複雜度為 O(1) 的操作
print(len(tpl), tuple_obj.ob_size)  # 3 3

# 注意：重點來了，我們修改元組裡的元素
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)
"""
# 我們看到前後的地址並沒有改變
# 但是元組卻發生了改變

因此所謂的 immutable 和 mutable 只是在使用 Python 時，抽象出來的這個一個東西。所以 immutable 型別的物件，本質上也只是直譯器沒有將該物件的修改介面去暴露出來而已。

比如在 Python 中修改序列物件的某個元素時，會呼叫 __setitem__，但直譯器沒有為元組實現這個方法，所以元組是不可變物件；而直譯器為列表實現了，所以列表是可變物件。

而我們目前是模擬底層的結構體實現的修改，所以繞過了直譯器的檢測。總之還是那句話，可變和不可變都是針對 Python 的表現而抽象出來的，如果是站在直譯器的層面上看，沒啥可變或不可變，一切都由我們決定。

兩個整數是怎麼比較大小的

到目前為止我們通過考察整數的具體實現，明白了它能夠保證不溢位的緣由。因為整數溢位導致的 BUG 非常多，而且不易發覺，為此 Python 設計出了不會溢位的整數，選擇從語言層面解決問題。

Python 的整數是串聯了多個 C 的 digit、即 uint32_t，在底層通過一個陣列來實現整數的儲存。這麼做的好處就是 Python 整數沒有長度限制了，因此不會溢位。而不會溢位的原因是陣列是沒有長度限制的，所以只要你的記憶體足夠，就可以算任意大的數。

Python 表示：存不下？會溢位？這都不是事兒，直接繼續往陣列裡面塞 digit 就 ok 了。另外陣列存的是絕對值，符號是通過 ob_size 體現的。

不過說實話，用陣列實現大整數的做法非常普遍，並沒有什麼神祕的，就是將多個整陣列合起來，模擬具有更高位的大整數。但這種實現方式的難點在於大整數的數學運算，它們才是重點，實現的時候比較考驗程式設計技巧以及思維邏輯。

因此 Python 的整數比浮點數要複雜的多，浮點數在底層直接用 C 的 double 來維護具體的值，因此運算的話，比如相加，直接轉成 C 的 double 做加法即可。但整數就不行了，在底層不能簡單地將陣列相加。

下面就來看看 Python 整數的運算在底層是怎麼做的？不過在看運算之前，先來看看整數的大小比較。

首先整數在底層是通過陣列儲存的，ob_size 的絕對值維護了陣列的長度。顯然陣列越長，整數的絕對值就越大，這是毫無疑問的。至於整數的正負，則由 ob_size 的正負來體現。那麼兩個整數進行比較時：

如果 ob_size 均為正，顯然 ob_size 越大，底層陣列越長，對應的整數越大；
如果 ob_size 均為負，顯然 ob_size 越大（越靠近0），底層陣列越短，整數的絕對值越小。但因為是負數，還要乘上 -1，因此整數反而會越大；
如果 ob_size 一正一負，這個應該就不必說了， ob_size 體現了整數的正負，正數肯定大於負數。

因此可以得出一個結論：當兩個整數在比大小時，可以先比較各自的 ob_size。如果 ob_size 不一樣，那麼可以直接比較出整數的大小，並且是 ob_size 越大，整數越大。不管 ob_size 的正負如何，這一結論都是成立的，上面已經進行了驗證。

但如果兩個整數的 ob_size 一樣，那麼就從陣列 ob_digit 的尾部元素開始，不斷向前進行比較。只要兩個整數的 ob_digit 中有一個對應元素不相同，那麼就可以比較出大小。

之所以從陣列的尾部開始，是因為陣列元素的索引越大，那麼充當的位數就越高，而在比較的時候顯然要從高位開始比。

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

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

當然啦，我們圖中還少了一步，因為陣列反映的是絕對值的大小。所以圖中比較的是兩個整數的絕對值，只不過正數和它的絕對值相同；但如果是負數，那麼絕對值越大，對應的整數反而越小，因此比較之後的結果還要再乘上 -1。

比如將 a1 和 a2 都乘以 -1，那麼它們的 ob_size 都為 -3，由於 ob_size 相同，於是比較絕對值的大小。a1 絕對值大於 a2 絕對值，但因為是負數，所以改變符號，結果是 a1 小於 a2。

但如果陣列都遍歷完了，發現相同索引對應的元素都是相同的，那麼兩個整數就是相等的。

Python 底層也是按照上面這種方式比較的，先比較 ob_size，ob_size 不一樣則可以直接比較出大小。如果ob_size一樣的話，那麼會從後往前挨個比較陣列中的元素，確定整數絕對值的大小關係。最後再結合 ob_size 的正負，確定整數的大小關係。

整數的加減法運算

因為陣列儲存了整數的絕對值，所以 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 計算 a 和 b 絕對值之差，然後再取相反數。因為 a 和 b 為負，所以 a - b 和 |a| - |b| 的符號是相反的。比如 -5 - -3 的結果是 -2，而 5 - 3 的結果是 2；

所以相加時，符號相同會呼叫 x_add、符號不同會呼叫 x_sub；相減時，符號相同會呼叫 x_sub、符號不同會呼叫 x_add。

所以這就是 Python 的設計，因為絕對值的加減法不用考慮符號的影響，實現更為簡單，所以 Python 將整數運算轉化成整數的絕對值運算。

那麼下面我們的重心就在 x_add 和 x_sub 上面了，看看它們是如何對大整數絕對值進行運算的。到這裡你可能會有疑問，大整數運算這麼複雜，效率會差吧。顯然這是啃腚的，整數數值越大，整數物件的底層陣列就越長，運算開銷也就越大。

但 Python 底層有一個機制叫做快分支，因為通用邏輯能處理所有情況，那麼它的效率必然不高。而快分支則是對那些可以簡單運算的情況提前進行處理，比如在對 a 和 b 計算加減法的時候，底層會先判斷陣列的長度是否均小於等於 1，如果是則說明陣列中最多隻有一個元素。這樣的話，可以直接拿出來轉成 C 的整數進行運算，這樣效能損耗就可以忽略不計。

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

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

從最低位開始進行相加，逢十進一，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，可以通過程式設計實現一下。而 x_add 的原始碼位於 longobject.c 中，也建議讀一讀。

然後是絕對值減法，和絕對值加法一樣，也可以類比生活中的減法，從低位到高位分別相減。如果某一位相減的時候發現不夠了，那麼要向高位借一位。比如 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

結果沒有問題，這裡強烈建議看一下 x_add 和 x_sub 的底層實現，裡面用了大量的位運算，實現非常的巧妙。