1、如何表示一個整數(shù)

要想了解這個，那就需要看 Python 的源代碼[1]，Python中的整數(shù)底層對應(yīng)的結(jié)構(gòu)體是PyLongObject，它位于 longobject.h[2] 中。

逐步展開如下：

1. //longobject.h 
2. typedef struct _longobject PyLongObject; /* Revealed in longintrepr.h */ 
3.   
4. //longintrepr.h 
5. struct _longobject { 
6.     PyObject_VAR_HEAD 
7.     digit ob_digit[1]; 
8. }; 
9.   
10. //合起來可以看成 
11. typedef struct { 
12.     PyObject_VAR_HEAD 
13.     digit ob_digit[1]; 
14. } PyLongObject; 

再把宏定義 PyObject_VAR_HEAD 展開：

1. typedef struct { 
2.     PyObject_HEAD 
3.     int ob_size; 
4.     digit ob_digit[1]; 
5. } PyLongObject; 

再把宏定義 PyObject_HEAD 展開，結(jié)構(gòu)體中的變量我已經(jīng)作了注釋：

1. typedef struct { 
2.     int ob_refcnt;    //引用計數(shù) 
3.     struct _typeobject *ob_type; //變量類型 
4.     int ob_size;       //用來指明變長對象中一共容納了多少個元素 
5.     digit ob_digit[1]; //digit類型的數(shù)組,長度為1 
6. } PyLongObject; 

這里面的 ob_size 用來指明變長對象中一共容納了多少個元素，也就是 ob_digit 數(shù)組的長度，而這個 ob_digit 數(shù)組顯然只能是用來維護(hù)具體的值。

到這里已經(jīng)很明顯了，Python 將大整數(shù)切割后存在 ob_digit，這個數(shù)組的長度是可變的，數(shù)據(jù)越大，數(shù)組越長，只要內(nèi)存夠用，存多大的數(shù)都可以。

那么下面的重點(diǎn)就在這個 ob_digit 數(shù)組了，我們看看 Python 中整數(shù)對應(yīng)的值，比如 256，是怎么放在這個數(shù)組里面的。不過首先我們要看看這個digit 是個什么類型，它同樣定義在 longintrepr.h 中

1. #if PYLONG_BITS_IN_DIGIT == 30 
2. typedef uint32_t digit; 
3. // ... 
4. #elif PYLONG_BITS_IN_DIGIT == 15 
5. typedef unsigned short digit; 
6. // ... 
7. #endif 

PYLONG_BITS_IN_DIGIT 是一個宏，如果你的機(jī)器是 64 位的，那么它會被定義為 30，32 位機(jī)器則會被定義為 15。

而我們的機(jī)器現(xiàn)在基本上都是 64 位的，所以 PYLONG_BITS_IN_DIGIT會等于 30，因為 digit 等價于 uint32_t(unsigned int)，所以它是一個無符號 32 位整型。

所以 ob_digit 這個數(shù)組是一個無符號 32 位整型數(shù)組，長度為 1。當(dāng)然這個數(shù)組具體多長則取決于你要存儲的 Python 整數(shù)有多大，因為 C 中數(shù)組的長度不屬于類型信息，你可以看成是長度 n，而這個 n 是多少要取決于你的整數(shù)大小。顯然整數(shù)越大，這個數(shù)組就越長，那么占用空間就越大。

為了說明 256 是如何存放在 ob_digit 里的，我們來簡化下，這里假如 ob_digit 這個數(shù)組是一個無符號 8 位整型數(shù)組，8 位二進(jìn)制，最大只能表示 255，我們要表示 256，那就只能再申請一個 8 位，也許你認(rèn)為再申請一個 8 位來表示 1，其實(shí)不是的，是使用一個新的 8 位整數(shù)來模擬更高的位，如下所示：

1. 255 = [255] 
2. 256 = [1,1] 

256 = [1,1] 的形式也不是真實(shí)情況，為了你理解，先這樣寫，它表達(dá)的意思就是 256 = 1 + 1 * (2^8 - 1) = 1 + 1 * 255 = 256。

也就是說 ob_digit 表示 x 進(jìn)制數(shù)，ob_digit[0] 是低位，ob_digit[1] 是高位，具體 x 是多少，取決于 ob_digit 的類型，這里 8 位，就是 255 進(jìn)制。

剛才提到 256 = [1,1] 的形式也不是真實(shí)情況，因為 PyLongObject 不僅僅是為了存儲大整數(shù)，也需要參與運(yùn)算，具體怎么運(yùn)算呢，那就是 ob_digit 逐位相加即可。

既然是相加，即又可能溢出，比如 [255 , 1] + [255, 1] = [510,2]

這里的 510 就超出了 8 位，為了簡化處理，只要我們不用滿 8 位，就不會溢出，也就是說，比如說只用 7 位，那最大也就是 [127,...] + [127,...] = [254,...] 也就不會溢出了。

到這里，你會明白，為什么 digit 雖然是無符號 32 位整數(shù)，卻只使用 30 位了吧：

1. #if PYLONG_BITS_IN_DIGIT == 30 
2. typedef uint32_t digit; 
3. // ... 
4. #elif PYLONG_BITS_IN_DIGIT == 15 
5. typedef unsigned short digit; 
6. // ... 
7. #endif 

聰明的你，可能會問，31 位就可以保證不溢出，為啥犧牲兩位，用 30 位，答案我也不知道，可能是因為 64 是 32 的兩倍， 30 也是 15 的兩倍，這樣看起來更舒服吧。

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

所以 Python 在比較兩個整型的大小時，會先比較 ob_size，如果 ob_size 不一樣則可以直接比較出大小來。

總結(jié)一下，就是當(dāng) PYLONG_BITS_IN_DIGIT == 30 的時候，整數(shù) = ob_digit[0] + ob_digit[1] * 2 ** 30 + ob_digit[2] * 2 ** 60 + ...

2、整數(shù)占用內(nèi)存大小

理解了這一點(diǎn)，我們再看一下這個結(jié)構(gòu)體：

1. typedef struct { 
2.     int ob_refcnt;    //引用計數(shù) 
3.     struct _typeobject *ob_type; //變量類型 
4.     int ob_size;       //用來指明變長對象中一共容納了多少個元素 
5.     digit ob_digit[1]; //digit類型的數(shù)組,長度為1 
6. } PyLongObject; 

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

現(xiàn)在的你不難理解以下結(jié)果：

3、整數(shù)池

此外 Python 中的整數(shù)屬于不可變對象，運(yùn)算之后會創(chuàng)建新的對象:

1. >>> a = 300 
2. >>> id(a) 
3. 140220663619152 
4. >>> a += 1 
5. >>> id(a) 
6. 140220663619408 
7. >>> 

這樣就勢必會有性能缺陷，因為程序運(yùn)行時會有對象的創(chuàng)建和銷毀，就是涉及內(nèi)存的申請和垃圾回收，一個常用的手段就是使用對象池，將頻率高的整數(shù)預(yù)先創(chuàng)建好，而且都是單例模式，需要使用時直接返回。

小整數(shù)對象池的實(shí)現(xiàn)位于 pycore_interp.h[3] 中：

驗證一下：

1. >>> a = -6 
2. >>> b = -6 
3. >>> a is b 
4. False 
5. >>> a = -5 
6. >>> b = -5 
7. >>> a is b 
8. True 
9. >>> a = 256 
10. >>> b = 256 
11. >>> a is b 
12. True 
13. >>> a = 257 
14. >>> b = 257 
15. >>> a is b 
16. False 
17. >>> 

不同的版本可能會不同，我這里 Python3.8，區(qū)間為 [-5,257)。

4、整數(shù)加減法

有了前面的鋪墊，現(xiàn)在我們來看下 Python 中大整數(shù)是如何相加的，源代碼 longobject.c : long_add 函數(shù)[4]

可以看到 long_add 根據(jù) ob_size 的正或負(fù)來調(diào)用 x_add 或 x_sub。

現(xiàn)在看一下 x_add 的源代碼：

可以看到，Python 大整數(shù)的相加就是底層數(shù)組的相加，當(dāng)然還會涉及到進(jìn)位等操作：

1. for (i = 0; i < size_b; ++i) { 
2.  carry += a->ob_digit[i] + b->ob_digit[i]; 
3.  z->ob_digit[i] = carry & PyLong_MASK; 
4.  carry >>= PyLong_SHIFT; 
5. } 

x_sub 的源代碼：

4、整數(shù)乘法

Python 整數(shù)乘法使用的是 Karatsuba multiplication[5] 算法進(jìn)行的大數(shù)乘法，感興趣的可以研究一下。

最后的話

源碼之下無秘密，看源碼會比較辛苦，卻可以學(xué)到精髓和本質(zhì)，本文通過源碼逐層展開，帶你了解了下 Python 整數(shù)對象的實(shí)現(xiàn)、整數(shù)內(nèi)存大小的計算，整數(shù)池，整數(shù)加減法源碼，相信你已經(jīng)知道了 Python 是如何實(shí)現(xiàn)整數(shù)想加而不溢出的。如果有收獲，還請點(diǎn)在、點(diǎn)贊、轉(zhuǎn)發(fā)，感謝一路的支持和陪伴。

原文鏈接：https://mp.weixin.qq.com/s?__biz=MzU0OTg3NzU2NA==&mid=2247487960&idx=1&sn=9be99d54fb47fdd2f6fc6f8b9c37e3f7&chksm=fba8738bccdffa9dafbcc0055c0079fe1b1a50622d0607fee183fc00d1a68abb99e1db4e943f&mpshare=1&