大整数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;
}