为什么需要高精度运算
基本概念
高精度运算，本质是将大整数按位拆分，用字符串（或数组）保存每一位的数字，完全模拟小学阶段学习的竖式加减乘除规则，逐位计算并处理进位、借位。
- 存储方式：通常用字符串保存，高位在前、低位在后（和日常书写习惯一致），在计算时会反转字符串，让下标 0 对应最低位，方便对齐处理。
- 核心操作：进位处理（加法、乘法）、借位处理（减法）、前导零去除、数值大小比较。
三、实现方法
1）加法
运算原理
加法完全模拟小学竖式加法规则：
- 将两个数右对齐，从最低位开始逐位相加；
- 每一位的和 = 第一个数当前位 + 第二个数当前位 + 低位传来的进位 ；
- 当前位结果 = 和 % 10，向高位的进位 = 和 / 10；
- 所有位计算完成后，如果还有剩余进位，要在最高位补上。
// 代码中先将字符串反转，是为了让数组下标 0 对应最低位，天然实现右对齐，无需手动补位 |
string add(string a, string b) |
{ |
if (a.length() < b.length()) swap(a, b); // 大的数字放“上面”，方便操作 |
reverse(a.begin(), a.end()), reverse(b.begin(), b.end()); |
string res; |
int carry = 0; |
for (size_t i = 0; i < a.length(); ++i) |
{ |
int x = a[i] - '0'; |
int y = i < b.length() ? b[i] - '0' : 0; |
int sum = x + y + carry; |
res += (sum % 10) + '0'; |
carry = sum / 10; |
} |
if (carry) res += carry + '0'; |
reverse(res.begin(), res.end()); |
return res; |
} |
2）减法
运算原理
减法同样模拟小学竖式减法规则：
- 先比较两个数的大小，用大数减小数，保证结果非负，最后再补上负号；
- 将两个数右对齐，从最低位开始逐位相减；
- 如果当前位被减数 < 减数 + 借位，就向高位借 1 当 10，同时标记借位；
- 计算完成后，结果会产生多余的前导零，需要去除。
为什么要去除前导零？
减法计算完成后，高位可能会出现连续的 0。例如计算 ，按位计算后反转得到的中间结果会是 ，前面的三个 0 就是前导零。前导零不符合数字的书写规范，也会影响后续运算的长度判断，因此必须去除多余的前导零，仅保留最后一个有效数字（注意结果为 0 时保留一个 0）。
string sub(string a, string b) |
{ |
bool swaped = false; |
if (a.length() < b.length() || (a.length() == b.length() && a < b)) |
{ |
swap(a, b); |
swaped = true; |
} |
reverse(a.begin(), a.end()), reverse(b.begin(), b.end()); |
string res; |
int carry = 0; |
for (size_t i = 0; i < a.length(); ++i) |
{ |
int x = a[i] - '0'; |
int y = i < b.length() ? b[i] - '0' : 0; |
int sum = x - y - carry; |
if (sum < 0) |
{ |
sum += 10; |
carry++; |
} else carry = 0; |
res += sum + '0'; |
} |
/*-----去除前导零-----*/ |
while (res.length() > 1 && res.back() == '0') res.pop_back(); |
if (swaped) res += '-'; |
reverse(res.begin(), res.end()); |
return res; |
} |
3）乘法
运算原理
乘法模拟小学竖式乘法的错位相加规则：
- 第一个数的第 i 位，乘以第二个数的第 j 位，结果会落在结果的第 i+j 位上（最低位从 0 开始计数）；
- 先把所有位的乘积累加到位对应的位置，暂不处理进位；
- 全部相乘完成后，统一从低位到高位处理进位，每一位满十进一；
- 最后去除高位多余的前导零，再转换为字符串。
注意：两个长度分别为 La 和 Lb 的数相乘，结果长度最多为 La+Lb 位。
string mul(string a, string b) |
{ |
int La = a.size(), Lb = b.size(); |
vector<int> res(La + Lb, 0); |
reverse(a.begin(),a.end()), reverse(b.begin(),b.end()); |
for (size_t i = 0; i < a.length(); i++) |
{ |
int x = a[i] - '0'; |
for (size_t j = 0; j < b.length(); j++) |
{ |
int y = b[j] - '0'; |
res[i+j] += x * y; // 把每次每位的相乘结果放在数组中，先不进位 |
} |
} |
/*-----进位-----*/ |
for (int i = 0; i < (int)res.size(); i++) |
if (res[i] >= 10) |
{ |
res[i+1] += res[i] / 10; |
res[i] %= 10; |
} |
/*-----去除前导零-----*/ |
while (res.size() > 1 && res.back() == 0) res.pop_back(); |
string ret; |
for (int i = res.size()-1; i >= 0; i--) ret += res[i] + '0'; |
return ret; |
} |
4）除法
运算原理
这里实现的是高精度整数除以普通 int 整数（高精度除以高精度复杂度更高，日常场景中高精度除低精度最常用），同样模拟竖式除法规则：
- 从被除数的最高位开始，逐位向下计算；
- 当前位数值 = 上一位的余数 × 10 + 当前位数字；
- 当前位的商 = 当前位数值 ÷ 除数，新的余数 = 当前位数值 % 除数；
- 逐位计算完成后，去除商的前导零，同时可以返回余数。
代码中提供了两种写法：一种返回商和余数的 pair，一种只返回商，核心逻辑完全一致。
// 高精度除法：a / b，a为大整数（字符串），b为int，返回商和余数 |
pair<string, int> div(string a, int b) |
{ |
string res; |
int remainder = 0; // 余数 |
for (size_t i = 0; i < a.length(); ++i) |
{ |
remainder = remainder * 10 + (a[i] - '0'); |
res += (remainder / b) + '0'; |
remainder %= b; |
} |
// 去除前导零 |
size_t pos = res.find_first_not_of('0'); |
if (pos == string::npos) res = "0"; |
else res = res.substr(pos); |
return {res, remainder}; |
} |
string divide(string a, int b) |
{ |
if (b == 0) return "Error: Division by zero"; |
vector<int> num; |
for (char c : a) num.push_back(c - '0'); |
vector<int> result; |
int remainder = 0; |
for (size_t i = 0; i < num.size(); i++) |
{ |
int current = remainder * 10 + num[i]; |
result.push_back(current / b); |
remainder = current % b; |
} |
// 去除前导零 |
size_t start = 0; |
while (start < result.size() && result[start] == 0) start++; |
if (start == result.size()) return "0"; // 等于0时保留一个0 |
string ret = ""; |
for (size_t i = start; i < result.size(); i++) ret += result[i] + '0'; |
return ret; |
} |