大数的加法与乘法

「大数」的意思就是理论上可以无限长，只要字符串存储的下就可以，远超过 int、long、long long 可以表示的范围的数。

两个大数的加法

基本思路：

两个大数用字符串的形式输入，将字符串对应修改为存放每一位数字的数组，注意是逆序的数组，方便后续进行加法操作。直接对所有位进行加法，然后遍历一遍，有超过 9 的数字就往前进 1，最终再把数组逆序输出即可。

1、两个必要函数的准备

char C1(int x); // 把 0 到 9 转换为 '0' 到 '9'。
int C2(char x); // 相反
// 直接用 switch 就可以了

2、将两个字符数组转换为逆序的整型数组

void char_to_int(int *b,char *a,int t)
{// 把长度为t的字符数组 a 逆序存储在整型数组 b 中，其余项初始化为 0
    for(int i=0;i<t;i++)
        b[i]=C2(a[t-1-i]);
    for(int i=t;i<N;i++)
        b[i]=0;
    return;
}

3、两个字符数组相加

void add(int *c,int *a,int *b)
{
    for(int i=0;i<N;i++)
    {
        c[i]=a[i]+b[i];
    }// 不考虑进位问题，全部加一遍
    for(int i=0;i<N;i++)
    {
        if(c[i]>9)
        {
            if(i>=N-2)
                cerr << "int[N] overflow" << endl;
            else
            {// 哪一位进位了就把上一位加一，遍历的顺序是细节问题
                c[i+1]++;
                c[i]-=10;
            }
        }
    }
}

4、将逆序整型数组转换为字符数组

void int_to_char(char *b,int *a)
{
    int t=0;
    for(int i=N-1;i>=0;i--)
    {
        if(a[i]!=0)
        {
            t=i+1;
            break;
        }
    }
    for(int i=0;i<t;i++)
    {
        b[i]=C1(a[t-1-i]);
    }
    b[t]='\0';
}

两个大数的乘法

乘法的本质就是对加法的简化表达，那我们就把它「复杂」回去！

加法写了那么多代码，不能浪费嘛。

举例说明我的方法

987654321 * 12345

我们先计算，987654321 * 5，然后计算 9876543210 * 4，然后是 98765432100 * 3……

这个时候就会发现，计算大数加法的时候的逆序数组真是方便啊！

把数组「右移一位」就多了个零。

而这个乘以 5、乘以 4、乘以 3…我们直接用循环几次的「大数加法」就行。

代码

void mul(int *c,int *a,int *b)
{// a 乘以 b，存储在 c 里面
    for(int i=0;i<N;i++)
        c[i]=0;// 初始化，很重要！不然就会出现一堆莫名其妙的数字。
    int size=0;
    for(int i=N-1;i>=0;i--)
    {// 计算一下这个 b 有多长，长度是 size
        if(b[i]!=0)
        {
            size=i+1;
            break;
        }
    }
    for(int i=0;i<size;i++)
    {// 外面的大循环，把 b 分成一位一位的，分别去乘以 a
        int *aa=new int[N];
        for(int j=0;j<i;j++)
            aa[j]=0;
        for(int j=i;j<N;j++)
            aa[j]=a[j-i];
          // 这两个循环是把 a 「右移」，就是在 a 的低位增加几个零，具体个数要看下面要乘的是 b 的哪一位

        int x=b[i];
        for(int j=0;j<x;j++)
        {// 直接调用大数的加法，省事
            add(c,c,aa);
        }
        free(aa);
    }
    return;
}

最后

减法与加法几乎是一样的，就不细说了。

大数的除法，我目前还不会，想一想感觉是比较麻烦的，因为「大数的乘法」我是想到了乘法与加法的关系才弄出来的，但除法的话感觉规律我还不懂，有机会我要学习一下，然后再水一篇文章（误）。