为什么需要高精度运算

基本概念高精度运算本质是将大整数按位拆分用字符串或数组保存每一位的数字完全模拟小学阶段学习的竖式加减乘除规则逐位计算并处理进位、借位。存储方式通常用字符串保存高位在前、低位在后和日常书写习惯一致在计算时会反转字符串让下标 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 位结果会落在结果的第 ij 位上最低位从 0 开始计数先把所有位的乘积累加到位对应的位置暂不处理进位全部相乘完成后统一从低位到高位处理进位每一位满十进一最后去除高位多余的前导零再转换为字符串。注意两个长度分别为 La 和 Lb 的数相乘结果长度最多为 LaLb 位。string mul(string a, string b){int La a.size(), Lb b.size();vectorint 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[ij] x * y; // 把每次每位的相乘结果放在数组中先不进位}}/*-----进位-----*/for (int i 0; i (int)res.size(); i)if (res[i] 10){res[i1] 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 / ba为大整数字符串b为int返回商和余数pairstring, 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;vectorint num;for (char c : a) num.push_back(c - 0);vectorint 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时保留一个0string ret ;for (size_t i start; i result.size(); i) ret result[i] 0;return ret;}四、总结