摘要：前言本次分析基于解釋器，版本在時(shí)代，整型有類型和長(zhǎng)整型，長(zhǎng)整型不存在溢出問題，即可以存放任意大小的整數(shù)。在后，統(tǒng)一使用了長(zhǎng)整型。

本次分析基于 CPython 解釋器，python3.x版本

在python2時(shí)代，整型有 int 類型和 long 長(zhǎng)整型，長(zhǎng)整型不存在溢出問題，即可以存放任意大小的整數(shù)。在python3后，統(tǒng)一使用了長(zhǎng)整型。這也是吸引科研人員的一部分了，適合大數(shù)據(jù)運(yùn)算，不會(huì)溢出，也不會(huì)有其他語言那樣還分短整型，整型，長(zhǎng)整型...因此python就降低其他行業(yè)的學(xué)習(xí)門檻了。

那么，不溢出的整型實(shí)現(xiàn)上是否可行呢？

盡管在 C 語言中，整型所表示的大小是有范圍的，但是 python 代碼是保存到文本文件中的，也就是說，python代碼中并不是一下子就轉(zhuǎn)化成 C 語言的整型的，我們需要重新定義一種數(shù)據(jù)結(jié)構(gòu)來表示和存儲(chǔ)我們新的“整型”。

怎么來存儲(chǔ)呢，既然我們要表示任意大小，那就得用動(dòng)態(tài)的可變長(zhǎng)的結(jié)構(gòu)，顯然，數(shù)組的形式能夠勝任:

[longintrepr.h]
struct _longobject {
    PyObject_VAR_HEAD
    int *ob_digit;
};

長(zhǎng)整型在python內(nèi)部是用一個(gè) int 數(shù)組( ob_digit[n] )保存值的. 待存儲(chǔ)的數(shù)值的低位信息放于低位下標(biāo), 高位信息放于高下標(biāo).比如要保存 123456789 較大的數(shù)字,但我們的int只能保存3位(假設(shè)):

ob_digit[0] = 789;
ob_digit[1] = 456;
ob_digit[2] = 123;

低索引保存的是地位，那么每個(gè) int 元素保存多大的數(shù)合適？有同學(xué)會(huì)認(rèn)為數(shù)組中每個(gè)int存放它的上限(2^31 - 1)，這樣表示大數(shù)時(shí)，數(shù)組長(zhǎng)度更短，更省空間。但是，空間確實(shí)是更省了，但操作會(huì)代碼麻煩，比方大數(shù)做乘積操作，由于元素之間存在乘法溢出問題，又得多考慮一種溢出的情況。

怎么來改進(jìn)呢？在長(zhǎng)整型的 ob_digit 中元素理論上可以保存的int類型有 32 位，但是我們只保存 15 位，這樣元素之間的乘積就可以只用 int 類型保存即可, 結(jié)果做位移操作就能得到尾部和進(jìn)位 carry 了，定義位移長(zhǎng)度為 15：

#define PyLong_SHIFT  15
#define PyLong_BASE ((digit)1 << PyLong_SHIFT)
#define PyLong_MASK ((digit)(PyLong_BASE - 1))

PyLong_MASK 也就是 0b111111111111111 ,通過與它做位運(yùn)算 與 的操作就能得到低位數(shù)。

有了這種存放方式，在內(nèi)存空間允許的情況下，我們就可以存放任意大小的數(shù)字了。

加法與乘法運(yùn)算都可以使用我們小學(xué)的豎式計(jì)算方法，例如對(duì)于加法運(yùn)算:

為方便理解，表格展示的是數(shù)組中每個(gè)元素保存的是 3 位十進(jìn)制數(shù)，計(jì)算結(jié)果保存在變量z中，那么 z 的數(shù)組最多只要 size_a + 1 的空間（兩個(gè)加數(shù)中數(shù)組較大的元素個(gè)數(shù) + 1），因此對(duì)于加法運(yùn)算，可以這樣來處理:

[longobject.c]
static PyLongObject * x_add(PyLongObject *a, PyLongObject *b) {
    int size_a = len(a), size_b = len(b);
    PyLongObject *z;
    int i;
    int carry = 0; // 進(jìn)位
    
    // 確保a是兩個(gè)加數(shù)中較大的一個(gè)
    if (size_a < size_b) {
        // 交換兩個(gè)加數(shù)
        swap(a, b);
        swap(&size_a, &size_b);
    }
    
    z = _PyLong_New(size_a + 1);  // 申請(qǐng)一個(gè)能容納size_a+1個(gè)元素的長(zhǎng)整型對(duì)象
    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;                 // 移除低15位, 得到進(jìn)位
    }
    for (; i < size_a; ++i) {                   // 多帶帶處理a中高位數(shù)字
        carry += a->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    z->ob_digit[i] = carry;
    return long_normalize(z);                   // 整理元素個(gè)數(shù)
    
}

這部分的過程就是，先將兩個(gè)加數(shù)中長(zhǎng)度較長(zhǎng)的作為第一個(gè)加數(shù)，再為用于保存結(jié)果的 z 申請(qǐng)空間，兩個(gè)加數(shù)從數(shù)組從低位向高位計(jì)算，處理結(jié)果的進(jìn)位，將結(jié)果的低 15 位賦值給 z 相應(yīng)的位置。最后的 long_normalize(z) 是一個(gè)整理函數(shù)，因?yàn)槲覀?z 申請(qǐng)了 a_size + 1 的空間，但不意味著 z 會(huì)全部用到，因此這個(gè)函數(shù)會(huì)做一些調(diào)整，去掉多余的空間，數(shù)組長(zhǎng)度調(diào)整至正確的數(shù)量，若不方便理解，附錄將給出更利于理解的python代碼。

豎式計(jì)算不是按個(gè)位十位來計(jì)算的嗎，為什么這邊用整個(gè)元素？

豎式計(jì)算方法適用與任何進(jìn)制的數(shù)字，我們可以這樣來理解，這是一個(gè) 32768 (2的15次方) 進(jìn)制的，那么就可以把數(shù)組索引為 0 的元素當(dāng)做是 “個(gè)位”，索引 1 的元素當(dāng)做是 “十位”。

乘法運(yùn)算一樣可以用豎式的計(jì)算方式，兩個(gè)乘數(shù)相乘，存放結(jié)果的 z 的元素個(gè)數(shù)為 size_a + size_b 即可：

這里需要主意的是，當(dāng)乘數(shù) b 用索引 i 的元素進(jìn)行計(jì)算時(shí)，結(jié)果 z 也是從 i 索引開始保存。先創(chuàng)建 z 并初始化為 0，這 z 上做累加操作，加法運(yùn)算則可以利用前面的 x_add 函數(shù)：

// 為方便理解，會(huì)與cpython中源碼部分稍有不同
static PyLongObject * x_mul(PyLongObject *a, PyLongObject *b)
{
    int size_a = len(a), size_b = len(b);
    PyLongObject *z = _PyLong_New(size_a + size_b);
    memset(z->ob_digit, 0, len(z) * sizeof(int)); // z 的數(shù)組清 0
    
    for (i = 0; i < size_b; ++i) {
        int carry = 0;          // 用一個(gè)int保存元素之間的乘法結(jié)果
        int f = b->ob_digit[i]; // 當(dāng)前乘數(shù)b的元素
        
        // 創(chuàng)建一個(gè)臨時(shí)變量，保存當(dāng)前元素的計(jì)算結(jié)果，用于累加
        PyLongObject *temp = _PyLong_New(size_a + size_b);
        memset(temp->ob_digit, 0, len(temp) * sizeof(int)); // temp 的數(shù)組清 0
        
        int pz = i; // 存放到臨時(shí)變量的低位
        
        for (j = 0; j < size_a; ++j) {
            carry = f * a[j] + carry;
            temp[pz] = carry & PyLong_MASK;  // 取低15位
            carry = carry >> PyLong_SHIFT;  // 保留進(jìn)位
            pz ++;
        }
        if (carry){     //  處理進(jìn)位
            carry += temp[pz];
            temp[pz] = carry & PyLong_MASK;
            carry = carry >> PyLong_SHIFT;
        }
        if (carry){
            temp[pz] += carry & PyLong_MASK;
        }
        temp = long_normalize(temp);
        z = x_add(z, temp);
    }
    
    return z
    
}

這大致就是乘法的處理過程，豎式乘法的復(fù)雜度是n^2，當(dāng)數(shù)字非常大的時(shí)候（數(shù)組元素個(gè)數(shù)超過 70 個(gè)）時(shí)，python會(huì)選擇性能更好，更高效的 Karatsuba multiplication 乘法運(yùn)算方式，這種的算法復(fù)雜度是 3nlog3≈3n1.585，當(dāng)然這種計(jì)算方法已經(jīng)不是今天討論的內(nèi)容了。有興趣的小伙伴可以去了解下。

要想支持任意大小的整數(shù)運(yùn)算，首先要找到適合存放整數(shù)的方式，本篇介紹了用 int 數(shù)組來存放，當(dāng)然也可以用字符串來存儲(chǔ)。找到合適的數(shù)據(jù)結(jié)構(gòu)后，要重新定義整型的所有運(yùn)算操作，本篇雖然只介紹了加法和乘法的處理過程，但其實(shí)還需要做很多的工作諸如減法，除法，位運(yùn)算，取模，取余等。

python代碼以文本形式存放，因此最后，還需要一個(gè)將字符串形式的數(shù)字轉(zhuǎn)換成這種整型結(jié)構(gòu):

[longobject.c]
PyObject * PyLong_FromString(const char *str, char **pend, int base)
{
}

這部分不是本篇的重點(diǎn)，有興趣的同學(xué)可以看看這個(gè)轉(zhuǎn)換的過程。

longobject.c

# 例子中的表格中，數(shù)組元素最多存放3位整數(shù)，因此這邊設(shè)置1000
# 對(duì)應(yīng)的取低位與取高位也就變成對(duì) 1000 取模和取余操作
PyLong_SHIFT = 1000
PyLong_MASK = 999

# 以15位長(zhǎng)度的二進(jìn)制
# PyLong_SHIFT = 15
# PyLong_MASK = (1 << 15) - 1

def long_normalize(num):
    """
    去掉多余的空間，調(diào)整數(shù)組的到正確的長(zhǎng)度
    eg: [176, 631, 0, 0]  ==>  [176, 631]
    :param num:
    :return:
    """
    end = len(num)
    while end >= 1:
        if num[end - 1] != 0:
            break
        end -= 1

    num = num[:end]
    return num

def x_add(a, b):
    size_a = len(a)
    size_b = len(b)
    carry = 0

    # 確保 a 是兩個(gè)加數(shù)較大的，較大指的是元素的個(gè)數(shù)
    if size_a < size_b:
        size_a, size_b = size_b, size_a
        a, b = b, a

    z = [0] * (size_a + 1)
    i = 0
    while i < size_b:
        carry += a[i] + b[i]
        z[i] = carry % PyLong_SHIFT
        carry //= PyLong_SHIFT
        i += 1

    while i < size_a:
        carry += a[i]
        z[i] = carry % PyLong_SHIFT
        carry //= PyLong_SHIFT
        i += 1
    z[i] = carry

    # 去掉多余的空間，數(shù)組長(zhǎng)度調(diào)整至正確的數(shù)量
    z = long_normalize(z)

    return z


def x_mul(a, b):
    size_a = len(a)
    size_b = len(b)
    z = [0] * (size_a + size_b)

    for i in range(size_b):
        carry = 0
        f = b[i]

        # 創(chuàng)建一個(gè)臨時(shí)變量
        temp = [0] * (size_a + size_b)
        pz = i
        for j in range(size_a):
            carry += f * a[j]
            temp[pz] = carry % PyLong_SHIFT
            carry //= PyLong_SHIFT
            pz += 1

        if carry:    # 處理進(jìn)位
            carry += temp[pz]
            temp[pz] = carry % PyLong_SHIFT
            carry //= PyLong_SHIFT
            pz += 1

        if carry:
            temp[pz] += carry % PyLong_SHIFT
        temp = long_normalize(temp)
        z = x_add(z, temp)   # 累加

    return z


a = [543, 934, 23]
b = [632, 454]
print(x_add(a, b))
print(x_mul(a, b))