一般数据范围： int型：10^9 long long型：10^18 double型：10^308 如果要存储的数据比这些还大，就需要使用大整数运算
大整数的存储
用数组将大整数的每一位数一次存储 整数的高位存储在数组的高位，整数的低位存储在数组的低位 (如235813有:d[0] = 3, d[1] = 1, d[2] = 8, d[3] = 5, d[4] = 3, d[5] = 2) 因为加法减法乘法都是从低位遍历到高位，只有除法从高位开始 所以加法减法乘法即时更新长度，而除法的长度提前确定一般会定义一个d数组和记录长度的len组成的结构体来表示大整数
struct bign
{
int d
[1000];
int len
;
bign()
{
memset(d
,0,sizeof(d
));
len
= 0;
}
};
大整数的四则运算
高精度加法
bign
add(bign a
, bign b
)
{
bign c
;
int carry
= 0;
for(int i
= 0; i
< a
.len
|| i
< b
.len
; i
++)
{
int temp
= a
.d
[i
] + b
.d
[i
] + carry
;
c
.d
[c
.len
++] = temp
%10;
carry
= temp
/10;
}
if(carry
)
{
c
.d
[c
.len
++] = carry
;
}
return c
;
}
高精度减法(减法后高位可能有多余的0，要除去它们，也要保证结果至少有一位数)
bign
sub(bign a
, bign b
)
{
bign c
;
for(int i
= 0; i
< a
.len
|| i
< b
.len
; i
++)
{
if(a
.d
[i
] < b
.d
[i
])
{
a
.d
[i
+1]--;
a
.d
[i
] += 10;
}
c
.d
[c
.len
++] = a
.d
[i
] - b
.d
[i
];
}
while(c
.len
- 1 > 0 && c
.d
[len
-1] == 0)
{
c
.len
--;
}
return c
;
}
tip：乘除法a和b中如果存在负数，需要先记录下其负号，然后取它们的绝对值代入函数
高精度与低精度的乘法
bign
multi(bign a
, int b
)
{
bign c
;
int carry
= 0;
for(int i
= 0; i
< a
.len
; i
++)
{
int temp
= a
.d
[i
] * b
+ carry
;
c
.d
[c
.len
++] = temp
%10;
carry
= temp
/10;
}
while(carry
)
{
c
.d
[len
++] = carry
%10;
carry
/= 10;
}
return c
;
}
高精度与低精度的除法
bign
divide(bign a
, int b
, int &r
)
{
bign c
;
c
.len
= a
.len
;
for(int 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
- 1 > 0 && c
.d
[c
.len
- 1] == 0)
{
c
.len
--;
}
return c
;
}
