1. 字符串运算的底层实现原理
在C++中直接处理大数运算时，我们经常会遇到整型变量溢出的问题。比如两个很大的数字相加或相乘，超出了int或long long的表示范围。这时候，将数字以字符串形式存储并进行运算就成为了一个可靠的解决方案。
字符串运算的核心思想是模拟人类手工计算的过程。我们小时候学习加减乘除时，都是从最低位（个位）开始，逐位计算并处理进位。这个算法正是将这个过程用代码实现出来。
提示：字符串运算特别适合处理超大数字（比如100位以上的数字），这是基本数据类型无法直接处理的场景。
2. 字符串相加算法详解
2.1 算法思路解析
字符串相加的基本流程如下：
- 从两个字符串的末尾（即数字的个位）开始遍历
- 将对应位的字符转换为数字后相加
- 处理进位问题
- 将结果拼接成新的字符串
- 最后反转字符串得到正确顺序
2.2 代码实现与注释
cpp复制string addstring(string s1, string s2) {
int end1 = s1.size()-1; // s1的末位索引
int end2 = s2.size()-1; // s2的末位索引
int value1 = 0; // s1当前位的值
int value2 = 0; // s2当前位的值
int next = 0; // 进位值
string addstr; // 结果字符串
// 从末位开始遍历，直到两个字符串都处理完
while (end1 >= 0 || end2 >= 0) {
// 获取s1当前位的值，如果已遍历完则设为0
if (end1 >= 0) {
value1 = s1[end1] - '0'; // 字符转数字
--end1;
} else {
value1 = 0;
}
// 获取s2当前位的值，如果已遍历完则设为0
if (end2 >= 0) {
value2 = s2[end2] - '0'; // 字符转数字
--end2;
} else {
value2 = 0;
}
// 计算当前位的和（包括进位）
int sumval = value1 + value2 + next;
// 处理进位
if (sumval > 9) {
next = 1;
sumval -= 10;
} else {
next = 0;
}
// 将当前位的结果添加到字符串
addstr += (sumval + '0'); // 数字转字符
}
// 如果最后还有进位，需要添加
if (next != 0) {
addstr += (next + '0');
}
// 反转字符串得到正确顺序
reverse(addstr.begin(), addstr.end());
return addstr;
}
2.3 关键点解析
-
字符与数字转换：使用
'0'进行转换是因为字符'0'到'9'在ASCII表中是连续的，'0'的ASCII码是48，'1'是49，依此类推。所以'5'-'0'等于数字5。 -
进位处理：当某一位的和大于9时，我们需要记录进位，并在下一位计算时加上这个进位值。
-
字符串反转：因为我们是从最低位开始计算，结果也是从低位到高位拼接的，所以最后需要反转字符串才能得到正确的数字顺序。
3. 字符串相乘算法详解
3.1 算法思路解析
字符串相乘比相加复杂一些，它实际上是多次相加的组合。基本思路是：
- 用第二个数的每一位去乘第一个数
- 根据当前位的位置补相应数量的0（相当于乘以10的n次方）
- 将所有这些部分积相加得到最终结果
3.2 代码实现与注释
cpp复制string mulstring(string s1, string s2) {
int end1 = s1.size() - 1;
int end2 = s2.size() - 1;
string addstr; // 临时存储部分积
int n = 0; // 需要补的0的数量
string addstr1 = "0"; // 累计结果，初始为0
// 用s2的每一位去乘s1
while (end2 >= 0) {
int value1 = 0;
int value2 = 0;
int next = 0;
addstr.clear();
// 根据当前位的位置补0
for (int i = 0; i < n; i++) {
addstr += '0';
}
value2 = s2[end2] - '0'; // 获取s2当前位的值
// 用s2的当前位乘s1的每一位
end1 = s1.size() - 1;
while (end1 >= 0) {
value1 = s1[end1] - '0'; // 获取s1当前位的值
int mul1 = value2 * value1 + next; // 计算乘积加上进位
// 处理进位
if (mul1 > 9) {
next = mul1 / 10;
mul1 = mul1 % 10;
} else {
next = 0;
}
addstr += (mul1 + '0'); // 添加到部分积
--end1;
}
// 如果最后还有进位，需要添加
if (next != 0) {
addstr += (next + '0');
}
// 反转部分积字符串
reverse(addstr.begin(), addstr.end());
// 将部分积累加到总和中
addstr1 = addstring(addstr, addstr1);
++n; // 下一位需要多补一个0
--end2; // 处理s2的下一位
}
return addstr1;
}
3.3 关键点解析
-
补零操作：在计算部分积时，根据当前位的位置补相应数量的0，这相当于乘以10的n次方。比如第二位的计算需要补1个0，第三位补2个0，以此类推。
-
逐位相乘：对于s2的每一位，都要与s1的所有位相乘，并处理进位问题。
-
累加部分积：每次计算完一个部分积后，都要将其与之前的结果相加，这里复用了之前实现的字符串相加函数。
4. 常见问题与优化建议
4.1 常见问题排查
-
结果不正确：
- 检查字符与数字转换是否正确（确保使用了
-'0'和+'0'） - 验证进位处理逻辑是否正确
- 确认字符串反转操作是否在正确的位置
- 检查字符与数字转换是否正确（确保使用了
-
内存问题：
- 对于非常大的数字，注意字符串拼接的效率问题
- 可以考虑预分配足够大的空间避免频繁重新分配
-
性能问题：
- 字符串操作相对较慢，对于性能敏感的场景可以考虑优化
- 反转操作可以改为从字符串头部插入，但这样效率可能更低
4.2 优化建议
-
去除前导零：在返回结果前，可以添加逻辑去除结果中的前导零（除非结果本身就是0）。
-
预分配空间：可以预先估计结果的最大长度，为字符串预分配足够空间，避免频繁重新分配。
-
使用更高效的数据结构：对于特别大的数字运算，可以考虑使用vector
代替string来存储数字，可能会更高效。 -
并行计算：对于乘法运算，不同位之间的部分积计算是独立的，可以考虑并行化处理。
4.3 边界情况处理
-
输入包含非数字字符：当前实现假设输入都是合法数字字符串，实际应用中应该添加验证逻辑。
-
空字符串输入：应该处理空字符串的情况，可以将其视为"0"。
-
结果为0的情况：确保不会返回空字符串，至少返回"0"。
-
超大数字运算：对于特别大的数字（如上千位），需要考虑算法的时间复杂度问题。
5. 实际应用示例
让我们通过一个具体例子来理解这两个函数的运作过程。假设我们要计算"54" × "123"：
-
首先分解乘法：
- 3 × 54 = 162
- 2 × 54 = 108（补一个0变成1080）
- 1 × 54 = 54（补两个0变成5400）
-
然后相加：
- 162 + 1080 = 1242
- 1242 + 5400 = 6642
在代码中的具体执行过程：
-
处理s2的'3'：
- 计算3×4=12 → 记录2，进位1
- 计算3×5=15，加上进位1=16 → 记录6，进位1
- 最后还有进位1 → 得到"162"（反转后）
-
处理s2的'2'（n=1���：
- 先补1个0 → ""
- 计算2×4=8 → 记录8
- 计算2×5=10 → 记录0，进位1
- 最后还有进位1 → 得到"108"（反转前是"801"）
- 反转后是"108"，加上补的0 → "1080"
-
将"162"和"1080"相加得到"1242"
-
处理s2的'1'（n=2）：
- 先补2个0 → ""
- 计算1×4=4 → 记录4
- 计算1×5=5 → 记录5
- 得到"54"（反转前是"45"）
- 反转后是"54"，加上补的0 → "5400"
-
将"1242"和"5400"相加得到"6642"
这个例子清晰地展示了字符串相乘算法的分步执行过程，以及如何通过字符串相加函数来组合部分积。