C/C++高精度算法的实现分享！

做ACM题的时候，经常遇到大数的加减乘除，乘幂，阶乘的计算，这时给定的数据类型往往不够表示最后结果，这时就需要用到高精度算法。高精度算法的本质是把大数拆成若干固定长度的块，然后对每一块进行相应的运算。这里以考虑4位数字为一块为例，且输入的大数均为正整数（也可以考虑其他位，但要注意在每一块进行相应运算时不能超出数据类型的数值范围；有负整数的话读入时判断一下正负号在决定运算）。

1. 高精度加法

以3479957928375817 + 897259321544245为例：

C语言实现代码如下：

  #include <stdio.h>  #include <stdlib.h>  #include <string.h>  #define N 200    //整数乘幂运算函数  int Pow(int a, int b)  {    int i = 0, result = 1;    for(i = 0; i < b; ++i)    {      result *= a;    }    return result;  }      //High Precision Of Addition  int main()  {    char stra[N], strb[N];   //字符串数组，以字符形式储存两个大数；    int i = 0, step = 4, carry = 0; //step表示块长，carry为进位位；    int lengtha, lengthb, maxlength, resultsize;  //maxlength表示stra和strb二者长度较大的那个；    int numa[N], numb[N],numc[N];  //依次储存被加数，加数，和；    memset(numa, 0, sizeof(numa));    memset(numb, 0, sizeof(numb));    memset(numc, 0, sizeof(numc));     //初始化为零；    scanf("%s%s", stra, strb);    lengtha = strlen(stra);    lengthb = strlen(strb);   //计算两个大数的长度    //字符数字转为四位一块的整数数字    for(i = lengtha-1; i >= 0; --i)    {      numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);    }    for(i = lengthb-1; i >= 0; --i)    {      numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);    }    maxlength = lengtha > lengthb ? lengtha : lengthb;      //逐块相加，并进位    for(i = 0; i <= maxlength/step; ++i)    {      numc[i] = (numa[i] + numb[i])%Pow(10, step) + carry;  //计算和      carry = (numa[i] + numb[i])/Pow(10, step); //计算进位    }      //计算最后和的块的总数    resultsize = numc[maxlength/step] > 0 ? maxlength/step : maxlength/step - 1;    printf("%d", numc[resultsize]);    for(i = resultsize-1; i >= 0; --i)    {      printf("%04d", numc[i]);  //右对齐，补零输出；    }    printf("n");    return 0;  }  

2. 高精度减法

与加法类似，不同的是要注意正负号和显示位数的变化。以99999037289799 – 100004642015000为例：

先判断被减数和减数哪个大，显然这里减数大，故输出结果为负数。在用大数减去小数，（若某一块相减为负数，则要向高位块借位）如下表

C语言实现代码如下：

  #include <stdio.h>  #include <stdlib.h>  #include <string.h>  #define N 200    //整数乘幂运算函数  int Pow(int a, int b)  {    int i = 0, result = 1;    for(i = 0; i < b; ++i)    {      result *= a;    }    return result;  }    //High Precision Of Subtraction  int main()  {    char stra[N], strb[N];   //字符串数组，以字符形式储存两个大数；    int i = 0, step = 4, borrow = 0, mark = 0; //step表示块长，borrow为借位位, mark为结果符号位；    int lengtha, lengthb, maxlength, resultsize;  //maxlength表示stra和strb二者长度较大的那个；    int numa[N], numb[N],numc[N], *maxnum, *minnum;  //依次储存被减数，减数，和；    memset(stra, 0, sizeof(stra));    memset(strb, 0, sizeof(strb));    memset(numa, 0, sizeof(numa));    memset(numb, 0, sizeof(numb));    memset(numc, 0, sizeof(numc));     //初始化为零；    scanf("%s%s", stra, strb);    lengtha = strlen(stra);    lengthb = strlen(strb);   //计算两个大数的长度    maxlength = lengtha >= lengthb ? lengtha : lengthb;      //字符数字转为四位一块的整数数字    for(i = lengtha-1; i >= 0; --i)    {      numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);    }    for(i = lengthb-1; i >= 0; --i)    {      numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);    }      //找出较大的数    maxnum = numa;    minnum = numb;    mark = 1;    for(i = (maxlength-1)/step; i >= 0; --i)    {      if(numa[i] > numb[i])      {        maxnum = numa;        minnum = numb;        mark = 1;        break;      }      else if(numa[i] < numb[i])      {        maxnum = numb;        minnum = numa;        mark = -1;        break;      }    }      //逐块相减，并借位    for(i = 0; i <= maxlength/step; ++i)    {      numc[i] = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)%Pow(10,step);  //计算差      borrow = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)/Pow(10, step) - 1; //计算借位    }      //计算最后和的块的总数    resultsize = maxlength/step;    while(!numc[resultsize])  --resultsize;    printf("%d", mark*numc[resultsize]);    for(i = resultsize-1; i >= 0; --i)    {      printf("%04d", numc[i]);  //右对齐，补零输出；    }    printf("n");    return 0;  }    

3. 高精度乘法

乘法可以看作是乘数每一位与被乘数相乘后再相加，以4296556241 x 56241为例：

• 1
• 2
• 3
• 下一页