算法数学算法

高精度运算代码模板，非负整数加减乘除、取模、比较

字数统计: 3.4k字   |   阅读时长: 17分
,

摘要: 在数组上实现高精度运算，包括加减乘除、取模、比较、可以作为代码模板

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在计算机中表示整数一般是通过 int、long long 等类型，这些类型能表示的数字都有大小限制。但有时在应用中我们需要处理更大的数字，这时就不能用内置的 int、double 来做了。

为了实现大整数的加减乘除等运算，高精度运算是一种解法，也就是用字符串、数组、链表等线性数据结构维护整数的各个位的数字。比如用字符串表示数字的话，一个字符串代表一个整数，字符串中的每个字符代表整数的每个位，通过在字符串上实现按位的加减乘除，最终来实现大整数的加减乘除。

根据需要，高精度运算还可以实现大整数的比较、取模等运算。在文章 中我们以力扣上的 8 道题看了一下在字符串、数组、链表等数据结构上如何实现按位加减乘除。

本文我们来实现包括加减乘除、取模、比较的大整数非负数的完整代码，可以作为代码模板使用。主要内容如下：

  • 非负整数大数类基础功能
  • >> 和 << 方便调试
  • 加减乘(减法不支持小减大)
  • 大数对小数取模
  • 大数除大数，大数对大数取模
  • 小于比较
  • 完整代码
  • 要支持负数可以加一个 BigInteger::sign 维护，有点复杂。

$1 正整数大数类基础功能

结构体 BigInteger 用于存储高精度非负整数。

以下代码中，通过构造函数给 BigInteger 的值只能在 long long 范围内，可以通过字符串将很长的整数交给 BigInteger 可以通过赋值函数。

BASE 是静态成员变量，是属于类的，其它地方用可以写 BigInteger::BASE。

  • static const int BASE = 2;
  • static const int WIDTH = 1;
  • s 保存大整数各个数位
  • 原数 1234 => s=[4,3,2,1]
  • 进制数为 BASE
  • WIDTH 为 s[i] 中保存的位数，即 BASE 的位数，例如 BASE = 10，则 WIDTH = 1(0~9)，BASE = 11，则 WIDTH = 2(0~10)，BASE=1e8，WIDTH=8
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
struct BigInteger
{
    static const int BASE = 2;
    static const int WIDTH = 1;
    // s 保存大整数各个数位，BASE=10, WIDTH=1 为例
    // 原数 1234 => s=[4,3,2,1]
    // BASE=100, WIDTH=2 为例
    // 原数 1234 => s=[34, 12]
    vector<int> s;

    void show()
    {
        for(int i: s) cout << i << " ";
        cout << endl;
    }

    BigInteger(ll num = 0) // 构造函数
    {
        *this = num;
    }

    BigInteger operator=(ll num) // 赋值运算符
    {
        s.clear();
        do
        {
            s.push_back(num % BASE);
            num /= BASE;
        }while(num > 0);
        return *this;
    }

    BigInteger operator=(const string& str) // 赋值运算符
    {
        s.clear();
        int len = (str.length() - 1) / WIDTH + 1;
        int x;
        for(int i = 0; i < len; ++i)
        {
            int end = str.length() - i * WIDTH;
            int start = max(0, end - WIDTH);
            sscanf(str.substr(start, end - start).c_str(), "%d", &x);
            s.push_back(x);
        }
        return *this;
    }

    // 去掉大数的前导0
    void clean()
    {
        while(!s.empty() && s.back() == 0)
            s.pop_back();
    }
};

$2 >> 和 << 方便调试

stringstream 也自动支持了 BigInteger，这得益于 C++ 的继承机制。

>> 和 << 的参数是一般的 istream 和 ostream，cin/cout 和 stringstream 都是更特殊的类型，因此也能用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ostream& operator<<(ostream& out, const BigInteger& x)
{
    out << x.s.back();
    for(int i = x.s.size() - 2; i >= 0; --i)
    {
        string tmp = to_string(x.s[i]);
        string buf(BigInteger::WIDTH - tmp.size(), 0);
        buf += tmp;
        for(int j = 0; j < (int)buf.size(); ++j)
            out << buf[j];
    }
    return out;
}

istream& operator>>(istream& in, BigInteger& x)
{
    string s;
    if(!(in >> s))
        return in;
    x = s;
    return in;
}

测试构造函数，赋值函数和输入输出。

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
int main()
{
    // 测试构造函数
    cout << "测试构造函数" << endl;
    int n;
    cin >> n;
    BigInteger biginteger1(n);
    cout << biginteger1 << endl;
    // 测试int赋值
    cout << "测试int赋值" << endl;
    int m;
    cin >> m;
    BigInteger biginteger2;
    biginteger2 = m;
    cout << biginteger2 << endl;
    // 测试字符串赋值
    cout << "测试字符串赋值" << endl;
    string s;
    cin >> s;
    BigInteger biginteger3;
    biginteger3 = s;
    cout << biginteger3 << endl;
    // 测试从输入流赋值
    cout << "测试从输入流赋值" << endl;
    BigInteger biginteger4;
    cin >> biginteger4;
    cout << biginteger4 << endl;
    // 测试从字符流赋值
    cout << "测试从字符流赋值" << endl;
    string str;
    cin >> str;
    stringstream ss;
    BigInteger biginteger5;
    ss << str;
    ss >> biginteger5;
    cout << biginteger5 << 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& b) const;
BigInteger operator-(const BigInteger& b) const;
BigInteger operator*(const BigInteger& b) const;
BigInteger operator+=(const BigInteger& b)    // +=运算符
{
    *this = *this + b;
    return *this;
}
BigInteger operator-=(const BigInteger& b)    // -=运算符
{
    *this = *this - b;
    return *this;
}
BigInteger operator*=(const BigInteger& b)    // *=运算符
{
    *this = *this * b;
    return *this;
}

加减乘的具体实现

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
BigInteger BigInteger::operator+(const BigInteger& b) const
{
    BigInteger c;
    c.s.clear();
    int iter = 0;
    int carry = 0;
    while(iter < (int)s.size() || iter < (int)b.s.size() || carry != 0)
    {
        int x = carry;
        if(iter < (int)s.size())
            x += s[iter];
        if(iter < (int)b.s.size())
            x += b.s[iter];
        c.s.push_back(x % BASE);
        carry = x / BASE;
        ++iter;
    }
    return c;
}

BigInteger BigInteger::operator-(const BigInteger& b) const
{
    // 大数减小数
    BigInteger c;
    c.s.clear();
    int iter = 0;
    int carry = 0;
    while(iter < (int)s.size() || iter < (int)b.s.size() || carry != 0)
    {
        int x = carry;
        carry = 0;
        if(iter < (int)s.size())
            x += s[iter];
        if(iter < (int)b.s.size())
            x -= b.s[iter];
        if(x < 0)
        {
            x += BASE;
            carry = -1;
        }
        c.s.push_back(x);
        ++iter;
    }
    c.clean();
    return c;
}

BigInteger BigInteger::operator*(const BigInteger& b) const
{
    BigInteger c;
    int lena = s.size(), lenb = b.s.size(), lenc = lena + lenb;
    c.s.clear();
    c.s.assign(lenc, 0);
    for(int i = 0; i < lena; ++i)
    {
        for(int j = 0; j < lenb; ++j)
        {
            c.s[i + j] += s[i] * b.s[j];
        }
    }
    for(int i = 0; i < lenc - 1; ++i)
    {
        c.s[i + 1] += c.s[i] / BASE;
        c.s[i] %= BASE;
    }
    c.clean();
    return c;
}

$4 大数对小数除法，大数对小数取模

大数取模小数，实现上与大数除小数差不多。只是最后返回的东西不一样。

注意 operator/ 的参数是 ll，ll 就是这里指的小数。

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
// 大数对小数除法和取模
BigInteger operator/(const ll& b) const
{
    // 大数除小数
    BigInteger c;
    c.s.clear();
    c.s.assign((int)s.size(), 0);
    int carry = 0; // 高位未除尽的部分
    for(int i = (int)s.size() - 1; i >= 0; --i)
    {
        c.s[i] = (s[i] + carry * BASE) / b;
        carry = s[i] + carry * BASE - c.s[i] * b;
    }
    c.clean();
    return c;
}
BigInteger operator%(const ll& b) const
{
    long long ans = 0, lena = s.size();
    for(int i = lena - 1; i >= 0; --i)
    {
        ans = (ans * BASE + s[i]) % b;
    }
    return ans;
}
BigInteger operator/=(const long long& b) // /=运算符
{
    *this = *this / b;
    return *this;
}
BigInteger operator%=(const ll& b) // %=运算符
{
    *this = *this % b;
    return *this;
}

$5 大数除大数，大数对大数取模

接口

1
2
3
4
5
6
7
8
9
10
11
12
BigInteger operator/(const BigInteger& b) const;
BigInteger operator%(const BigInteger& b) const;
BigInteger operator/=(const BigInteger& b)  // /=运算符
{
    *this = *this / b;
    return *this;
}
BigInteger operator %= (const BigInteger& b)    // %=运算符
{
    *this = *this % b;
    return *this;
}

大数对大数的除法和取模实现

与大数对小数除法，大数对小数取模逻辑一样。只是 carry 的维护直接用 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
34
35
36
37
38
39
40
41
42
BigInteger BigInteger::operator/(const BigInteger& b) const
{
    BigInteger c;
    c.s.clear();
    c.s.assign((int)s.size(), 0);
    BigInteger carry;
    carry = 0; // 高位未除尽的部分
    for(int i = (int)s.size() - 1; i >= 0; --i)
    {
        carry = carry * BASE + s[i];
        int j = 0;
        // 求 b * j <= carry 的最大 j
        while(j < BASE)
        {
            if(carry < b * (j + 1))
                break;
            ++j;
        }
        c.s[i] = j;
        carry = carry - b * j;
    }
    c.clean();
    return c;
}

BigInteger BigInteger::operator%(const BigInteger& b) const
{
    BigInteger carry = 0;
    for(int i = (int)s.size() - 1; i >= 0; --i)
    {
        carry = carry * BASE + s[i];
        int j = 0;
        while(j < BASE)
        {
            if(carry < b * (j + 1))
                break;
            ++j;
        }
        carry = carry - b * j;
    }
    return carry;
}

$6 小于比较

小于比较的实现非常直接，就从高位到低位一位一位比较即可。基于小于比较 <，可以实现 >, <=, >=, ==, != 等比较操作。

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
bool operator < (const BigInteger& b) const    // <运算符   
{  
    if(s.size() != b.s.size()) 
        return s.size() < b.s.size();  
    for(int i = s.size() - 1; i >= 0; --i)  
        if(s[i] != b.s[i]) 
            return s[i] < b.s[i];  
    return false;  
}  
bool operator > (const BigInteger& b) const    // >运算符 
{ 
    return b < *this; 
}      
bool operator <= (const BigInteger& b) const   // <=运算符   
{ 
    return !(b < *this); 
}    
bool operator >= (const BigInteger& b) const   // >=运算符   
{ 
    return !(*this < b); 
}    
bool operator != (const BigInteger& b) const   // !=运算符   
{ 
    return b < *this || *this < b; 
}    
bool operator == (const BigInteger& b) const   // ==运算符   
{ 
    return !(b < *this) && !(*this < b); 
}

$7 完整代码 (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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <cstring>
#include <climits>

using namespace std;

using ll = long long;

struct BigInteger
{
    static const int BASE = 10;
    static const int WIDTH = 1;
    // s 保存大整数各个数位
    // 原数 1234 => s=[4,3,2,1]
    // 进制数为 BASE
    // s[i] 中保存的位数
    vector<int> s;

    // 基本功能
    void show()
    {
        for(int i: s) cout << i << " ";
        cout << endl;
    }

    // 去掉大数的前导0
    void clean()
    {
        while(!s.empty() && s.back() == 0)
            s.pop_back();
    }

    BigInteger(ll num = 0) // 构造函数
    {
        *this = num;
    }

    BigInteger operator=(ll num) // 赋值运算符
    {
        s.clear();
        do
        {
            s.push_back(num % BASE);
            num /= BASE;
        }while(num > 0);
        return *this;
    }

    BigInteger operator=(const string& str) // 赋值运算符
    {
        s.clear();
        int len = (str.length() - 1) / WIDTH + 1;
        int x;
        for(int i = 0; i < len; ++i)
        {
            int end = str.length() - i * WIDTH;
            int start = max(0, end - WIDTH);
            sscanf(str.substr(start, end - start).c_str(), "%d", &x);
            s.push_back(x);
        }
        return *this;
    }

    // 加减乘
    BigInteger operator+(const BigInteger& b) const;
    BigInteger operator-(const BigInteger& b) const;
    BigInteger operator*(const BigInteger& b) const;
    BigInteger operator+=(const BigInteger& b)    // +=运算符
    {
        *this = *this + b;
        return *this;
    }
    BigInteger operator-=(const BigInteger& b)    // -=运算符
    {
        *this = *this - b;
        return *this;
    }
    BigInteger operator*=(const BigInteger& b)    // *=运算符
    {
        *this = *this * b;
        return *this;
    }

    // 大数对小数除法和取模
    BigInteger operator/(const ll& b) const
    {
        // 大数除小数
        BigInteger c;
        c.s.clear();
        c.s.assign((int)s.size(), 0);
        int carry = 0; // 高位未除尽的部分
        for(int i = (int)s.size() - 1; i >= 0; --i)
        {
            c.s[i] = (s[i] + carry * BASE) / b;
            carry = s[i] + carry * BASE - c.s[i] * b;
        }
        c.clean();
        return c;
    }
    BigInteger operator%(const ll& b) const
    {
        long long ans = 0, lena = s.size();
        for(int i = lena - 1; i >= 0; --i)
        {
            ans = (ans * BASE + s[i]) % b;
        }
        return ans;
    }
    BigInteger operator/=(const long long& b) // /=运算符
    {
        *this = *this / b;
        return *this;
    }
    BigInteger operator%=(const ll& b) // %=运算符
    {
        *this = *this % b;
        return *this;
    }

    // 大数对大数除法和取模
    BigInteger operator/(const BigInteger& b) const;
    BigInteger operator%(const BigInteger& b) const;
    BigInteger operator/=(const BigInteger& b)  // /=运算符
    {
        *this = *this / b;
        return *this;
    }
    BigInteger operator %= (const BigInteger& b)    // %=运算符
    {
        *this = *this % b;
        return *this;
    }

    // 比较
    bool operator < (const BigInteger& b) const    // <运算符
    {
        if(s.size()!=b.s.size()) return s.size()<b.s.size();
        for(int i=s.size()-1;i>=0;i--)
            if(s[i]!=b.s[i]) return s[i]<b.s[i];
        return false;
    }
    bool operator > (const BigInteger& b) const    // >运算符
    {
        return b < *this;
    }
    bool operator <= (const BigInteger& b) const   // <=运算符
    {
        return !(b < *this);
    }
    bool operator >= (const BigInteger& b) const   // >=运算符
    {
        return !(*this < b);
    }
    bool operator != (const BigInteger& b) const   // !=运算符
    {
        return b < *this || *this < b;
    }
    bool operator == (const BigInteger& b) const   // ==运算符
    {
        return !(b < *this) && !(*this < b);
    }
};

ostream& operator<<(ostream& out, const BigInteger& x)
{
    out << x.s.back();
    for(int i = x.s.size() - 2; i >= 0; --i)
    {
        string tmp = to_string(x.s[i]);
        string buf(BigInteger::WIDTH - tmp.size(), 0);
        buf += tmp;
        for(int j = 0; j < (int)buf.size(); ++j)
            out << buf[j];
    }
    return out;
}

istream& operator>>(istream& in, BigInteger& x)
{
    string s;
    if(!(in >> s))
        return in;
    x = s;
    return in;
}


BigInteger BigInteger::operator+(const BigInteger& b) const
{
    BigInteger c;
    c.s.clear();
    int iter = 0;
    int carry = 0;
    while(iter < (int)s.size() || iter < (int)b.s.size() || carry != 0)
    {
        int x = carry;
        if(iter < (int)s.size())
            x += s[iter];
        if(iter < (int)b.s.size())
            x += b.s[iter];
        c.s.push_back(x % BASE);
        carry = x / BASE;
        ++iter;
    }
    return c;
}

BigInteger BigInteger::operator-(const BigInteger& b) const
{
    // 大数减小数
    BigInteger c;
    c.s.clear();
    int iter = 0;
    int carry = 0;
    while(iter < (int)s.size() || iter < (int)b.s.size() || carry != 0)
    {
        int x = carry;
        carry = 0;
        if(iter < (int)s.size())
            x += s[iter];
        if(iter < (int)b.s.size())
            x -= b.s[iter];
        if(x < 0)
        {
            x += BASE;
            carry = -1;
        }
        c.s.push_back(x);
        ++iter;
    }
    c.clean();
    return c;
}

BigInteger BigInteger::operator*(const BigInteger& b) const
{
    BigInteger c;
    int lena = s.size(), lenb = b.s.size(), lenc = lena + lenb;
    c.s.clear();
    c.s.assign(lenc, 0);
    for(int i = 0; i < lena; ++i)
    {
        for(int j = 0; j < lenb; ++j)
        {
            c.s[i + j] += s[i] * b.s[j];
        }
    }
    for(int i = 0; i < lenc - 1; ++i)
    {
        c.s[i + 1] += c.s[i] / BASE;
        c.s[i] %= BASE;
    }
    c.clean();
    return c;
}

BigInteger BigInteger::operator/(const BigInteger& b) const
{
    BigInteger c;
    c.s.clear();
    c.s.assign((int)s.size(), 0);
    BigInteger carry;
    carry = 0; // 高位未除尽的部分
    for(int i = (int)s.size() - 1; i >= 0; --i)
    {
        carry = carry * BASE + s[i];
        int j = 0;
        // 求 b * j <= carry 的最大 j
        while(j < BASE)
        {
            if(carry < b * (j + 1))
                break;
            ++j;
        }
        c.s[i] = j;
        carry = carry - b * j;
    }
    c.clean();
    return c;
}

BigInteger BigInteger::operator%(const BigInteger& b) const
{
    BigInteger carry = 0;
    for(int i = (int)s.size() - 1; i >= 0; --i)
    {
        carry = carry * BASE + s[i];
        int j = 0;
        while(j < BASE)
        {
            if(carry < b * (j + 1))
                break;
            ++j;
        }
        carry = carry - b * j;
    }
    return carry;
}


int main()
{
    BigInteger b1, b2;
    cin >> b1 >> b2;
    b1.show();
    b2.show();
    cout << "+ " << b1 + b2 << endl;
    cout << "- " << b1 - b2 << endl;
    cout << "* " << b1 * b2 << endl;
    cout << "/ " << b1 / b2 << endl;
    cout << "% " << b1 % b2 << endl;
}
Share