大整数运算

一、定义、赋值、比较、输出
1、大整数的结构体

struct bign {
    int d[1000];
    int len;
    bign() {
        memset(d, 0, sizeof(d));
        len = 0;
    }
};

2、逆着赋值（先用字符串读入，再把字符串另存值bign结构体）
思想：1、生成结构体 2、赋值len 3、for逆着赋值

bign change(char str[]) {
    bign a;
    a.len = strlen(str);
    for (int i = 0;i < a.len;++i) {
        a.d[i] = str[a.len - i - 1] - '0';
    }

    return a;
}

3、比较两个bign变量大小
思想：1、先比较长度，长度不同则以长的为大 2、长度相同，则从高到低比较

int compare(bign a, bign b) {
    if (a.len > b.len)  return 1;   //a大
    else if (a.len < b.len) return -1;  //b大
    else {
        for (int i = a.len - 1;i >= 0;--i) {    //從高到低比较
            if (a.d[i] > b.d[i])    return 1;   //只要有一位a大，则a大
            else if (a.d[i] < b.d[i]) return -1;    //只要有一位b大，则b大
        }
        return 0;       //两数相等
    }
}

二、四则运算（高精度加法，高精度减法，高精度与低精度乘法，高精度与低精度除法）
1、加法
思想：其中一位加法，改为上的两个数字和进位相加，得到的结果个位数作为该位的结果，取十位数作为进位

bign add(bign a, bign b) {
    bign c;
    int carry = 0;  //carry是进位
    for (int i = 0;i < a.len || i < b.len;++i) {    //以较长为界限
        int temp = a.d[i] + b.d[i] + carry; //两个对应为与进位相加
        c.d[len++] = temp % 10; //个位数为结果
        carry = temp / 10;  //十位数位进位
    }
    if (carry != 0) {
        c.d[len++] = carry;
    }
    return c;
}

注意：
（1）以上写法都是非负整数
（2）如果有一方式负数，可以再转换数组这一步去掉其负号，然后采用高精度减法
（3）如果两个都是负数，就都去掉负号，然后高精度加法，最后再加上负号

2、减法
思想：对某一步，比较被减位和减位，如果不够减，则令被减位的高位减1，被减位加10再进行减法；
如果够减，则直接减。
最后一步要注意减法后高位可能有多余的0，要五十他们，但也要保证结果至少有一位数

bign sub(bign a, bign b) {
    bign c;
    for (int i = 0;i < a.len || b.len;i++) {
        if (a.d[i] < b.d[i]) {
            a.d[i + 1]--;   //向高位借位
            a.d[i] += 10;   //当前位加10
        }
        c.d[len++] = a.d[i] - b.d[i];   //减法结果为当前位结果
    }
    whilw(c.len - 1 >= 1 && c.[c.len - 1] == 0) {
        c.len--;    //去除高位的0，同时至少保留一位最低位
    }
    return c;
}

注意：
1、使用sub函数需要比较两个数大小，如果被减数小于减数，
交换两个变量
输出符号
再使用sub函数

3、高精度与低精度乘法
思想：去bign某位与Int整体相乘，再与进位相加，所得结果的个位数作为该位结果，高位部分作为新的进位

bign multi(bign a, bign b) {
    bign c;
    int carry = 0;  //进位
    for (int i = 0;i < a.len;i++) {
        int temp = a.d[i] * b + carry;  
        c.d[len++] = temp % 10; //个位作为该位的结果
        carry = temp / 10;  //高部分作为新的进位
    }
    while (carry != 0) {
        c.d[len++] = carry % 10;    //和加法不一样，乘法的进位可能不止一位，需要用while
        carry /= 10;
    }
    return c;
}

注意：
如果a和b中存在负数，需要先记录负号，然后取绝对值进入函数

4、高精度与低精度除法
算法思想：
1、得出某一步的步骤：上一步的余数乘以10加上该步的位，得到该步临时的被除数，
2、将其与除数比较，如果不够除，则该位的商为0，如果够除，则商为对应的商，余数为对应的余数
3、最后一步要注意减法后高位可能有多余的0，要忽视他们，但也要保证结果至少有一位

bign divide(bign a, bign b,int & r) {   //高精度除法，r为余数
    bign c;
    c.len = a.len;  //被除数的每一位和商的每一位是一一对应的，因此先令长度相等
    for (int i a.len - 1;i >= 0;--i) {
        r = r * 10 + a.d[i];
        if (r < b) c.d[i] = 0;  //不够除
        else{   //够除
            c.d[i] = r / b; //商
            r = r % b;  //获得新的余数
        }
    }

    while (c.len - 1 >= 1 && c.d[len - 1] == 0) {
        c.len--;    //取出高位的0，同时至少保留一位最低位
    }
    return c;
}

注意：
1、很多题目要求得出商和余数，但只能返回一个值，所以把余数作为引用，或者作为全局变量