本次分析基于 CPython 解釋器，python3.x版本
在python2時代，整型有 int 類型和 long 長整型，長整型不存在溢出問題，即可以存放任意大小的整數。在python3后，統一使用了長整型。這也是吸引科研人員的一部分了，適合大數據運算，不會溢出，也不會有其他語言那樣還分短整型，整型，長整型...因此python就降低其他行業的學習門檻了。
那么，不溢出的整型實現上是否可行呢？
不溢出的整型的可行性
盡管在 C 語言中，整型所表示的大小是有范圍的，但是 python 代碼是保存到文本文件中的，也就是說，python代碼中并不是一下子就轉化成 C 語言的整型的，我們需要重新定義一種數據結構來表示和存儲我們新的“整型”。
怎么來存儲呢，既然我們要表示任意大小，那就得用動態的可變長的結構，顯然，數組的形式能夠勝任:
[longintrepr.h]
struct _longobject {
PyObject_VAR_HEAD
int *ob_digit;
};
長整型的保存形式
長整型在python內部是用一個 int 數組( ob_digit[n] )保存值的. 待存儲的數值的低位信息放于低位下標, 高位信息放于高下標.比如要保存 123456789 較大的數字,但我們的int只能保存3位(假設):
ob_digit[0] = 789;ob_digit[1] = 456;ob_digit[2] = 123;
低索引保存的是地位，那么每個 int 元素保存多大的數合適？有同學會認為數組中每個int存放它的上限(2^31 - 1)，這樣表示大數時，數組長度更短，更省空間。但是，空間確實是更省了，但操作會代碼麻煩，比方大數做乘積操作，由于元素之間存在乘法溢出問題，又得多考慮一種溢出的情況。
怎么來改進呢？在長整型的 ob_digit 中元素理論上可以保存的int類型有 32 位，但是我們只保存 15 位，這樣元素之間的乘積就可以只用 int 類型保存即可, 結果做位移操作就能得到尾部和進位 carry 了，定義位移長度為 15：
#define PyLong_SHIFT 15#define PyLong_BASE ((digit)1 << PyLong_SHIFT)#define PyLong_MASK ((digit)(PyLong_BASE - 1))
PyLong_MASK 也就是 0b111111111111111 ,通過與它做位運算 與 的操作就能得到低位數。
有了這種存放方式，在內存空間允許的情況下，我們就可以存放任意大小的數字了。
長整型的運算
加法與乘法運算都可以使用我們小學的豎式計算方法，例如對于加法運算:
| ob_digit[2] | ob_digit[1] | ob_digit[0] | ||
|---|---|---|---|---|
| 加數a | 23 | 934 | 543 | |
| 加數b | + |
學習交流
熱門圖片
猜你喜歡的新聞
新聞熱點  2020-02-16 09:52:44
 2020-02-15 15:53:44
 2020-02-11 22:02:38
 2020-02-11 21:45:12
 2020-02-07 10:36:18
 2020-02-06 12:16:44
疑難解答 |
