大整數BigInterger的簡單入門（vector實作）

什麼是大整數BigInteger?

假設某一數字有1000位，一般這種數字就是就叫BigInteger，這種數字即使使用unsigned long long 類型也無法表示（unsigned long long的最大值：18446744073709551615）

如何處理BigInter？

這個時候我們如何處理這種類型的數字呢？機器不能算，我們可以靠人工來計算， 就是國小生都會的簡單加減乘除四則運算。

這種資料我們一般用一個數組來表示，用char類型(或者C++的string)把一串大整數當做字元串來讀取，然後将這些字元轉換成純數字（-‘0’）,由于我們做加減乘除都是從後往前，是以我們采用倒序存儲的方法，比如 “123456”我們存到數組裡時令

arr[ 0 ] = 6 ,

arr[ 1 ] = 5 ,

arr[ 2 ] = 4 ,

arr[ 3 ] = 3,

arr[ 4 ] = 2 ,

arr[ 5 ] = 1

處理代碼（C++）

void change(string ss, vector<int> &arr) //vector寫在了main函數中，于是用了下引用
{
    for(int i = ss.length()-1; i>=0; i--)
        arr.push_back(ss[i]-'0');
}
           

BigInteger之間的比較

如果整數a的長度大于b，那麼a大于b；反之b大于a

如果a b長度相等，按每一位大小比較

代碼如下

int comp(vector<int> &a, vector<int> &b)
{
    if(a.size() > b.size()) return 1; //a > b
    else if(a.size() < b.size()) return -1;
    else
    {
        for(int i = a.size()-1; i >= 0 ; i--) // 從高位向低位比較
        {
            if(a[i] > b[i]) return 1;
            else if(a[i] < b[i]) return -1;
        }
    }

    return 0; //a = b
}
           

四則運算

負數我就不處理了XD

這裡有個注意點，定義的temp（臨時變量）和carry（進位數）都是int類型的，也就是說如果計算時超過了這個類型最大值就會發生溢出，改用 long long就沒問題了

下面代碼均用int，請注意。

加法

相當于實作普通的豎式加法

vector<int> add(vector<int> a, vector<int> b)
{
    int carry = 0; //進位變量
    vector<int> cc;//答案存儲到該數組中
    for(int i = 0; i< a.size() || i < b.size(); i++)
    {
        if(i >= a.size()) a.insert(a.begin()+i, 0);//如果位數不夠，最前端插一個0
        if(i >= b.size()) b.insert(b.begin()+i, 0);
        int temp = a[i] + b[i] + carry;
        cc.push_back(temp % 10); //目前位的值
        carry = temp /10;// 進位的值
    }
    if(carry != 0)    //最高位有進位時，在最前端插入
        cc.insert(cc.begin()+cc.size(), carry);
    return cc;
}
           

減法

減法也是豎式模拟，實際上并沒有看起來代碼寫的這麼麻煩，隻是vector不如c的數組那麼靈活（但安全性更高）是以多餘步驟比較多

這裡有個vector的坑，end（）指向的是vector最後一個元素的後面，删除高位0的元素是不要忘記這一點

vector<int> sub(vector<int> a, vector<int> b)
{
    vector<int> cc;
    for(int i = 0; i< a.size() || i< b.size(); i++)
    {
        if(i >= a.size()) a.insert(a.begin()+i, 0);
        if(i >= b.size()) b.insert(b.begin()+i, 0);

        if(a[i] < b[i])
        {
            a[i+1]--;
            a[i] += 10;
        }
        cc.push_back(a[i] - b[i]);
    }

    while(cc[cc.size()-1] == 0 && cc.size() > 1)
        cc.erase(cc.end()-1);

    
    return cc;
}
           

乘法（BigInteger X int）

實作Biginteger 與 int 的乘法，令BigInteger的第一位與int相乘，取個位數作為本位的值，其餘值進位，下一位做乘法後再加上進位的值，直到數組内部數字全部乘完畢，将最後的進位作為最高位。

vector<int> multi(vector<int> a, int b)
{
    vector<int> cc;
    int carry = 0; //進位數字
    for(int i = 0; i< a.size(); i++)
    {
        int temp = a[i] * b + carry;
        cc.push_back(temp %10);
        carry = temp / 10;
    }
    while(carry != 0)
    {
        cc.push_back(carry%10);
        carry /= 10;
    }
    return cc;
}
           

除法（BigInteger / int）

除法和豎式的除法也基本相同，是以要從最高位開始往最低位除。

先拿出最高位，除以 除數，得到該位結果，對除數取餘，乘10加到次高位上，然後這樣反複作除，直到最低位除以除數後餘數就丢掉

vector<int> divide(vector<int> a, int b)
{
    vector<int> cc;
    reverse(a.begin(), a.end()); //反轉數組
    int carry = 0;
    for(int i = 0; i<a.size(); i++)
    {
        int temp = a[i] + carry *10;
        cc.push_back(temp / b);
        carry = temp % b;
    }
    //循環結束後carry的值就是餘數
    while(cc[0] == 0)
    {
        cc.erase(cc.begin());
    }

    return cc;
}