'高精度算法'
高精度算法
一、为什么需要高精度运算#
普通的整数类型（int、long long）都有固定的取值范围，例如64位 long long 最大只能存储约 9×10¹⁸ 的数值。当我们需要处理几十位、上百位甚至更长的大整数时（比如大数阶乘、密码学计算、超长数值运算等场景），内置类型会发生溢出，无法正确存储和计算。高精度运算的核心思路就是用字符串或数组存储大整数的每一位数字，模拟人类手算的方式完成加减乘除，从而突破数值范围的限制。
二、基本概念#
高精度运算，本质是将大整数按位拆分，用字符串（或数组）保存每一位的数字，完全模拟小学阶段学习的竖式加减乘除规则，逐位计算并处理进位、借位。
- 存储方式：通常用字符串保存，高位在前、低位在后（和日常书写习惯一致），在计算时会反转字符串，让下标 0 对应最低位，方便对齐处理。
- 核心操作：进位处理（加法、乘法）、借位处理（减法）、前导零去除、数值大小比较。
三、实现方法#
1）加法#
运算原理
加法完全模拟小学竖式加法规则：
将两个数右对齐，从最低位开始逐位相加；
每一位的和 = 第一个数当前位 \(a[i]\) + 第二个数当前位 \(b[i]\) + 低位传来的进位 \(carry\)；
当前位结果 = 和 % 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。例如计算 \(1000 - 999 = 1\)，按位计算后反转得到的中间结果会是 \(0001\)，前面的三个 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 = class="hljs-number">0;
for (size_t i = class="hljs-number">0; i < a.length(); ++i)
{
int x = a[i] - class="hljs-string">'class="hljs-number">0';
int y = i < b.length() ? b[i] - class="hljs-string">'class="hljs-number">0' : class="hljs-number">0;
int sum = x - y - carry;
if (sum < class="hljs-number">0)
{
sum += class="hljs-number">10;
carry++;
} else carry = class="hljs-number">0;
res += sum + class="hljs-string">'class="hljs-number">0';
}
class=class="hljs-string">"hljs-comment">/*-----去除前导零-----*/
while (res.length() > class="hljs-number">1 && res.back() == class="hljs-string">'class="hljs-number">0') res.pop_back();
if (swaped) res += class="hljs-string">'-';
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, class="hljs-number">0);
reverse(a.begin(),a.end()), reverse(b.begin(),b.end());
for (size_t i = class="hljs-number">0; i < a.length(); i++)
{
int x = a[i] - class="hljs-string">'class="hljs-number">0';
for (size_t j = class="hljs-number">0; j < b.length(); j++)
{
int y = b[j] - class="hljs-string">'class="hljs-number">0';
res[i+j] += x * y; class=class="hljs-string">"hljs-comment">// 把每次每位的相乘结果放在数组中，先不进位
}
}
class=class="hljs-string">"hljs-comment">/*-----进位-----*/
for (int i = class="hljs-number">0; i < (int)res.size(); i++)
if (res[i] >= class="hljs-number">10)
{
res[i+class="hljs-number">1] += res[i] / class="hljs-number">10;
res[i] %= class="hljs-number">10;
}
class=class="hljs-string">"hljs-comment">/*-----去除前导零-----*/
while (res.size() > class="hljs-number">1 && res.back() == class="hljs-number">0) res.pop_back();
string ret;
for (int i = res.size()-class="hljs-number">1; i >= class="hljs-number">0; i--) ret += res[i] + class="hljs-string">'class="hljs-number">0';
return ret;
}4）除法#
运算原理
这里实现的是高精度整数除以普通 int 整数（高精度除以高精度复杂度更高，日常场景中高精度除低精度最常用），同样模拟竖式除法规则：
- 从被除数的最高位开始，逐位向下计算；
- 当前位数值 = 上一位的余数 × 10 + 当前位数字；
- 当前位的商 = 当前位数值 ÷ 除数，新的余数 = 当前位数值 % 除数；
- 逐位计算完成后，去除商的前导零，同时可以返回余数。
代码中提供了两种写法：一种返回商和余数的 pair，一种只返回商，核心逻辑完全一致。
class=class="hljs-string">"hljs-comment">// 高精度除法：a / b，a为大整数（字符串），b为int，返回商和余数
pair<string, int> div(string a, int b)
{
string res;
int remainder = class="hljs-number">0; class=class="hljs-string">"hljs-comment">// 余数
for (size_t i = class="hljs-number">0; i < a.length(); ++i)
{
remainder = remainder * class="hljs-number">10 + (a[i] - class="hljs-string">'class="hljs-number">0');
res += (remainder / b) + class="hljs-string">'class="hljs-number">0';
remainder %= b;
}
class=class="hljs-string">"hljs-comment">// 去除前导零
size_t pos = res.find_first_not_of(class="hljs-string">'class="hljs-number">0');
if (pos == string::npos) res = class="hljs-string">"class="hljs-number">0";
else res = res.substr(pos);
return {res, remainder};
}
string divide(string a, int b)
{
if (b == class="hljs-number">0) return class="hljs-string">"Error: Division by zero";
vector<int> num;
for (char c : a) num.push_back(c - class="hljs-string">'class="hljs-number">0');
vector<int> result;
int remainder = class="hljs-number">0;
for (size_t i = class="hljs-number">0; i < num.size(); i++)
{
int current = remainder * class="hljs-number">10 + num[i];
result.push_back(current / b);
remainder = current % b;
}
class=class="hljs-string">"hljs-comment">// 去除前导零
size_t start = class="hljs-number">0;
while (start < result.size() && result[start] == class="hljs-number">0) start++;
if (start == result.size()) return class="hljs-string">"class="hljs-number">0"; class=class="hljs-string">"hljs-comment">// 等于class="hljs-number">0时保留一个class="hljs-number">0
string ret = class="hljs-string">"";
for (size_t i = start; i < result.size(); i++) ret += result[i] + class="hljs-string">'class="hljs-number">0';
return ret;
}四、总结#
高精度四则运算的核心思想高度统一：用字符串/数组拆分存储大整数的每一位，完全模拟人工竖式计算的规则。
- 加法、乘法：从低位到高位计算，重点处理进位；
- 减法：从低位到高位计算，重点处理借位，注意正负号判断；
- 除法（低精度除数）：从高位到低位计算，逐位落数，保留余数。
所有运算最终都需要处理前导零，保证输出格式符合常规数字的书写习惯。这套实现可以处理任意长度的正整数运算，是算法竞赛和大数计算场景的基础工具。
五、最后碎碎念#
由于学期接近期末，最近都在准备期末考试，所以更新慢了许多，还请见谅！此外如果你发现我的博客有错误的地方、语义矛盾或者有更好的方法，欢迎你的建议与指导！
相关文章
评论