Python內部是如何實現整數相加不溢出的？
1、如何表示一個整數
要想了解這個，那就需要看 Python 的源代碼[1]，Python中的整數底層對應的結構體是PyLongObject，它位于 longobject.h[2] 中。
逐步展開如下：
- //longobject.h
- typedef struct _longobject PyLongObject; /* Revealed in longintrepr.h */
- //longintrepr.h
- struct _longobject {
- PyObject_VAR_HEAD
- digit ob_digit[1];
- };
- //合起來可以看成
- typedef struct {
- PyObject_VAR_HEAD
- digit ob_digit[1];
- } PyLongObject;
再把宏定義 PyObject_VAR_HEAD 展開：
- typedef struct {
- PyObject_HEAD
- int ob_size;
- digit ob_digit[1];
- } PyLongObject;
再把宏定義 PyObject_HEAD 展開，結構體中的變量我已經作了注釋：
- typedef struct {
- int ob_refcnt; //引用計數
- struct _typeobject *ob_type; //變量類型
- int ob_size; //用來指明變長對象中一共容納了多少個元素
- digit ob_digit[1]; //digit類型的數組,長度為1
- } PyLongObject;
這里面的 ob_size 用來指明變長對象中一共容納了多少個元素，也就是 ob_digit 數組的長度，而這個 ob_digit 數組顯然只能是用來維護具體的值。
到這里已經很明顯了，Python 將大整數切割后存在 ob_digit，這個數組的長度是可變的，數據越大，數組越長，只要內存夠用，存多大的數都可以。
那么下面的重點就在這個 ob_digit 數組了，我們看看 Python 中整數對應的值，比如 256，是怎么放在這個數組里面的。不過首先我們要看看這個digit 是個什么類型，它同樣定義在 longintrepr.h 中。
- #if PYLONG_BITS_IN_DIGIT == 30
- typedef uint32_t digit;
- // ...
- #elif PYLONG_BITS_IN_DIGIT == 15
- typedef unsigned short digit;
- // ...
- #endif
PYLONG_BITS_IN_DIGIT 是一個宏，如果你的機器是 64 位的，那么它會被定義為 30，32 位機器則會被定義為 15。
而我們的機器現在基本上都是 64 位的，所以 PYLONG_BITS_IN_DIGIT會等于 30，因為 digit 等價于 uint32_t(unsigned int)，所以它是一個無符號 32 位整型。
所以 ob_digit 這個數組是一個無符號 32 位整型數組，長度為 1。當然這個數組具體多長則取決于你要存儲的 Python 整數有多大，因為 C 中數組的長度不屬于類型信息，你可以看成是長度 n，而這個 n 是多少要取決于你的整數大小。顯然整數越大，這個數組就越長，那么占用空間就越大。
為了說明 256 是如何存放在 ob_digit 里的，我們來簡化下，這里假如 ob_digit 這個數組是一個無符號 8 位整型數組，8 位二進制，最大只能表示 255，我們要表示 256，那就只能再申請一個 8 位，也許你認為再申請一個 8 位來表示 1，其實不是的，是使用一個新的 8 位整數來模擬更高的位，如下所示：
- 255 = [255]
- 256 = [1,1]
256 = [1,1] 的形式也不是真實情況，為了你理解，先這樣寫，它表達的意思就是 256 = 1 + 1 * (2^8 - 1) = 1 + 1 * 255 = 256。
也就是說 ob_digit 表示 x 進制數，ob_digit[0] 是低位，ob_digit[1] 是高位，具體 x 是多少，取決于 ob_digit 的類型，這里 8 位，就是 255 進制。
剛才提到 256 = [1,1] 的形式也不是真實情況，因為 PyLongObject 不僅僅是為了存儲大整數，也需要參與運算，具體怎么運算呢，那就是 ob_digit 逐位相加即可。
既然是相加，即又可能溢出，比如 [255 , 1] + [255, 1] = [510,2]
這里的 510 就超出了 8 位，為了簡化處理，只要我們不用滿 8 位，就不會溢出，也就是說，比如說只用 7 位，那最大也就是 [127,...] + [127,...] = [254,...] 也就不會溢出了。
到這里，你會明白，為什么 digit 雖然是無符號 32 位整數，卻只使用 30 位了吧：
- #if PYLONG_BITS_IN_DIGIT == 30
- typedef uint32_t digit;
- // ...
- #elif PYLONG_BITS_IN_DIGIT == 15
- typedef unsigned short digit;
- // ...
- #endif
聰明的你，可能會問，31 位就可以保證不溢出，為啥犧牲兩位，用 30 位，答案我也不知道，可能是因為 64 是 32 的兩倍， 30 也是 15 的兩倍，這樣看起來更舒服吧。
那如何表示負數呢，其實負數的話，就是 ob_size 變成了負的，其他沒變。整數的正負號是通過這里的 ob_size 決定的。ob_digit 存儲的其實是絕對值，無論 n 取多少，-n 和 n 對應的 ob_digit 是完全一致的，但是ob_size 則互為相反數。所以 ob_size 除了表示數組的長度之外，還可以表示對應整數的正負。
所以 Python 在比較兩個整型的大小時，會先比較 ob_size，如果 ob_size 不一樣則可以直接比較出大小來。
總結一下，就是當 PYLONG_BITS_IN_DIGIT == 30 的時候，整數 = ob_digit[0] + ob_digit[1] * 2 ** 30 + ob_digit[2] * 2 ** 60 + ...
2、整數占用內存大小
理解了這一點，我們再看一下這個結構體：
- typedef struct {
- int ob_refcnt; //引用計數
- struct _typeobject *ob_type; //變量類型
- int ob_size; //用來指明變長對象中一共容納了多少個元素
- digit ob_digit[1]; //digit類型的數組,長度為1
- } PyLongObject;
一個整數占用多少個字節，取決于 PyLongObject 這個結構體占用多少字節，ob_refcnt、ob_type、ob_size 這三個是整數所必備的，它們都是 8 字節，加起來 24 字節。所以任何一個整數所占內存都至少 24 字節，至于具體占多少，則取決于 ob_digit 里面的元素都多少個。
現在的你不難理解以下結果：
3、整數池
此外 Python 中的整數屬于不可變對象，運算之后會創建新的對象:
- >>> a = 300
- >>> id(a)
- 140220663619152
- >>> a += 1
- >>> id(a)
- 140220663619408
- >>>
這樣就勢必會有性能缺陷，因為程序運行時會有對象的創建和銷毀，就是涉及內存的申請和垃圾回收，一個常用的手段就是使用對象池，將頻率高的整數預先創建好，而且都是單例模式，需要使用時直接返回。
小整數對象池的實現位于 pycore_interp.h[3] 中：
驗證一下：
- >>> a = -6
- >>> b = -6
- >>> a is b
- False
- >>> a = -5
- >>> b = -5
- >>> a is b
- True
- >>> a = 256
- >>> b = 256
- >>> a is b
- True
- >>> a = 257
- >>> b = 257
- >>> a is b
- False
- >>>
不同的版本可能會不同，我這里 Python3.8，區間為 [-5,257)。
4、整數加減法
有了前面的鋪墊，現在我們來看下 Python 中大整數是如何相加的，源代碼 longobject.c : long_add 函數[4]。
可以看到 long_add 根據 ob_size 的正或負來調用 x_add 或 x_sub。
現在看一下 x_add 的源代碼：
可以看到，Python 大整數的相加就是底層數組的相加，當然還會涉及到進位等操作：
- for (i = 0; i < size_b; ++i) {
- carry += a->ob_digit[i] + b->ob_digit[i];
- z->ob_digit[i] = carry & PyLong_MASK;
- carry >>= PyLong_SHIFT;
- }
x_sub 的源代碼：
4、整數乘法
Python 整數乘法使用的是 Karatsuba multiplication[5] 算法進行的大數乘法，感興趣的可以研究一下。
最后的話
源碼之下無秘密，看源碼會比較辛苦，卻可以學到精髓和本質，本文通過源碼逐層展開，帶你了解了下 Python 整數對象的實現、整數內存大小的計算，整數池，整數加減法源碼，相信你已經知道了 Python 是如何實現整數想加而不溢出的。如果有收獲，還請點在、點贊、轉發，感謝一路的支持和陪伴。
