[[418532]]

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

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

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

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

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

那么下面的重點(diǎn)就在這個(gè) ob_digit 數(shù)組了，我們看看 Python 中整數(shù)對(duì)應(yīng)的值，比如 256，是怎么放在這個(gè)數(shù)組里面的。不過首先我們要看看這個(gè)digit 是個(gè)什么類型，它同樣定義在 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 是一個(gè)宏，如果你的機(jī)器是 64 位的，那么它會(huì)被定義為 30，32 位機(jī)器則會(huì)被定義為 15。

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

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

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

255 = [255] 
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í)情況，因?yàn)?PyLongObject 不僅僅是為了存儲(chǔ)大整數(shù)，也需要參與運(yùn)算，具體怎么運(yùn)算呢，那就是 ob_digit 逐位相加即可。

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

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

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

#if PYLONG_BITS_IN_DIGIT == 30 
typedef uint32_t digit; 
// ... 
#elif PYLONG_BITS_IN_DIGIT == 15 
typedef unsigned short digit; 
// ... 
#endif 

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

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

所以 Python 在比較兩個(gè)整型的大小時(shí)，會(huì)先比較 ob_size，如果 ob_size 不一樣則可以直接比較出大小來。

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

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

理解了這一點(diǎn)，我們?cè)倏匆幌逻@個(gè)結(jié)構(gòu)體： 

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

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

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

 

3、整數(shù)池

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

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

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

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

 

驗(yàn)證一下： 

>>> 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 
>>> 

不同的版本可能會(huì)不同，我這里 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)然還會(huì)涉及到進(jìn)位等操作： 

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] 算法進(jìn)行的大數(shù)乘法，感興趣的可以研究一下。

最后的話

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