layout: posttitle: 数据结构与算法—大整数相加
date: 2019-10-18
tag: 数据结构与算法

大整数相加

给两个很大很大的整数（可能有几百位），求出他们的和

• 思路

因为很大的数已经超过了计算机可以存储，虽然 Python3 中的整型是没有限制内存大小的，但是不代表其他语言没有内存限制，所以一般将两个整数直接相加并不现实

在 Python3 中，一个长度为 36 的整数占 48 字节，一个长度为 1 的数占的字节数 28 字节，整数长度长和短在内存中差别并不明显。

既然没办法直接进行相加，想想小学的时候，老师是怎么教我们的，是不是从个位相加，超过 10 就进位。那么这么大的数字该用什么存储呢？有两种方法，一种是用数组存储，一种是用字符串存储。

• 代码

边界条件与测试案例

1. 边界条件：输入非数值
2. 正常大的整数
3. 小的数值（0 ）与大的数值

def big_num_sum(num1: str, num2: str) -> str:
    """
    边界条件：输入非数值
    测试案例：
    1. 包含有非数值的字符串
    2. 正常大的整数
    """
    assert num1.isdigit() == True
    assert num2.isdigit() == True
    long_num, short_num = (num1, num2) if (len(num1) > len(num2)) else (num2, num1)  # c
    long_num = long_num[::-1] # 倒序
    short_num = short_num[::-1] 
    long_len = len(long_num)  # 字符的长度
    short_len = len(short_num)
    for i in range(long_len - short_len):  # 将较短的数值后面补 0 补到和较长的数一样的长度
        short_num += "0"
    result = ""  # 用来保存结果
    flag = 0  # 进位标志位
    for i in range(long_len):
        temp = int(long_num[i]) + int(short_num[i]) + flag
        if temp >= 10:
            result += str(temp-10)
            flag = 1 # 
        else:
            result += str(temp)
            flag = 0
    return int(result[::-1])
if __name__ == "__main__":
    assert (big_num_sum("1234533333133333336", "88888888888888") == 1234533333133333336+88888888888888) == True
    assert (big_num_sum("0", "1") == 0+1) == True
    assert (big_num_sum("0", "d"))  # 非数值输入会报错，用来测试边界条件

当然，这个程序还可以换成用数组的形式写，这里就不在给出，同时还可对以上代码进行优化，如：只需要遍历最短的那个即可，这样对于很大整数加上一个小的整数来说，效率会更高，占据的内存也会更小

本代码的时间复杂度是 O(n)