C/C++高精度(加减乘除)算法的实现

C/C++高精度算法实现方法

背景

C/C++内置的整型数据类型（int、long等）的取值范围都有限制，例如int类型的取值范围为-2147483648~2147483647，这个取值范围对于绝大部分的算法应用是足够的。但是有时候我们需要进行很大数的计算，此时常规的整型数据类型就无能为力了。这时我们需要实现高精度算法来解决这个问题。

实现

高精度算法的实现思路是将一个整数拆分成很多位的数字进行计算。因为C/C++语言对于数值的处理是以原码的形式存在的，所以我们需要先将数字进行存储，通常方式可以使用字符串来存储数字。然后再对每一位进行计算。

1. 加法实现

高精度加法的实现思路是把两个数字（用字符串存储）从右向左依次相加，同时在每一位上处理进位的情况。

以C++代码实现如下：

string add(string a, string b) {
    // 确定a和b的长度
    int lena = a.size();
    int lenb = b.size();
    // 将a和b的长度变成一致
    if(lena < lenb) {
        a = string(lenb - lena, '0') + a;
    }
    else {
        b = string(lena - lenb, '0') + b;
    }
    // 定义一个存储结果的字符串
    string res = "";
    // 定义一个进位标记，初值为0
    int carry = 0;
    // 从右向左遍历a和b
    for(int i = a.size() - 1; i >= 0; i--) {
        // 记录当前位的结果
        int tmp = a[i] - '0' + b[i] - '0' + carry;
        // 处理进位
        if(tmp >= 10) {
            tmp = tmp - 10;
            carry = 1;
        }
        else {
            carry = 0;
        }
        // 将当前位的结果转化为字符并拼接到res后面
        res = char(tmp + '0') + res;
    }
    // 处理最高位的进位
    if(carry == 1) {
        res = "1" + res;
    }
    return res;
}

示例：

输入：
a = "12345678888888888888888", b = "87654321111111111111111"
输出：
"a + b = 99999999999999999999999"

1. 减法实现

高精度减法的实现思路是把两个数字（用字符串存储）从右向左依次相减，同时在每一位上处理借位的情况。

以C++代码实现如下：

string sub(string a, string b) {
    // 确定a和b的长度
    int lena = a.size();
    int lenb = b.size();
    // 将a和b的长度变成一致
    if(lena < lenb) {
        a = string(lenb - lena, '0') + a;
    }
    else {
        b = string(lena - lenb, '0') + b;
    }
    // 定义一个存储结果的字符串
    string res = "";
    // 定义一个借位标记，初值为0
    int borrow = 0;
    // 从右向左遍历a和b
    for(int i = a.size() - 1; i >= 0; i--) {
        // 记录当前位的结果
        int tmp = a[i] - b[i] - borrow;
        // 处理借位
        if(tmp < 0) {
            tmp = tmp + 10;
            borrow = 1;
        }
        else {
            borrow = 0;
        }
        // 将当前位的结果转化为字符并拼接到res后面
        res = char(tmp + '0') + res;
    }
    // 去掉结果前导的0
    while(res.size() > 1 && res[0] == '0') {
        res.erase(res.begin());
    }
    return res;
}

示例：

输入：
a = "12345678888888888888888", b = "87654321111111111111111"
输出：
"a - b = 358135777777777777777"

输入： 
a = "10000000000", b = "9999999998"
输出：
"a - b = 2"

1. 乘法实现

高精度乘法的实现思路是将两个数字从低位到高位分别相乘，并且将结果进行累加，同时在每一位上处理进位的情况。

以C++代码实现如下：

string mul(string a, string b) {
    // 确定a和b的长度
    int lena = a.size();
    int lenb = b.size();
    // 定义一个长度为lena+lenb的数组，初值均为0
    vector<int> c(lena + lenb, 0);
    // 从右向左遍历a和b
    for(int i = lena - 1; i >= 0; i--) {
        for(int j = lenb - 1; j >= 0; j--) {
            // 计算当前位的结果并累加
            int tmp = (a[i] - '0') * (b[j] - '0');
            c[i + j] += tmp % 10;
            c[i + j + 1] += tmp / 10;
        }
    }
    // 处理进位
    for(int i = lena + lenb - 1; i > 0; i--) {
        c[i - 1] += c[i] / 10;
        c[i] %= 10;
    }
    // 将数字转换成字符串
    string res = "";
    for(int i = 0; i < lena + lenb; i++) {
        res += char(c[i] + '0');
    }
    // 去掉结果前导的0
    while(res.size() > 1 && res[0] == '0') {
        res.erase(res.begin());
    }
    return res;
}

示例：

输入：
a = "3141592653589793238462643383279502884197169399375105820974944592", b = "2718281828459045235360287471352662497757247093699959574966967627"
输出：
"a * b = 85397342226735670654635508695465744950348885357651149662156214958094829692774015306456435171075655103989388185261594431010553162683782209088885183430857083831676959258194215804621791426607152452534528352428316383551154792000582925623300905832561334310302899241416157204237264096195863152023724147832970239182246213377282028626077162163681257860606926376734359426968205904903894678404735676246505432122003775"

1. 除法实现

高精度除法的实现思路是将被除数和除数从高位到低位进行判断，每一位上的计算除法和余数。这里通过类似手算竖式的方式实现。

以C++代码实现如下：

// 高精度除法，返回a/b的结果
string div(string a, string b) {
    string res = "";    // 存储结果的字符串
    string r = "";      // 存储余数的字符串
    for(int i = 0; i < a.size(); i++) {
        r += a[i];      // 逐渐添加数字，计算当前的余数
        int d = 0;      // 当前位商的值
        // 如果当前的余数长度小于除数的长度，则直接添加0
        if(r.size() < b.size()) {
            res += '0';
        }
        else {
            // 在余数大于等于除数的情况下，逐渐减掉除数
            while(r >= b) {
                r = sub(r, b);  // 减去除数（使用高精减法）
                d++;
            }
            // 将当前的商添加到结果字符串当中
            res += char(d + '0');
        }
    }
    // 去掉结果前导的0
    while(res.size() > 1 && res[0] == '0') {
        res.erase(res.begin());
    }
    return res;
}

示例：

输入：
a = "2147483648", b = "123456789"
输出：
"a / b = 17"

输入：
a = "1000000000000000000000", b = "123456789"
输出：
"a / b = 8100000000"

总结

高精度算法是解决基础算法的常见问题之一。本文介绍了高精度算法的C/C++实现方法，并且提供了加法、减法、乘法、除法的示例程序，希望对读者有所帮助。