大整数运算

大整数存储

在C语言中若要计算A+B，如果A和B的在范围int(或long)范围内，那很容易就可以写出来，但是若A和B是有着1000个位数的整数就没办法用数据类型来表示了，这时只能去模拟加减乘除的运算过程。此外，大整数又称高精度整数，其含义就是用基本数据类型无法存储其精度的整数。

若要计算大整数首先要先把需要计算的大整数存储下来，对于存储大整数使用数据即可，例如定义int型数组d[1000]，那么这个数组中的一位就代表整数的每一位，不过这就产生一个问题，当我们把整数例如：258369当字符串用%s读入数组S时，则S[0]=2,S[1]=5,S[2]=8……S[5]=9此时若两数相加需要进位则需要数组集体向后移一位才可以进位十分麻烦，所以我们将读入之后需将数组翻转一下及：S[0]=9,S[1]=6,S[2]=3……S[5]=2

而为了方便获取大整数我们首先定义一个int类型的变量len来记录大整数的长度，并和数组 d 组合成结构体并利用构造函数为结构体初始化，代码如下

struct bign{
    int d[1000];                 //定义数组用来存储大整数
    int len;                     //用来存储大整数的位数
    bign(){
        memset(d, 0, sizeof(d)); //初始化数据b全部存储为0
        len = 0;                 //初始化大整数长度
    }
};

而输入大整数时，一般先用字符串读入，然后再把字符串另存为bing结构体，由于使用 char 数组读入，所以要将翻转一下然后在赋值给结构体中的 d数组：

bign change(shar str[]){  //将大整数存入bign
    bign a;
    int i;
    a.len = strlen(str);   //bign的长度就是字符串的长度
    for(i = 0; i < a.len; i++)
        a.d[i] = str[a.len - i -1] - '0';   //逆着赋值
    return a;
}

若需要比较两个大整数的大小，则首先判断两者的len大小，如果不相等，则len长的大；如果相等，则从高位到低位一次比较，直到某一位不等时就可以判断出两数的大小，代码如下：

int compare(bign a, bign b){   //比较a和b的大小
    if(a.len > b.len) return 1;   //a大返回 1
    else if(a.len < b.len) return -1;  //b大返回 -1
    else{
        int i;
        for(i = a.len - 1; i >= 0; i--){
            if(a.d[i] > b.d[i]) return 1;       //a大返回 1
            else if(a.b[i] < b.d[i]) return -1; //b大返回 -1
        }
        return 0;  //两数相等返回 0
    }
}

大整数的四则运算

高精度加法

若将153+86看做两个大整数相加，我按照小学的竖式进行相加如下：

高精度加法

1. 3 + 6 = 9，个位取作为该结果 9 ，十位取 0作为进位。
2. 5 + 8 = 13，再加上进位0还为13，然后个位取3作为结果，十位1作为进位。
3. 1 + 0 = 1 ，再加上进位1，然后取个位2为结果

将上述步骤归纳可得出如下代码：

bign add(bign a, bign b){   //高精度a+b
    bign c;
    int carry = 0;    //表示进位
    int i;
    for(i = 0; i<a.len || i<b.len; i++){ //以较长的为界限
        int temp = a.d[i] + b.len[i] + carry;   //两数相加并加上进位
        c.d[c.len++] = temp % 10;   //个位为该位结果
        carry = temp / 10;      //十位为进位
    }
    if(carry !=0 ) c.d[c,len++] = carry;    //软工最后进位不为零则直接赋值给最高位
    return c;
}

完整高精度A+B代码如下：

#include<stdio.h>
struct bign{
    int d[1000];                 //定义数组用来存储大整数
    int len;                     //用来存储大整数的位数
    bign(){
        memset(d, 0, sizeof(d)); //初始化数据b全部存储为0
        len = 0;                 //初始化大整数长度
    }
};
bign change(shar str[]){  //将大整数存入bign
    bign a;
    int i;
    a.len = strlen(str);   //bign的长度就是字符串的长度
    for(i = 0; i < a.len; i++)
        a.d[i] = str[a.len - i -1] - '0';   //逆着赋值
    return a;
}
bign add(bign a, bign b){   //高精度a+b
    bign c;
    int carry = 0;    //表示进位
    int i;
    for(i = 0; i<a.len || i<b.len; i++){ //以较长的为界限
        int temp = a.d[i] + b.len[i] + carry;   //两数相加并加上进位
        c.d[c.len++] = temp % 10;   //个位为该位结果
        carry = temp / 10;      //十位为进位
    }
    if(carry !=0 ) c.d[c,len++] = carry;    //软工最后进位不为零则直接赋值给最高位
    return c;
}
void print(bign a){    //输出bign
    int i;
    for(i = a.len-1; i >=0; i--)
        printf("%d",a.d[i]);
}

main()
{
    char s1[1000],s2[1000];
    scanf("%s%s",s1,s2);
    bign a = change(s1);
    bign b = change(s2);
    print(add(a,b));
}

高精度减法

若将 169-96 看做两个大整数减法，我按照小学的竖式进行相加如下：

减法

1. 9-6>0够减，不需要借位，则直接减，结果为：3
2. 6-9<0不够减，向高位1借1，于是改结果为16-9=7
3. 两数最高位均为0，计算结束

将上述步骤归纳可得出如下代码：

bign sub(bign a,bign b){   //高精度A-B
    bign c;
    int i;
    for(i = 0; i<a.len || i<b.len; i++){ //以较长的为界限
        if(a.d[i] < b.d[i]){   //如果不够减
            a.d[i+1] --;       //向高位借位
            a.d[i] += 10;      //当前位+10
        }
        c.d[c.len++] = a.[i] - b.d[i];   //计算当前结果
    }
    while(c.len-1 >= 1 && c.d[c.len -1] == 0)
        c.len -- ;          //去除高位的0，同时若两数相见为0则保留一位0
    return c;
}

若题目涉及的高精度减法A-B<0则利用函数compare()判断一下，若 A<B 则计算 B-A 并输出一个符号即可。

高精度与低精度的乘法

所谓低精度就是可以用基本数据类型存储的数据，而高精度与低精度的乘法就是讲述 bign 与 int 类型的乘法，其做法与小学学的竖式略有不同，若以258 × 25（258看做高精度数据、25看做低精度数据）为例，在计算过程中要把低精度数据25看做一个整体，具体做法如下：

乘法

1. 25×8=200，个位数 0 作为该位的结果，20 作为进位。
2. 25×5=125，再加上进位的 20，结果为145，个位数 5 作为该位结果，14作为进位。
3. 2×25=50，再加上进位的 14，结果为64，个位数 4 作为该位结果，6作为进位。

将上述步骤归纳可得出如下代码：

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

高精度除以低精度

除法计算和小学学的竖式相同，以 1234/7 为例：

除法

1. 1与7比较，不够除，因此该位商为0，余数为1。
2. 余数1与新位2组合成12，12与7比较，够除，商为1,余数为5。
3. 余数5与新位3组合成53，53与7比较，够除，商为7,余数为4。
4. 余数4与新位4组合成44，44与7比较，够除，商为6,余数为2。

将上述步骤归纳可得出如下代码：

bign divde(bign a, bign b, int& r){     //r为余数
    bign c;
    c.len = a.len;         //被除数的每一位和商的每一位是一一对应的，因此先另长度相等
    int i;
    for(i = a.len - 1; i >=0 ; i--){      //从高位开始除
        r = r * 10 + a.d[i];              //和上一位遗留的余数组合
        if(r < b) c.d[i] = 0;             //不够除则为0
        else{
            c.d[i] = r / b ;         //够除则求出商
            r %= b;                  //获得新的余数
        }
    }
    while(c.len -1 >= 1 && c.d[c.len - 1] == 0)
        c.len --;          //去除高位的0，同时若两数相见为0则保留一位0
    return c;
}