[[418532]]

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

要想了解這個，那就需要看 Python 的源代碼[1]，Python中的整數(shù)底層對應的結構體是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 展開，結構體中的變量我已經(jīng)作了注釋： 

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

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

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

那么下面的重點就在這個 ob_digit 數(shù)組了，我們看看 Python 中整數(shù)對應的值，比如 256，是怎么放在這個數(shù)組里面的。不過首先我們要看看這個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。

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

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

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

255 = [255] 
256 = [1,1] 

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

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

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

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

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

到這里，你會明白，為什么 digit 雖然是無符號 32 位整數(shù)，卻只使用 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 的兩倍，這樣看起來更舒服吧。

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

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

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

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

理解了這一點，我們再看一下這個結構體： 

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

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

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

 

3、整數(shù)池

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

>>> a = 300 
>>> id(a) 
140220663619152 
>>> a += 1 
>>> id(a) 
140220663619408 
>>> 

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

小整數(shù)對象池的實現(xiàn)位于 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，區(qū)間為 [-5,257)。

4、整數(shù)加減法

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

 

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

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

 

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

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、整數(shù)乘法

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

最后的話

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