【大数基本操作】

操作分析讲解

<1>大数加法

高精度加法呢，简单来说就是：

我们剖析出我们最基础的加法步骤：按位相加。

按位求和：

按位求和最重要的一点就是我们知道每一位是不可能超过10的。
所以我们每次都将超过了10的部分加到下一位去。
我们在这里为了方便计算，将每一位数字倒序排列，我们就可以从左向右进行操作了。
得到了以后呢，我们有一个地方要注意：就是我们的最高位是不是多了一位。所以我们多了一个删除前导0的操作。
最后倒序返回就好了。

特殊形高精度加法：

这也不能叫特殊。我们上面的加法只适用于两个非负数相加。那么要是有负数咋办呢？
首先如果两个都是整数或负数，就不管符号直接相加就好啦，最后把符号给加上去（因为符号不变）。
那如果一正一负的话，我们就要考虑是否会变号。
所以就要考虑四种情况，每一种情况我们是用较大的数进行高精度减去较小的数得到的，然后判别符号就行了。

代码

string add(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    int mx = len1 > len2 ? len1 : len2;
    for (int i = 0; i < mx; i++) {
        num1[i] += num2[i];
        num1[i + 1] += num1[i] / 10;
        num1[i] %= 10;
    }
    //按位相加
    while (!num1[mx]) mx--;
    //删除前导0（是否有最高位进位）
    string ans;
    for (int i = mx; i >= 0; i--) ans += num1[i] + '0';
    //倒序生成字符串
    return ans;
}

<2>大数减法

我们这里讲的高精度减法并不直接得到两个数直接相减的值：

我们将大数减小数的值输出，如果是负数我们就输出0。
但是按这个道理，计算出来也没问题，我们先判断两个数的大小就好了。

减法和加法其实非常类似：

我们不过是从向下一个数进位变成了，找下一个数借位。
所以我们先进行减法，如果小于0了，我们就将其变为0~9之间的数，并借位。
这里要注意！我们由于承载了上一位的借位，所以可能会小于-9，那么我们就要循环将其加回0~9的区间。
同样这里要注意的是，我们的高位是不是没了。比如4321-4300，最后就是21，高位没了。所以我们也有一个删前导0的操作。
然后如果现在的最高位被借了，小于0，就特判出去就好了。
然后就可以倒序返回了。

代码

string sub(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    int mx = len1 > len2 ? len1 : len2;
    for (int i = 0; i < mx; i++) {
        num1[i] -= num2[i];
        while (num1[i] < 0) {
            num1[i] += 10;
            num1[i + 1]--;
        }
    }
    //按位相减
    while (!num1[mx]) mx--;
    //删除前导0
    string ans;
    if (num1[mx] < 0) ans += '0';
    //特判负数
    else
        for (int i = mx; i >= 0; i--) ans += num1[i] + '0';
    //倒序生成字符串
    return ans;
}

<3>大数乘法

乘法也回归到我们的基础计算中：

我们的每一次数位相乘，都是在这两个数位之积的地方产生数（看不懂没关系，下面举个栗子）。

我们先举个栗子吧：

假如用1234 * 53，我们按照正常操作当然就是先把3对着4,3,2,1一个一个乘，然后5也是一样。
但是他们和目标的数位有什么关系呢？我们不妨先不干进位的操作，留到最后干。
我们先来看3和1234，毫无疑问是在个十百千位上的。而5呢，当然是在十百千万位上。
也就是说，我们目标的数位 = 乘数的数位 + 被乘数的数位（为啥是加呢，因为幂次函数相乘就是指数相加嘛。栗子：5在十位，4在千位，10*1000=1e5，所以在万位）。

那么我们就清楚了，我们把每一位的数先求出来，最后再来进位就好了。

for (int i = 0; i < len1; i++)
    for (int j = 0; j < len2; j++)
        digit[i + j] += num1[i] * num2[j];

所以就是这样。

最后要注意，最大位数可以达到len1+len2，所以要从这一位删前导0。
倒序返回就好了。

代码

string mul(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    memset(digit, 0, sizeof digit);
    for (int i = 0; i < len1; i++)
        for (int j = 0; j < len2; j++)
            digit[i + j] += num1[i] * num2[j];
    //算出每一个数位上的值
    int mx = len1 + len2;
    for (int i = 0; i < mx; i++)
        if (digit[i] > 9) {
            digit[i + 1] += digit[i] / 10;
            digit[i] %= 10;
        }
    while (mx && !digit[mx]) mx--;
    if (!mx) return "0";
    string ans;
    for (int i = mx; i >= 0; i--)
        ans += digit[i] + '0';
    return ans;
}

<4>大数除法 + 取模

高精度除法和取模是相辅相成的，因为取模的过程中用到了除法，除法当然也要用到模。

首先我们知道除法最基本的是什么：

就是被除数可以减去除数的次数。

我们这里的高精度除法其实就是模拟了这个过程：减法，所以我们可以看到我们上面已经讲过的减法内容。

但是单纯的一个一个减过去也太浪费时间了，所以我们用了一种方法使其变得非常的简单快捷。

减法模拟：

我们直接举个栗子会更好理解：
假如我们是求7546 / 23。如果一个一个删过去，我们要删几百次。但是如果按照我们平常的思想，从最高位算过去该怎么模拟呢？
其实我们就可以先将23增大100倍，让23的数位变得和7456一样大。然后做减法，得到的商为3。所以我们就知道他可以对23除300次，余数是646。
然后将23以十倍的顺序逐渐缩小，每次对其求商取余。
然后我们用上一次的余数646除230，又可以得到商为2，余数为186。我们知道他可以对23除20次，现在总计320次。
然后186对23求商为8，取余为2，可以对23除8次，总计328次。余数也自然而然的出来了就是2。
详细实现过程看代码~

代码

string div(string s1, string s2, char ch) {
    int len1 = s1.length(), len2 = s2.length();
    int mx = len1;
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    if (len1 < len2 || (len1 == len2 && s1 < s2))
        if ('/' == ch) return "0";
        else return s1;
    //判断s1数比s2小的情况
    int t = len1 - len2;
    for (int i = len1 - 1; i >= 0; i--)
        if (i >= t) num2[i] = num2[i - t];
        else num2[i] = 0;
    len2 = len1;
    //将num2增大数位差倍
    memset(digit, 0, sizeof digit);
    for (int i = 0; i <= t; i++) {
        int tmp = calc(num1, num2 + i, len1, len2 - i);
        while (tmp >= 0) {
            len1 = tmp;
            digit[t - i]++;
            tmp = calc(num1, num2 + i, len1, len2 - i);
        }
    }
    //求出每一位的数据
    int L = mx;
    for (int i = 0; i < L; i++) {
        digit[i + 1] += digit[i] / 10;
        digit[i] %= 10;
    }
    //处理进位
    string ans1, ans2;
    L = mx;
    while (L >= 0 && !digit[L]) L--;
    while (L >= 0) ans1 += digit[L--] + '0';
    //求商
    L = mx;
    while (L >= 0 && !num1[L]) L--;
    while (L >= 0) ans2 += num1[L--] + '0';
    if (ans2.empty()) ans2 = "0";
    //求余数
    if ('/' == ch) return ans1;
    else return ans2;
}
int calc(int* num1, int* num2, int len1, int len2) {
    if (len1 < len2) return -1;
    if (len1 == len2)
        for (int i = len1 - 1; i >= 0; i--)
            if (num1[i] > num2[i]) break;
            else if (num1[i] < num2[i]) return -1;
    for (int i = 0; i < len1; i++) {
        num1[i] -= num2[i];
        if (num1[i] < 0) {
            num1[i] += 10;
            num1[i + 1]--;
        }
    }
    //高精度减法
    for (int i = len1 - 1; i >= 0; i--)
        if (num1[i]) return i + 1;
    return 0;
    //num1大于num2时，返回相差的位数
}

高精度计算综合测试代码

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e6 + 7;
string s1, s2;//输入字符串
int num1[MAX], num2[MAX], digit[MAX];//转换数组，进位数组
//全局变量区

string add(string s1, string s2);//加法
string sub(string s1, string s2);//减法
string mul(string s1, string s2);//乘法
string div(string s1, string s2, char ch);//除法or取模
int calc(int* num1, int* num2, int len1, int len2);//用于div：计算s1可以对s2满减的次数
//函数预定义区

int main() {
    IOS;
    cout << "请输入两个数:" << endl;
    while (cin >> s1 >> s2) {
        cout << "以下为该大数的基础运算:" << endl;
        cout << s1 << " + " << s2 << " = " << add(s1, s2) << endl;
        cout << s1 << " - " << s2 << " = " << sub(s1, s2) << endl;
        cout << s1 << " * " << s2 << " = " << mul(s1, s2) << endl;
        cout << s1 << " / " << s2 << " = " << div(s1, s2, '/') << endl;
        cout << s1 << " % " << s2 << " = " << div(s1, s2, '%') << endl;
        cout << endl << "----------分割线----------" << endl;
        cout << endl << "请输入两个数:" << endl;
    }
    return 0;
}
string add(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    int mx = len1 > len2 ? len1 : len2;
    for (int i = 0; i < mx; i++) {
        num1[i] += num2[i];
        num1[i + 1] += num1[i] / 10;
        num1[i] %= 10;
    }
    //按位相加
    while (mx >= 0 && !num1[mx]) mx--;
    //删除前导0（是否有最高位进位）
    if (mx < 0) return "0";
    string ans;
    for (int i = mx; i >= 0; i--) ans += num1[i] + '0';
    //倒序生成字符串
    return ans;
}
string sub(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    int mx = len1 > len2 ? len1 : len2;
    for (int i = 0; i < mx; i++) {
        num1[i] -= num2[i];
        while (num1[i] < 0) {
            num1[i] += 10;
            num1[i + 1]--;
        }
    }
    //按位相减
    while (mx >= 0 && !num1[mx]) mx--;
    //删除前导0
    string ans;
    if (mx < 0 || num1[mx] < 0) ans += '0';
    //特判负数
    else
        for (int i = mx; i >= 0; i--) ans += num1[i] + '0';
    //倒序生成字符串
    return ans;
}
string mul(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    memset(digit, 0, sizeof digit);
    for (int i = 0; i < len1; i++)
        for (int j = 0; j < len2; j++)
            digit[i + j] += num1[i] * num2[j];
    //算出每一个数位上的值
    int mx = len1 + len2;
    for (int i = 0; i < mx; i++)
        if (digit[i] > 9) {
            digit[i + 1] += digit[i] / 10;
            digit[i] %= 10;
        }
    while (mx && !digit[mx]) mx--;
    if (!mx) return "0";
    string ans;
    for (int i = mx; i >= 0; i--)
        ans += digit[i] + '0';
    return ans;
}
string div(string s1, string s2, char ch) {
    int len1 = s1.length(), len2 = s2.length();
    int mx = len1;
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    if (len1 < len2 || (len1 == len2 && s1 < s2))
        if ('/' == ch) return "0";
        else return s1;
    //判断s1数比s2小的情况
    int t = len1 - len2;
    for (int i = len1 - 1; i >= 0; i--)
        if (i >= t) num2[i] = num2[i - t];
        else num2[i] = 0;
    len2 = len1;
    //将num2增大数位差倍
    memset(digit, 0, sizeof digit);
    for (int i = 0; i <= t; i++) {
        int tmp = calc(num1, num2 + i, len1, len2 - i);
        while (tmp >= 0) {
            len1 = tmp;
            digit[t - i]++;
            tmp = calc(num1, num2 + i, len1, len2 - i);
        }
    }
    //求出每一位的数据
    int L = mx;
    for (int i = 0; i < L; i++) {
        digit[i + 1] += digit[i] / 10;
        digit[i] %= 10;
    }
    //处理进位
    string ans1, ans2;
    L = mx;
    while (L >= 0 && !digit[L]) L--;
    while (L >= 0) ans1 += digit[L--] + '0';
    //求商
    L = mx;
    while (L >= 0 && !num1[L]) L--;
    while (L >= 0) ans2 += num1[L--] + '0';
    if (ans2.empty()) ans2 = "0";
    //求余数
    if ('/' == ch) return ans1;
    else return ans2;
}
int calc(int* num1, int* num2, int len1, int len2) {
    if (len1 < len2) return -1;
    if (len1 == len2)
        for (int i = len1 - 1; i >= 0; i--)
            if (num1[i] > num2[i]) break;
            else if (num1[i] < num2[i]) return -1;
    for (int i = 0; i < len1; i++) {
        num1[i] -= num2[i];
        if (num1[i] < 0) {
            num1[i] += 10;
            num1[i + 1]--;
        }
    }
    //高精度减法
    for (int i = len1 - 1; i >= 0; i--)
        if (num1[i]) return i + 1;
    return 0;
    //num1大于num2时，返回相差的位数
}
//函数区

后话

<5>大数阶层

大数的阶层，我们必然也是要用一个数组来保存答案数据的每一位的。

阶层的原理是啥呢？

我们的阶层就是从1一步一步的乘到n。
那我们上面将高精度乘法的时候是怎么讲的呢？就是将数放到两个数位之和的位置上面去。
同样的思路，我们可以换一个看法：就是用乘数的每一位去乘上被乘数，然后逐步进位到下一位。同时我们用一个变量digit标记最后一位的位置（用于识别答案当前长度）。

那怎么操作呢？

先看个栗子：假如是50的阶层，我们最开始肯定是1，digit也是1。然后按位乘：1 * 2，答案是2，digit还是1。同理得到3时是6和digit=1。
※那接下来变成4就不一样了：我们用6 * 4 = 24，现在a[0]=24。我们知道每一位不能超过9。所以把超过个位的放到a[1]里面去（放24 / 10，存24 % 10），再标记digit = 2了。
※那到了5之后呢，我们现在digit>1，按每一位来计算，先用个位：4 * 5 = 20，同理将0留下，2进位。然后十位：2 * 5 + 进位 = 12，所以留下2，进位1。这个1超过原来的长度了，digit就再加。
按上面这个道理，简单用语言描述是怎么弄呢？就是先按位进行计算，并进位，直到算到被乘数（当前答案数组）的最高位。然后将越界的进位放到后面的位置，并改变digit的位置。

打代码嘞：

先输入我们的阶层数，这个数很大，但我们定在1w以内，这样只要2s左右可以算出来，再大就难算了。
先定义1的情况，就是a[0] = 1，digit = 1。
然后从2循环乘到n。
循环内先将被乘数（当前答案数组）进行逐位乘法并进位。然后将超出最高位的进位放进数组，并标记digit。
最后倒序输出（要拿出来用也可以合并成String）。
看我代码~

代码

#include <iostream>
using namespace std;
#define IOS ios::sync_with_stdio(false);
//代码预处理区

const int MAX = 1e5 + 7;
int a[MAX];
//全局变量区

int main() {
    int n; cin >> n;
    a[0] = 1;
    int digit = 1;//表示最高数位位置
    for (int i = 2; i <= n; i++) {
        int plus = 0;//保存向下一位的进位
        for (int j = 0; j < digit; j++) {
            int temp = a[j] * i + plus;
            a[j] = temp % 10;
            plus = temp / 10;
        }
        //上一位的长度范围内进行乘法进位操作
        while (plus) {
            a[digit] = plus % 10;
            plus /= 10;
            digit++;
        }
        //超出上一位的长度范围的进位操作（同时标记这一位长度）
    }
    for (int k = digit - 1; k >= 0; k--)
        cout << a[k];
    cout << endl;
    //倒序输出
    return 0;
}
//函数区

算法专栏文章被收录于专栏

憨憨的专栏