抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

C/C++中,当进行整数计算时,最多可以储存一个8bye的数据,也就是$2^{64}$,超过这个限度的数字,没有其他的数据类型来储存。所以就需要高精度来解决这一问题

存储

高精度可以使用字符串或者数组来表示,在存储时逆序存储,在输出时逆序输出

头文件及全局变量

1
2
3
4
#include <bits/stdc++.h>
static const int LEN = 1004;
int a[LEN], b[LEN], c[LEN], d[LEN];
int flag;

清空

1
2
3
4
void clean(int temp[]) {
for (int i = 0; i < LEN; ++i)
temp[i] = 0;
}

存储

1
2
3
4
5
6
7
8
9
10
11
void read(int temp[]) {
static char s[LEN + 1];
scanf("%s", s);

clean(temp);

int len = strlen(s);
for (int i = 0; i < len; ++i) {
temp[len - 1 - i] = s[i] - '0';
}
}

输出

1
2
3
4
5
6
7
8
9
void print(int a[]) {
int i;
for (i = LEN - 1; i >= 1; --i)
if (a[i] != 0)
break;
for (; i >= 0; i--)
putchar(a[i] + '0');
putchar('\n');
}

这样就完成了对于数据的存储与输出

加法

高精度加法其实就是按照竖式加法法则来计算

从低位开始相加,满十则向高一位进一,本位取余

这里使用十进制,也可以使用其他更大的进制,如1000进制

1
2
3
4
5
6
7
8
9
10
11
//高精度加法
void add(int a[], int b[], int c[]) {
clean(c);
for (int i = 0; i < LEN - 1; i++) {
c[i] = a[i] + b[i];
if (c[i] > 9) {//判断是否满十
c[i] -= 10;
c[i + 1] += 1;
}
}
}

减法

高精度减法同样也是按照竖式减法逐位相减,减不过向高一位借一。

因为要考虑到小数减大数的情况,所以用此函数来判断

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
bool compare(int a[], int b[]) {
int i, j;
for (i = LEN - 1; i >= 1; --i)
if (a[i] != 0)
break;
for (j = LEN - 1; j >= 1; --j)
if (b[j] != 0)
break;

if (i > j) {
return 0;
} else if (i < j) {
return 1;
} else {
for (int p = i; p >= 0; --p) {
if (a[p] == b[p])
continue;

if (a[p] > b[p])
return 0;
else
return 1;
}
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//高精度减法
void sub(int* a, int* b, int* c) {
flag = compare(a, b);//判断是否是小数减大数
if (flag) {//如果是
putchar('-');//则输出负号
sub(b, a, c);//按照大数减小数计算
flag = 0;
return;
}

clean(c);
for (int i = 0; i < LEN - 1; i++) {
c[i] += a[i] - b[i];
if (c[i] < 0) {
c[i] += 10;
c[i + 1] -= 1;
}
}
}

乘法

高精度*低精度

如果是高精度与低精度相乘的话,就没必要使用高精度乘法

1
2
3
4
5
6
7
8
9
10
11
12
void mul(int a[], int b, int c[]) {
clean(c);

for (int i = 0; i < LEN - 1; ++i) {
c[i] += a[i] * b;//每位都乘低精度

if (c[i] > 9) {
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
}
}

高精度*高精度

高精度与高精度相乘也是模拟了手写计算乘法的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//高精度乘法
void mul(int a[], int b[], int c[]) {
clean(c);
for (int i = 0; i < LEN - 1; i++) {
// 第 i 次循环为 c[i] 加上了所有满足 p + q = i 的 a[p] 与 b[q] 的乘积之和
for (int j = 0; j <= i; j++) {
c[i] += a[j] * b[i - j];
}

if (c[i] > 9) {
c[i + 1] = c[i] / 10;
c[i] %= 10;
}
}
}

除法

1
2
3
4
5
6
7
8
9
10
11
12
//判断长度
inline bool greater_eq(int a[], int b[], int last_dg, int len) {
if (a[last_dg + len] != 0)
return true;
for (int i = len - 1; i >= 0; --i) {
if (a[last_dg + i] > b[i])
return true;
if (a[last_dg + i] < b[i])
return false;
}
return true;
}
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
//高精度除法
void div(int a[], int b[], int c[], int d[]) {
clean(c);
clean(d);

int la, lb;
for (la = LEN - 1; la > 0; --la)
if (a[la - 1] != 0)
break;
for (lb = LEN - 1; lb > 0; --lb)
if (b[lb - 1] != 0)
break;
if (lb == 0) {
puts("除数为零,错误");
return;
}

for (int i = 0; i < la; ++i) d[i] = a[i];
for (int i = la - lb; i >= 0; --i) {
while (greater_eq(d, b, i, lb)) {
for (int j = 0; j < lb; ++j) {
d[i + j] -= b[j];
if (d[i + j] < 0) {
d[i + j + 1] -= 1;
d[i + j] += 10;
}
}
c[i] += 1;
}
}
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main() {
flag = 0;
read(a);
read(b);

add(a, b, c);
print(c);

sub(a, b, c);
print(c);

mul(a, b, c);
print(c);

div(a, b, c, d);
print(c);
print(d);
return 0;
}

评论