高精度算法及其在 C++ 中的实现

高精度算法是一种用于处理大数运算的算法。由于计算机中的基本数据类型（如 int、long 等）所能表示的数值范围有限，当涉及到超出这个范围的数值运算时，就需要使用高精度算法。高精度算法在一些语言中（如Python，Java）已经被集成到语言里，这里为了学习思想，使用C++来自行实现该算法。

算法分析及难点

算法分析

高精度算法的思想为模拟，其模拟了人类对大数进行计算的过程，其实就是模拟了我们小学时学习到的“竖式”的计算方法来计算大数。我们可以用向量或字符串来存储大数，然后对它进行操作。

算法难点

本算法的难点在于加法的进位，减法的借位，乘法的进位和除法的商和余数的处理。

高精度加法

高精度加法是处理两个大整数相加的算法。其基本思想是将两个大整数分别存储在字符串中，然后从最低位开始逐位相加，如果和大于等于 10，则进位。
以下是 C++ 代码实现：

std::string addStrings(std::string num1, std::string num2) {
    std::string result; // 存储计算结果的字符串
    int carry = 0; // 进位

    int i = num1.length() - 1; // 指向 num1 的最低位
    int j = num2.length() - 1; // 指向 num2 的最低位

    while (i >= 0 || j >= 0 || carry > 0) { // 当还有数字位或者有进位时继续计算
        int digit1 = (i >= 0) ? num1[i] - '0' : 0; // 获取 num1 数字位的值，不存在则设为 0
        int digit2 = (j >= 0) ? num2[j] - '0' : 0; // 获取 num2 数字位的值，不存在则设为 0

        int sum = digit1 + digit2 + carry; // 计算当前位的和（包括进位）
        carry = sum / 10; // 计算进位
        int digit = sum % 10; // 当前位的数字

        result.push_back(digit + '0'); // 将当前位的数字转为字符，并加入结果字符串
        i--; // 移动 num1 指针
        j--; // 移动 num2 指针
    }

    std::reverse(result.begin(), result.end()); // 结果字符串翻转，得到正确的高精度整数表示
    return result; // 返回计算结果
}

高精度减法

高精度减法是处理两个大整数相减的算法。其基本思想是将两个大整数分别存储在字符串中，然后从最低位开始逐位相减，如果不够减，则向高位借位。
以下是 C++ 代码实现：

std::string subtractStrings(std::string num1, std::string num2) {
    std::string result; // 存储计算结果的字符串
    int borrow = 0; // 借位
    int i = num1.length() - 1; // 指向 num1 的最低位
    int j = num2.length() - 1; // 指向 num2 的最低位
    while (i >= 0 || j >= 0) { // 当还有数字位时继续计算
        int digit1 = (i >= 0) ? num1[i] - '0' : 0; // 获取 num1 数字位的值，不存在则设为 0
        int digit2 = (j >= 0) ? num2[j] - '0' : 0; // 获取 num2 数字位的值，不存在则设为 0
        digit1 -= borrow; // 减去借位
        borrow = 0; // 清空借位
        if (digit1 < digit2) { // 需要借位
            digit1 += 10;
            borrow = 1; // 设置借位为 1
        }
        int digit = digit1 - digit2; // 当前位的差值
        result.push_back(digit + '0'); // 将当前位的差值转为字符，并加入结果字符串
        i--; // 移动 num1 指针
        j--; // 移动 num2 指针
    }
    std::reverse(result.begin(), result.end()); // 结果字符串翻转，得到正确的高精度整数表示
    // 去掉前导零
    int k = 0;
    while (result[k] == '0' && k < result.length() - 1) {
        k++;
    }
    result = result.substr(k);
    return result; // 返回计算结果
}

高精度乘法

高精度乘法是处理两个大整数相乘的算法。其基本思想是将两个大整数分别存储在数组中，然后模拟竖式的乘法过程，将结果存储在另一个数组中。
以下是 C++ 代码实现：

std::string multiplyStrings(std::string num1, std::string num2) {
    int len1 = num1.length();
    int len2 = num2.length();
    std::string result(len1 + len2, '0'); // 存储计算结果的字符串，初始化为全零
    // 对 num1 的每一位进行循环
    for (int i = len1 - 1; i >= 0; i--) {
        int carry = 0;
        int digit1 = num1[i] - '0';
        // 对 num2 的每一位进行循环
        for (int j = len2 - 1; j >= 0; j--) {
            int digit2 = num2[j] - '0';
            int product = digit1 * digit2 + carry + (result[i + j + 1] - '0');
            carry = product / 10;
            int digit = product % 10;
            result[i + j + 1] = digit + '0';
        }
        result[i] += carry; // 处理进位
    }
    // 去掉前导零
    int k = 0;
    while (result[k] == '0' && k < result.length() - 1) {
        k++;
    }
    return result.substr(k);
}

高精度除法

高精度除法是处理两个大数相除的算法，其基本思想是模仿手工计算除法的过程，通过逐位进行减法操作，得到每一位的商，然后再将这些商拼接成最终的结果。

以下是C++代码实现：

std::string divideStrings(std::string dividend, std::string divisor) {
    std::string result; // 存储计算结果的字符串
    int len1 = dividend.length();
    int len2 = divisor.length();
    if (len1 < len2 || (len1 == len2 && dividend < divisor)) {
        return "0"; // 被除数小于除数，结果为0
    }
    int idx = 0; // 记录当前除法操作的位置
    std::string current = dividend.substr(0, len2); // 当前参与除法运算的数字
    while (idx < len1) {
        int quotient = 0; // 商
        while (current >= divisor) {
            current = subtractStrings(current, divisor); // 用被减数减去除数，得到当前商的结果
            quotient++;
        }
        result.push_back(quotient + '0'); // 将当前的商加入结果字符串中
        idx++;
        if (current.empty() && idx < len1) {
            current = dividend.substr(idx, 1); // 添加下一位被除数
        } else {
            current += dividend.substr(idx, 1);
        }
    }
    // 去掉前导零
    int k = 0;
    while (result[k] == '0' && k < result.length() - 1) {
        k++;
    }
    return result.substr(k);
}