算法笔记 大整数运算

大整数又称为高精度整数，其含义就是用基本数据结构无法存储其精度的整数。

一、大整数的存储

1.如何存储

用数组存储，并将整数的高位存储在数组的高位，整数的低位存储在数组的低位。因为在进行运算时都是从整数的低位到高位进行枚举。因为直接读入的话顺序会反过来，因此需要在读入时存在一个临时数组，反转后再存储。

例如：

整数 235813 ，

直接读入 d[0] = 2, d[1] = 3, d[2] = 5, d[3] = 8, d[4] = 1, d[5] = 3 ，

反转后存储 d[0] = 3, d[1] = 1, d[2] = 8, d[3] = 5, d[4] =3, d[5] = 2

2.结构体

为了方便获取大整数的长度，一般会定义一个 int 型变量 len 来记录其长度，可以组合成结构体。

1
2
3
4
struct bignum{
	int d[1000];
	int len;
};

3.初始化

在定义结构体变量后，应该马上初始化结构体。

还可以通过构造函数的方法方便地初始化结构体：

1
2
3
4
bignum(){
	memset(d, 0, sizeof(d));
	len = 0;
}

将构造函数放入结构体中：

1
2
3
4
5
6
7
8
struct bignum{
	int d[1000];
	int len;
	bignum(){
		memset(d, 0, sizeof(d));
		len = 0;
	}
};

相关博文：

4.存储大整数

先用字符串方式读入，然后再将字符串转存到结构体中。

1
2
3
4
5
6
7
8
struct bignum(char str[]){
	int i;
	struct bignum a;
	a.len = stelen(str);
	for (i = 0; i < a/len; i++)
		a.d[i] = str[a.len - i - 1] - '0';  //反着存入，字符转为数字
	return a;
}

​

二、大整数的比较

先判断二者 len 的大小：

  • 如果不相等，则长的为大

  • 如果相等，再从高位到低位进行比较，直到出现某一位不相等为止。

1
2
3
4
5
6
7
8
9
10
int compare(struct bignum a, struct bignum b){
	if (a.len > b.len)    return 1;
	if (a.len < b.len)    return -1;
	int i;
	for (i = a.len; i >= 0; i--){
		if (a.d[i] > b.d[i])    return 1;
		if (a.d[i] < b.d[i])    return -1;
	}
	return 0;
}

​

三、大整数加法

将两个数字与进位相加，得到的数字个位数作为该位结果，取十位数作为新的进位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct bignum add(struct bignum a, struct bignum b){
	struct bignum c;
	int i;
	int temp;
	int carry = 0;  //进位
	for (i = 0; i < a.len || i < b.len; i++){
		temp = a.d[i] + b.d[i] + carry;
		c.d[c.len++] = temp % 10;
		carry = temp / 10;
	}
	if (carry != 0){
		c.d[c.len++] = carry;
	}
	return c;
}

​

四、大整数减法

比较被减位和减位：

  • 如果不够减，则令被减位的高位减 1 ，被减位加 10 再做减法
  • 如果够减，则直接减。

最后需要注意减法后高位可能有多余的 0 ，要去除它们，但也要保证结果至少有一个数。在使用此函数前需要先比较两个数大小，若被减数小于减数，则交换两个变量，输出负号，再使用此函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct bignum sub(struct bignum a, struct bignum b){
	struct bignum c;
	int i;
	for(i = 0; i < a.len || i < b.len; i++){
		if (a.d[i] < b.d[i]){
			a.d[i + 1]--;
			a.[d] += 10;
		}
		c.d[c.len++] = a.d[i] - b.d[i];
	}
	while (c.len >= 2 && c.d[c.len - 1] == 0)
    	c.len--;
    return c;
}

​

五、大整数和普通数的乘法

将大整数的每一位与普通数整体相乘，再与进位相加，所得结果的个位数作为该位结果，高位部分作为新的进位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct bignum multi(struct bignum a, int b
	struct bignum c;
	int temp;
	int carry = 0;  //进位
	int i;
	for (i = 0; i < a.len; i++){
		temp = a.d[i] * b + carry;
		c.d[c.len++] = temp % 10;
		carry = temp / 10;
	}
	while (carry != 0){
		c.d[c.len++] = carry % 10;
		carry /= 10;
	}
	return c;
}

六、大整数和普通数的除法

上一步的余数乘以 10 加上该位上的数，得到此步的临时被除数，将其与除数比较：

  • 如果不够除，则该位的商为 0
  • 如果够除，则商即为该位的商，余数即为该位的余数

最后需要注意是否有多余的 0 ，去除它们，但至少保留一位数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct bignum divide(struct bignum a, int b, int &r){  //r为余数
	struct bignum c;
	c.len = a.len;
	int i;
	for (i = a.len - 1; i >= 0; i--){
		r = r * 10 + a.d[i];
		if (r < b)    c.d[i] = 0;
		else{
			c.d[i] = r / b;
			r = r % b;
		}
	}
	while (c.len >= 2 && c.d[c.len - 1] == 0)    c.len--;
	return c;
}

​

参考

  • 算法笔记