企业官网建设流程全解析

cosmos 大整数加法指南：Python 实现 100+ 位正整数的竖式进位求和

【免费下载链接】cosmosWorld's largest Contributor driven code dataset | Used in Quark Search Engine, @OpenGenus IQ, OpenGenus Visual Project项目地址: https://gitcode.com/gh_mirrors/co/cosmos

导读

在cosmos仓库的mathematical_algorithms模块中，Solve_Sum_2PositiveIntegers子目录演示了一个经典的算法问题：用程序实现两个 100 位以上大正整数的加法。本文以该目录下的 README.md 为骨架，结合 Sum_2largeNumbers.py 的完整源码，从问题背景、算法思路、逐行代码解析到复杂度与边界分析，带读者完整掌握"字符串模拟竖式加法"这一大数运算的基础算法，可直接复制运行并迁移到 C/C++、Java 等其它语言。

一、问题背景：为什么 100+ 位整数不能直接相加

原文档开篇就点明了问题的本质：

There is no primitive data type to hold an integer number with 100 plus digits.

在绝大多数编程语言中，内置的整数类型都有固定的位宽上限。以常见的 64 位有符号整数为例，其最大值约为9.2×10¹⁸（19 位十进制数字），远远无法容纳 100 位以上的数字；即便使用 64 位无符号整数，上限也只有约1.8×10¹⁹（20 位十进制数字）。因此，对于 100 位甚至上千位的整数（例如大数密码学、高精度科学计算场景），必须自己实现高精度运算。

解决方案的思路：既然单个原生变量装不下这么大的数字，就用"字符串"来表示大数——每个字符对应一位十进制数字，然后按位逐位计算，模拟手算过程。这正是本目录中 Python 实现所采用的策略。

二、算法思路：回归小学竖式加法

原文档给出的解题思路非常朴素，只有三步：

• 像小学老师教的那样，用最简单的方式解决这个问题；
• 从**最右边（个位）**开始，从右往左逐位相加；
• 如果某一位相加结果大于等于 10，就把1进位到下一次加法中。

这实际上就是**竖式加法（column addition）**的标准流程：

9876543210... + 1234567890... ---------------- ...

对每一位执行digit1 + digit2 + carry，结果的个位写入当前位，十位（即sum // 10）作为进位carry保留给下一位。如此循环，直到两个数的所有位都处理完。

之所以从右往左，是因为进位是向高位传递的：个位的进位会影响到十位，十位的进位会影响到百位……如果从左往右处理，则无法在计算高位时提前知道低位的进位结果。

三、源码解析：Sum_2largeNumbers.py 逐行拆解

目录中的核心实现是 Sum_2largeNumbers.py，共 33 行，完整可运行。下面按功能块逐段解读。

3.1 输入与校验

a = input("Enter 1st number: ") b = input("Enter 2nd number: ") if (a.isdigit() and b.isdigit()):

• 两个大数以字符串形式输入，从而绕开整数类型上限；
• str.isdigit()用于校验输入是否全为数字字符。只有当两个输入都合法时，才进入加法流程；否则程序不输出任何结果（实际使用中可在此处增加错误提示与重试逻辑）。

3.2 初始化：列表 + 进位标志

m = 0 # 进位（carry），只可能取值 0 或 1 sum = "" # 结果字符串，从高位到低位逐步拼接 n1 = list(a) # 将第一个数字字符串转为字符列表，方便 pop 从尾部取位 n2 = list(b) # 将第二个数字字符串转为字符列表

将字符串转成list后，每次用pop()从列表末尾取出一个字符，天然实现了"从个位（最右）往高位（最左）"的处理顺序。

3.3 主循环：逐位相加并处理进位

while True: #Take far right digits digit1 = n1.pop() if len(n1) > 0 else None digit2 = n2.pop() if len(n2) > 0 else None #no more digit to take escape if ( digit1 == None and digit2 == None): break #still a digit in sencond elif digit1 == None: sum_digit = int(digit2) + m #still a digit in first elif digit2 == None: sum_digit = int(digit1) + m # both have a digit else: sum_digit = int(digit1) + int(digit2) + m # remember 1 if greater than 10 m = sum_digit // 10 # add the digit to sum string sum = str(sum_digit % 10) + sum

这段代码是算法的核心，逻辑清晰：

1. 取位：pop()分别取出两个数当前的最低位（字符），若某数已取完则得到None；
2. 终止条件：两个数都取完（均为None）时break，结束循环；
3. 三种分支：
   • 第一个数已取完：sum_digit = int(digit2) + m（只加第二个数的当前位与进位）；
   • 第二个数已取完：sum_digit = int(digit1) + m（对称处理）；
   • 两数都有位：sum_digit = int(digit1) + int(digit2) + m（本位之和加进位）；
4. 计算进位：m = sum_digit // 10。由于digit是单个数字（0–9），m只可能是 0 或 1（例如9+9+1=19，19//10=1）；
5. 写入结果位：sum = str(sum_digit % 10) + sum，取和的个位，前插到结果字符串最前面——因为循环是从低位到高位处理的，前插才能保证最终字符串是从高位到低位排列。

3.4 收尾：处理最高位的最终进位

# make sure add 1 to sum string if needs sum = (str(m) if m==1 else "") + sum # output print(f"Sum is {sum}")

循环结束后，若最后一步仍产生进位（m == 1），需要把该进位补充到结果的最前面。这一步很容易被遗漏，但正是竖式加法正确性的关键。

3.5 运行示例

在仓库目录下直接运行：

cd code/mathematical_algorithms/mathematical_algorithms/Solve_Sum_2PositiveIntegers python3 Sum_2largeNumbers.py

交互输入示例如下：

Enter 1st number: 99999999999999999999999999999999 Enter 2nd number: 1 Sum is 100000000000000000000000000000000

可见连续 32 个9加1之后发生了整串进位（carry propagation），结果正确变为1后跟 32 个0，这正是竖式进位逻辑处理"999…9 + 1"这类极端情形的价值所在。

四、算法复杂度与正确性分析

• 时间复杂度：主循环对两个输入数的每一位恰好处理一次，设两数位数分别为n和m，则时间复杂度为O(max(n, m))；
• 空间复杂度：需要额外的列表与结果字符串，为O(n + m)；
• 进位安全性：由于每一步的sum_digit最大为9 + 9 + 1 = 19，//10得到的进位恒为 0 或 1，不存在进位溢出问题；
• 结果位数：两个正整数的和，其位数要么等于较长的那个数的位数，要么比它多 1（例如 999+1=1000），第 3.4 节正是为了覆盖"多 1 位"的情形。

从代码结构可以推断，这个实现刻意避免了reversed()、zip_longest等函数式写法，而是用pop()+ 显式分支模拟手算过程，目的是让读者能直观对照"小学竖式"的心智模型，作为教学示例非常合适。

五、与 Python 内置大整数（bigint）的关系

需要说明的是，Python 本身的int是任意精度类型，理论上可以直接int(a) + int(b)完成同样的计算，甚至支持数千位：

print(f"Sum is {int(a) + int(b)}")

因此本目录的实现并非为了解决 Python 语言自身的能力缺陷，而是为了演示大数加法的底层原理——这一算法是理解更高阶大数运算（大数乘法、大数除法、模幂运算、RSA 密码学运算等）的基础。同样的"字符串模拟竖式"思路，可以无缝移植到 C、C++、Java、Go 等整数类型有固定上限的语言中（例如用字符数组或字节数组存储每一位）。作为对照，仓库mathematical_algorithms模块中的其它算法也普遍采用"逐位处理 + 循环"的教学化写法，例如 Conversion_from_Binary_to_Decimal.py 用number % 10逐位拆解二进制数，与本例的逐位取位思路一脉相承。

六、边界情况与可改进方向

围绕"两个 100+ 位正整数相加"这一题目，以下几类边界情况值得验证：

在保持题目范围（两个正整数）不变的前提下，可以基于本实现做如下扩展：

• 支持多个大数连加：把两数相加的逻辑封装为函数，循环累加即可；
• 支持大数减法/乘法：在同一"字符串逐位运算"框架下改造进位/借位逻辑；
• 将m == 1的收尾判断简化为m != 0，以泛化到其它进制（如二进制、十六进制）的加法。

七、总结

Solve_Sum_2PositiveIntegers用一段 33 行的 Python 代码，完整回答了"原生类型放不下的大正整数如何相加"这一基础算法问题：以字符串存储大数、以列表pop()从右往左取位、以//10与%10分离进位与结果位、循环结束后补上最高位进位。该实现忠实还原了原文档"像小学竖式一样从右到左逐位相加、满十进一"的解题思路，既是学习高精度运算的入门范本，也为迁移到 C/C++ 等固定精度语言提供了可直接照搬的算法骨架。

相关资源

• 题目与解题思路说明：Solve_Sum_2PositiveIntegers/README.md
• 完整可运行源码：Solve_Sum_2PositiveIntegers/Sum_2largeNumbers.py
• 同模块的其它数学算法：mathematical_algorithms（含Solve_Pi、Solve_x_y、factorial等子目录）
• 逐位拆解的相近实现：Conversion_from_Binary_to_Decimal.py

【免费下载链接】cosmosWorld's largest Contributor driven code dataset | Used in Quark Search Engine, @OpenGenus IQ, OpenGenus Visual Project项目地址: https://gitcode.com/gh_mirrors/co/cosmos