大整数加法

概述

在C/C++中，long long 的长度一般为 64bit 整形， 大概能处理绝对值小于 8 * 10^18 的加法。

若加法的结果或 *** 作数的绝对值大于这个范围，那么系统就不能处理了。

此时需要用到大整数的技巧，用两个数组来存储 *** 作数，一个数组来存储结果，模拟竖式加法来完成大整数的加法。

需要实现的 *** 作

要实现一个大整数加法，需要实现的 *** 作不仅仅是加法 *** 作，还要实现大整数的存储和输入输出，这样才算完整。

不要觉得输入输出简单，这里面也蕴含着一些技巧需要掌握。

存储方式

大小端序 ：

大端序：数字的高位在地址的低位（也就是和打印顺序一致）。

以2021为例：

小端序：数字的低位在地址的低位。

大整数加法采用小端存储

通常进行高精度计算时，采取小端序方式，主要的目的是为了方便模拟竖式计算，在后面我们会详细解释。

实现细节

    1 . 使用int数组存储大整数的每一位。

采用小端序的存储方式，将高精度数字的每一位存在数组的每个元素里。

    2 .对于每一个大整数，需要一个长度位记录大整数的长度，以方便输入输出。

输入输出

若采用小端存储，那么存储的顺序和正常的阿拉伯数字顺序是相反的。

输入的时候，首先应该用一个字符串存储大整数，然后把 字符串大整数 按照 小端存储 的方式存入数组中。

输出的时候，则需要按照小端存储的逆序输出，这样才能按照正常的打印顺序打印出大整数。

加法 *** 作

结果的位数默认等与为两个加数最大的那个。

如果有进位，那么长度需要+1。

遍历把两个加数的当前位相加，存储在临时变量 tmp 中， tmp 小于10的部分即是结果的当前位，大于10的部分加入后一位。

代码

在下面的代码中，有一些细节没有明确体现出来，自己实现的时候需要注意：
1. 所有存储大整数的数组都应该初始化为0值数组。

#include 
#define N 110
using namespace std;
// 这里我们采用直接赋值的形式初始化，按照小端序的方式存储
// 所以这里加数a = 368， 加数b = 997，
// 感兴趣的话也可以按照之前介绍的方式改成手动输入
int a_digits[N] = {8, 6, 3}, a_len = 3;
int b_digits[N] = {7, 9, 9}, b_len = 3;
int ans_digits[N], ans_len;

int main() {
    // 1. 数位 *** 作:     
    ans_len = max(a_len, b_len);  // 初始长度
    for (int i = 0; i < ans_len; ++i) {
        // 假设a_len > b_len，这里需要保证b[b_len]到b[a_len - 1]的位置都是0，否则可能会出错。

        int tmp = a_digits[i] + b_digits[i];
        ans_digits[i] += tmp % 10; // 相加计算
        ans_digits[i + 1] += tmp / 10; //进位
    }
    
    // 2. 维护长度: 
    if (ans_digits[ans_len] > 0) 
        ans_len++; 
    
    // 3. 输出    
    for (int i = ans_len - 1; i >= 0; --i) 
        cout << ans_digits[i];
    cout << endl;
    
    return 0;
}

参考 ： 青舟智学