简单高精度加法


前言(可了解):C++语言里最大的64位整数类型有long long__int64两种类型(VC还支持__int64),它们最多只能容纳不到20位数字,标准输出方式有printf("%lld", x)printf("%I64d", x)cout<<x三种方式。但没有一种定义和输出方式的组合,可以兼容所有的平台和编译器,例如long long的定义方式不受平台限制,但__int64只能用于Windows平台而不能用于Linux平台;"%lld"只能用于Linux i386平台,"%I64d"只能用于Windows平台。

思路

C++现有的数据类型无法满足过大位数的计算需要,你可以考虑使用数组的形式来保存,首先读取a,b这么大的数时需要用字符串类型读取,然后再将字符串转化为整数数组。转化方式为该数字字符减去“0”或者“48”即可。该数组的每一个元素对应一位十进制数,由其下标顺序指明位序号,存储顺序为自右向左逆序。
对整型数组a[]和b[]按算术运算规则进行运算之前,需要用变量记录两组整数数组的最大元素个数,即最大位数,这是因为由于高精度运算的结果可能使得数据长度发生增减(最高位进位)。

AC代码

//简单高精度加法 
#include <iostream>
#define MAXN 1001
using namespace std;
int add(int x[], int y[], int z[], int len)
{
    for(int i=0; i<len; ++i)             //从下标0开始逐位相加到len-1
    {
        z[i] += x[i] + y[i];             //相加结果存到z[],注意是+=
        for(int j=i; j<len; ++j)
        {
            if(z[j]>=10)                 //如果当前位数的值超过了10,则要进位处理 
            {
                z[j+1] += z[j]/10;       //此处若改为++z[j+1],效率更高,注意是+=
                z[j] -= 10;              //或者是z[j]%=10,但速度稍慢 
                if(z[len]>0)             //最高位如果进位了,则最大位数加1 
                len++;
                if(z[j+1]<10)            //小优化 
                break;
            }
        }
    }
    return len;                          //返回位数 
}
void init(int x[], string str, int len)  //字符串转整型数组
{
    for(int i=0; i<len; i++)             //倒序转换 
    x[len-i-1] = str[i]-'0';
}
void output(int z[], int len)            //输出相加的结果 
{
    for(int i=len-1; i>=0; i--)
    cout<<z[i];
    cout<<endl;
}
int main(void)
{
    string str1, str2;
    while(cin>>str1>>str2)
    {
        int a[MAXN] = {0}, b[MAXN] = {0}, z[MAXN] = {0};  //初始化为0 
        int la, lb, len;
        la = str1.size();
        lb = str2.size();
        init(a, str1, la);           //初始化为整型数组 
        init(b, str2, lb);
        if(la>=lb)                   //确定a和b的最大位数 
        len = add(a, b, z, la);      //取最长位数la 
        else 
        len = add(b, a, z, lb);      //取最长位数lb 
        output(z, len);              //功德圆满
    }
    return 0;
}

之前犯傻想用一波STL中的atoi(str.c_str())把串转换为整型,结过人家本来就是大数...变量存不下。害我找了半天问题在哪。

声明:Kira's Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 简单高精度加法


Truth is I missed those summer days