什么是高精度运算

高精度运算用于处理超出标准整数类型范围的数值。C++中的 int 和 long long 类型分别能处理的最大值为 231−12^{31}-1和263−12^{63}-1 ，但对于更大的数值，就需要使用高精度运算。
高精度运算的核心思想是将大数分解为多个较小的数字（通常用字符串或数组存储），然后逐位进行运算。

高精度加法

原理
-将两个大数从最低位到最高位逐位相加。
-如果某一位相加的结果大于等于10，则向高位进位。
-最终结果可能比原数多一位。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string highPrecisionAdd(const string& a, const string& b) {
    string result;
    int carry = 0; // 进位
    int i = a.size() - 1, j = b.size() - 1;

    // 从后向前逐位相加
    while (i >= 0 || j >= 0 || carry > 0) {
        int num1 = (i >= 0) ? a[i] - '0' : 0; // 当前位的数字
        int num2 = (j >= 0) ? b[j] - '0' : 0;

        int sum = num1 + num2 + carry; // 当前位的和
        result.push_back((sum % 10) + '0'); // 将结果存储为字符
        carry = sum / 10; // 更新进位
        i--; // 向前移动
        j--;
    }

    // 因为结果是反向存储的，需要反转
    reverse(result.begin(), result.end());
    return result;
}

高精度减法

原理

  • 确保被减数大于或等于减数，否则结果为负数。
  • 从最低位到最高位逐位相减。
  • 如果某一位不够减，则从高位借1（即加10）。
    代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
string highPrecisionSubtract(const string& a, const string& b) {
    if (a.size() < b.size() || (a.size() == b.size() && a < b)) {
        string result = highPrecisionSubtract(b, a);
        return "-" + result; // 添加负号
    }

    string result;
    int carry = 0; // 借位
    int i = a.size() - 1, j = b.size() - 1;

    // 从后向前逐位相减
    while (i >= 0 || j >= 0) {
        int num1 = i >= 0 ? a[i] - '0' : 0; // 当前位的数字
        int num2 = j >= 0 ? b[j] - '0' : 0;

        int diff = num1 - carry - num2; // 当前位的差值
        if (diff < 0) {
            diff += 10; // 借位
            carry = 1; // 设置借位
        } else {
            carry = 0; // 清除借位
        }

        result.push_back(diff + '0'); // 将结果存储为字符
        i--; // 向前移动
        j--;
    }

    // 去掉前导0
    while (result.size() > 1 && result.back() == '0') {
        result.pop_back();
    }

    // 因为结果是反向存储的，需要反转
    reverse(result.begin(), result.end());
    return result;
}

高精度乘法

原理

  • 将两个大数从最低位到最高位逐位相乘。
  • 每次相乘的结果需要加上之前的结果，并注意进位。
  • 最终结果可能比原数多几位。
    代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
string highPrecisionMultiply(const string& a, const string& b) {
    int lenA = a.size(), lenB = b.size();
    vector<int> result(lenA + lenB, 0); // 结果数组

    // 从后向前逐位相乘
    for (int i = lenA - 1; i >= 0; i--) {
        for (int j = lenB - 1; j >= 0; j--) {
            int mul = (a[i] - '0') * (b[j] - '0');
            int sum = mul + result[i + j + 1];

            result[i + j] += sum / 10; // 进位
            result[i + j + 1] = sum % 10; // 当前位
        }
    }

    // 转换为字符串
    string res;
    for (int num : result) {
        if (res.empty() && num == 0) continue; // 去掉前导0
        res.push_back(num + '0');
    }

    return res.empty() ? "0" : res;
}

高精度除法

原理

  • 高精度除法较为复杂，通常需要模拟手工除法的过程。
  • 从高位到低位逐位试除，记录商和余数。
  • 余数用于下一次的试除。
    代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
pair<string, string> highPrecisionDivide(const string& a, const string& b) {
    string quotient, remainder;
    int lenA = a.size(), lenB = b.size();

    // 逐位试除
    for (int i = 0; i < lenA; i++) {
        remainder += a[i]; // 添加一位到余数
        int temp = 0; // 用于存储当前的商

        // 试除
        while (remainder >= b) {
            remainder = highPrecisionSubtract(remainder, b); // 减去除数
            temp++;
        }

        quotient += to_string(temp); // 添加商的当前位
    }

    // 去掉前导0
    quotient.erase(0, quotient.find_first_not_of('0'));
    remainder.erase(0, remainder.find_first_not_of('0'));

    return {quotient, remainder};
}