大数运算（高精度运算）——通用解决方案

核心思想：自定义大数类型（结构体或类），重载运算符。

最简单的大数运算模板：

const int maxn = 1000;
struct Bign
{
    int s[maxn],len;

    Bign()
    {
        memset(s,sizeof(s));
        len = 1;
    }

    Bign operator = (const char* num)
    {
        len = strlen(num);
        for(int i = len-1,j = 0; i>=0; i--) s[j++] = num[i] - '0';
        return *this;
    }

    Bign operator + (const Bign& b)const
    {
        Bign result;
        result.len = 0;

        int c = 0;
        for(int i = 0; i < max(len,b.len); i++)
        {
            if(i < len && i < b.len)
            {
                c += s[i] + b.s[i];
            }
            else
            {
                if(i < len)
                {
                    c += s[i];
                }

                if(i < b.len)
                {
                    c += b.s[i];
                }
            }

            result.s[result.len ++] = c % 10;
            c = c / 10;
        }

        if(c != 0) result.s[result.len ++] = c;

        return result;
    }
};

若用到其他运算，重载其他运算符即可。具体可参照《算法竞赛入门经典——刘汝佳 编著》中的5.2.3 高精度运算类bign

#include<iostream>
#include<cstring>
#define max(a,b) (a>b ? a : b)
#define min(a,b) (a<b ? a : b)

using namespace std;

const int maxn = 1000;
struct Bign
{
    int s[maxn],b.len); i++)
        {
            if(i < len && i < b.len)
            {
                c += s[i] + b.s[i];
            }
            else
            {
                if(i < len)
                {
                    c += s[i];
                }

                if(i < b.len)
                {
                    c += b.s[i];
                }
            }

            result.s[result.len ++] = c % 10;
            c = c / 10;
        }

        if(c != 0) result.s[result.len ++] = c;

        return result;
    }
};

int main()
{
    Bign a;
    a = "123456";

    Bign b;
    b = "123456";

    Bign c = a + b;

    for(int i=0; i<c.len; i++) cout<<c.s[i]<<" ";

    return 0;
}

====================================================================================

《拓展》

参考网站：大数相乘

在如下程序中包含了编程时的大部分思路，不当之处，敬请指正。

#include<iostream>
#include<cstring>
#define max(a,b) (a>b ? a : b) //表达式宏的最外面 最好 用一个括号括起来
#define min(a,b) (a<b ? a : b)

using namespace std;

const int maxn = 1000;
struct Bign //存储 数字的逆序数组 + 长度
{
    int s[maxn],sizeof(s));//头文件是<string.h>或<memory.h>
        len = 0;//没赋值之前没有值，故位数为0
    }


    /*
    赋值运算
    */
    Bign operator = (const char* num)
    {
        len = strlen(num);
        for(int i = len-1,j = 0; i>=0; i--) s[j++] = num[i] - '0'; //逆序存储
        return *this; //需要改变对象自身 （注意与下面的'+'、'-'、'*'、'/'区分）
    }


    /*
    赋值运算
    */
    Bign operator = (const Bign& b){
        len = b.len;

        for(int i=0;i<len;i++){
            s[i] = b.s[i];
        }

        return *this;
    }


    /*
    加法运算
    */
    Bign operator +(const Bign& b)const
    {
        Bign result;
        result.len = 0;

        int c = 0;//进位标志
        for(int i = 0; i < max(len,b.len); i++)
        {
            /*
            if(i < len && i < b.len)
            {
                c += s[i] + b.s[i];
            }
            else
            {
                if(i < len)
                {
                    c += s[i];
                }

                if(i < b.len)
                {
                    c += b.s[i];
                }
            }*/
            //上面的注释部分可以简化为：
            if(i < len) c += s[i]; //如果当前位未超过该数值的最大位数，就加上该数值的当前位。
            if(i < b.len) c += b.s[i];//...

            result.s[result.len ++] = c % 10;
            c = c / 10;
        }

        if(c != 0) result.s[result.len ++] = c;

        return result; //不改变对象自身，而是重建了一个对象。
    }


    /*
    减法运算
    */
    Bign operator -(const Bign& b)const
    {
        Bign a = *this;
        Bign result;

        int c = 0;//上一位的计算向当前位借位了吗
        for(int i=0;i<max(a.len,b.len);i++){

            //给上一位的计算  收拾摊子
            if(c == 1) {//上一位的计算向当前位借位过
                a.s[i] -= 1;
                c = 0;
            }

            //做当前位计算的工作
            if(a.s[i] < b.s[i]){ //当前位的计算需要向更高位借位
                c = 1;
                result.s[result.len ++] = a.s[i] + 10 - b.s[i]; //在此处隐藏着一个小Bug，在高位可能出现多余的0
            }else{
                result.s[result.len ++] = a.s[i] - b.s[i];
            }
        }

        //做完减法之后，高位可能会有多余的0存留
        result.reduceExtraZero();

        return result;
    }

    /*
    去除Bign中高位的多余的0
    */
    void reduceExtraZero(){
        while(len >= 1){
            if(s[len-1] == 0) len --;
            else break;
        }
    }

    /*
    乘法运算：参考网站：http://blog.sina.com.cn/s/blog_7496d1d601010o4e.html
    */
    Bign operator *(const Bign& b) const
    {
        Bign a = *this;
        Bign result;

        result.len = a.len + b.len;
        memset(result.s,sizeof(result.s));//注意一定要进行初始化，否则，虽然程序不会崩溃，但结果会出错。

        if(result.len > maxn) cout<<"结果溢出";
        else{
            cout<<"aaa"<<endl;
            //逐位相乘
            for(int i=0;i<a.len;i++)
            for(int j=0;j<b.len;j++) result.s[i + j] += a.s[i] * b.s[j];

            cout<<"bbb"<<endl;
            //处理进位
            int c = 0;//进位的数值
            for(int i=0;i<result.len;i++){
                int temp = (result.s[i] + c) % 10;
                c = (result.s[i] + c) / 10;
                result.s[i] = temp;
            }
            if(c) result.s[result.len ++] = c;

            cout<<"ccc"<<endl;
            //去除多余的0
            result.reduceExtraZero();

            return result;

            cout<<"eee"<<endl;
        }
    }
};

void print(const Bign& bign){ //可重载输入输出运算符实现
    for(int i = bign.len -1; i >= 0;i --)
        cout << bign.s[i];
}

int main()
{
    Bign a;
    a = "1234578";

    Bign b;
    b = "1234567";

    Bign result;

    result = a + b;
    print(a); cout<<" + "; print(b); cout<<" = "; print(result);
    cout<<endl;

    result = a - b;
    print(a); cout<<" - "; print(b); cout<<" = "; print(result);
    cout<<endl;

    result = a * b;
    cout<<"ddd"<<endl;
    print(a); cout<<" * "; print(b); cout<<" = "; print(result);
    cout<<endl;
    return 0;
}

对上述高精度乘法进行分析如下：

1. 高精度乘法的实现原理

(1)?前期准备

a.将两个因子逆序存入字符串中。

b.初始化结果：

? ? ? ?b1：位数 ——?result.len = a.len + b.len；

解析：

结果的位数最多为两因子位数之和 ? ? ?：result.len = a.len + b.len； 最大的例子:99*99=9791. 2 2 ——>4??...? ? 最少为两因子位数之和减1： 最小的例子:10*10=100. 2 * 2 ——>3

? ? ? ?b2：将各位置0。

(2)?逐位计算

result.s[i + j] = a.s[i]*b.s[j]；

(3)处理进位

现就上一步的方法进行举例：

原数值： 12*26

a = (2,1)

b = (6,2)

? ? ? ? ? ? ? ? result = (12,10,1)

将上一步得到的结果,各位依次为：(12,1)

? ? ? ??故需要使用除10和余10处理进位：结果为(2,1,2)