在c++中实现高精度

本文最后更新于：3 个月前

实现高精度整数运算的C++类

在某些应用中，我们可能需要处理超出基本整数范围的大整数，例如对于极大的数值计算或密码学应用。在C++中，我们可以实现一个高精度整数类，允许我们执行大整数的基本运算。本文将介绍如何使用C++创建这样一个类，并实现加法、减法、乘法和除法。

1. 大整数类的设计

我们将创建一个BigInteger类，它内部使用一个vector<int>来存储大整数的各个位数。以下是基本设计：

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
#include <iostream>
#include <vector>
#include <stdexcept>

using namespace std;

class BigInteger {
private:
    vector<int> digits;

public:
    // 构造函数、打印函数等基本成员函数...

    // 大整数加法
    BigInteger operator+(const BigInteger &other) const;

    // 大整数减法
    BigInteger operator-(const BigInteger &other) const;

    // 大整数乘法
    BigInteger operator*(const BigInteger &other) const;

    // 大整数除法
    BigInteger operator/(const BigInteger &other) const;

    // 比较函数、零判断函数等辅助函数...
};

2. 构造函数和打印函数

首先，我们通过构造函数将字符串表示的数字转换为BigInteger对象，并提供一个打印函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
BigInteger(string numStr) {
    if (!isValidNumber(numStr)) {
        throw invalid_argument("Invalid number format");
    }

    for (int i = numStr.length() - 1; i >= 0; i--) {
        digits.push_back(numStr[i] - '0');
    }
}

void print() const {
    for (int i = digits.size() - 1; i >= 0; i--) {
        cout << digits[i];
    }
    cout << endl;
}

3. 加法运算

加法运算实现了两个BigInteger对象之间的加法操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
BigInteger operator+(const BigInteger &other) const {
        BigInteger result;
        int carry = 0;
        int i = 0;

        while (i < digits.size() || i < other.digits.size() || carry) {
            int sum = carry;
            if (i < digits.size()) sum += digits[i];
            if (i < other.digits.size()) sum += other.digits[i];

            result.digits.push_back(sum % 10);
            carry = sum / 10;

            i++;
        }

        return result;
    }

4. 减法运算

减法运算实现了两个BigInteger对象之间的减法操作，并处理负数情况：

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
BigInteger operator-(const BigInteger &other) const {
        if (*this < other) {
            throw invalid_argument("Result is negative, subtraction not supported");
        }

        BigInteger result;
        int borrow = 0;
        int i = 0;

        while (i < digits.size() || i < other.digits.size()) {
            int diff = borrow;
            if (i < digits.size()) diff += digits[i];
            if (i < other.digits.size()) diff -= other.digits[i];

            if (diff < 0) {
                diff += 10;
                borrow = -1;
            } else {
                borrow = 0;
            }

            result.digits.push_back(diff);

            i++;
        }

        // 移除前导零
        while (!result.digits.empty() && result.digits.back() == 0) {
            result.digits.pop_back();
        }

        return result;
    }

5. 乘法运算

乘法运算实现了两个BigInteger对象之间的乘法操作：

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
BigInteger operator*(const BigInteger &other) const {
        BigInteger result;

        for (int i = 0; i < digits.size(); i++) {
            int carry = 0;
            BigInteger temp;

            // 在乘法中，每一位和另一个数相乘，并且结果向左移动一位
            for (int j = 0; j < i; j++) {
                temp.digits.push_back(0);
            }

            for (int j = 0; j < other.digits.size() || carry; j++) {
                int product = carry;
                if (j < other.digits.size()) product += digits[i] * other.digits[j];

                temp.digits.push_back(product % 10);
                carry = product / 10;
            }

            result = result + temp;
        }

        return result;
    }

6. 除法运算

除法运算实现了两个BigInteger对象之间的除法操作，并处理除数为零的情况：

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
BigInteger operator/(const BigInteger &other) const {
        if (other.isZero()) {
            throw invalid_argument("Division by zero");
        }

        BigInteger result;
        BigInteger currentDividend;
        int currentIndex = digits.size() - 1;

        while (currentIndex >= 0) {
            currentDividend.digits.insert(currentDividend.digits.begin(), digits[currentIndex]);

            int quotient = 0;
            while (currentDividend >= other) {
                currentDividend = currentDividend - other;
                quotient++;
            }

            result.digits.insert(result.digits.begin(), quotient);

            currentIndex--;
        }

        // 移除前导零
        while (!result.digits.empty() && result.digits.back() == 0) {
            result.digits.pop_back();
        }

        return result;
    }

7. 其他辅助函数

在实际应用中，我们可能还需要其他辅助函数，比如判断是否为零、比较大小等函数。这些函数应该根据实际需要进行实现。

8. 示例用法

最后，我们在main函数中展示了BigInteger类的一些基本用法，包括加法、减法、乘法和除法：

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
int main() {
    try {
        // 示例用法
        BigInteger num1("12345678901234567890");
        BigInteger num2("98765432109876543210");

        cout << "num1: ";
        num1.print();

        cout << "num2: ";
        num2.print();

        BigInteger sum = num1 + num2;
        cout << "Sum: ";
        sum.print();

        BigInteger difference = num1 - num2;
        cout << "Difference: ";
        difference.print();

        BigInteger product = num1 * num2;
        cout << "Product: ";
        product.print();

        BigInteger quotient = num1 / num2;
        cout << "Quotient: ";
        quotient.print();
    } catch (const exception &e) {
        cerr << "Error: " << e.what() << endl;
    }

    return 0;
}

结论

通过实现这个BigInteger类，我们能够在C++中处理大整数运算，从而满足一些特定应用的需求。在实际应用中，可能需要根据具体情况进行性能优化和错误处理。

附上完整代码：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <iostream>
#include <vector>
#include <stdexcept>

using namespace std;

class BigInteger {
private:
    vector<int> digits;

public:
    // 构造函数，接受字符串表示的数字
    BigInteger(string numStr) {
        if (!isValidNumber(numStr)) {
            throw invalid_argument("Invalid number format");
        }

        for (int i = numStr.length() - 1; i >= 0; i--) {
            digits.push_back(numStr[i] - '0');
        }
    }

    // 打印大整数
    void print() const {
        for (int i = digits.size() - 1; i >= 0; i--) {
            cout << digits[i];
        }
        cout << endl;
    }

    // 判断输入的数字是否合法
    static bool isValidNumber(const string &numStr) {
        for (char digit : numStr) {
            if (!isdigit(digit)) {
                return false;
            }
        }
        return true;
    }

    // 大整数加法
    BigInteger operator+(const BigInteger &other) const {
        BigInteger result;
        int carry = 0;
        int i = 0;

        while (i < digits.size() || i < other.digits.size() || carry) {
            int sum = carry;
            if (i < digits.size()) sum += digits[i];
            if (i < other.digits.size()) sum += other.digits[i];

            result.digits.push_back(sum % 10);
            carry = sum / 10;

            i++;
        }

        return result;
    }

    // 大整数减法
    BigInteger operator-(const BigInteger &other) const {
        if (*this < other) {
            throw invalid_argument("Result is negative, subtraction not supported");
        }

        BigInteger result;
        int borrow = 0;
        int i = 0;

        while (i < digits.size() || i < other.digits.size()) {
            int diff = borrow;
            if (i < digits.size()) diff += digits[i];
            if (i < other.digits.size()) diff -= other.digits[i];

            if (diff < 0) {
                diff += 10;
                borrow = -1;
            } else {
                borrow = 0;
            }

            result.digits.push_back(diff);

            i++;
        }

        // 移除前导零
        while (!result.digits.empty() && result.digits.back() == 0) {
            result.digits.pop_back();
        }

        return result;
    }

    // 大整数乘法
    BigInteger operator*(const BigInteger &other) const {
        BigInteger result;

        for (int i = 0; i < digits.size(); i++) {
            int carry = 0;
            BigInteger temp;

            // 在乘法中，每一位和另一个数相乘，并且结果向左移动一位
            for (int j = 0; j < i; j++) {
                temp.digits.push_back(0);
            }

            for (int j = 0; j < other.digits.size() || carry; j++) {
                int product = carry;
                if (j < other.digits.size()) product += digits[i] * other.digits[j];

                temp.digits.push_back(product % 10);
                carry = product / 10;
            }

            result = result + temp;
        }

        return result;
    }

    // 大整数除法
    BigInteger operator/(const BigInteger &other) const {
        if (other.isZero()) {
            throw invalid_argument("Division by zero");
        }

        BigInteger result;
        BigInteger currentDividend;
        int currentIndex = digits.size() - 1;

        while (currentIndex >= 0) {
            currentDividend.digits.insert(currentDividend.digits.begin(), digits[currentIndex]);

            int quotient = 0;
            while (currentDividend >= other) {
                currentDividend = currentDividend - other;
                quotient++;
            }

            result.digits.insert(result.digits.begin(), quotient);

            currentIndex--;
        }

        // 移除前导零
        while (!result.digits.empty() && result.digits.back() == 0) {
            result.digits.pop_back();
        }

        return result;
    }

    // 判断是否为零
    bool isZero() const {
        return digits.size() == 0 || (digits.size() == 1 && digits[0] == 0);
    }

    // 比较两个大整数的大小
    bool operator<(const BigInteger &other) const {
        if (digits.size() < other.digits.size()) return true;
        if (digits.size() > other.digits.size()) return false;

        for (int i = digits.size() - 1; i >= 0; i--) {
            if (digits[i] < other.digits[i]) return true;
            if (digits[i] > other.digits[i]) return false;
        }

        return false;
    }
};

#编程|c++
在c++中实现高精度
http://qyc233.eu.org/2023/11/27/在c-中实现高精度/
作者
邱雨晨
发布于
2023年11月27日
许可协议