大整数四则运算模板
1.大整数加法运算模板
总结步骤:将对应位上的数字和进位相加,得到的结果取个位数作为该位结果,取十位数作为新的进位。
//大整数加法
bign add(bign a,bign b){
bign c;
int carry =0 ; //carry 是进位
for(int i=0;i<a.len|| i<b.len;i++){ //以较长的为界限
int temp = a.data[i] + b.data[i] +carry; //两个对应位的数与进位相加
c.data[c.len++] = temp%10; //个位数作为该位结果
carry =temp/10;
}
if(carry!=0){
c.data[c.len++]=carry;
}
return c;
}
2.大整数减法运算模板
总结步骤:对每一步,比较被减位和减位,如果不够减,则令减位的高位减1,被减位+10在进行减法;
如果够减,则直接减。
最后一步要注意减法后高位可能有多余的0,要去除他们,但也要保证结果至少有一位数。
//大整数减法运算模板
bign sub(bign a,bign b){ //高精度a-b
bign c;
for( int i=0;i<a.len || i <b.len;i++){ //以较长的为界限
if(a.data[i] < b.data[i]){ //如果不够减
a.data[i+1]--; //向高位借1
a.data[i]+=10; //当前位+10
}
c.data[i] = a.data[i] - b.data[i]; //减法结果为当前结果
}
while(c.len-1 >=1 && c.data[c.len-1]==0){
c.len--; //取出高位的0,同时至少保留一位最低位
}
return c;
}
最后,需要指出的是,使用sub()之前,必须要比较两个数的大小,如果被减数小于减数,需要交换两个变量,然后输出负号,再使用sub()函数。
3.大整数乘法运算模板
总结步骤:取bign的某位与int型的整体相乘,再与进位相加,所得结果的个位数作为该位结果,高位部分作为新的进位。
//大整数乘法运算模板
bign multi(bign a,int x){
bign c;
int carry =0;
for(int i=0;i<a.len;i++){
int temp= a.data[i]*x +carry;
c.data[c.len++] = temp%10;
carry =temp/10;
}
while(carry!= 0){
c.data[len++] = carry%10;
carry /= 10;
}
return c;
}
4.大整数除法运算模板
总结步骤:上一步的余数x10加上该步的位,得到该步临时的被除数,将其与除数比较:
如果不够除,则该位的商为0;
//大整数除法运算模板
bign divide(bign a,int b,int& r){ //高精度除法,r为余数
bign c;
c.len = a.len; //被除数的每一位和商的每一位是一一对应的,因此先令长度相等
for(int i=a.len-1;i>=0;i--){ //从高位开始
r = r*10 + a.data[i]; //和上一位遗留的余数组合
if(r<b){
c.data[i] =0;
}else{ //够除
c.data[i] = r/b; //商
r=r%b; //获得新的余数
}
}
while( c.len-1>=1 && c.data[c.len-1]==0 ){
c.len--; //去除高位的0,同时至少保留最后一位最低位
}
return c;
}
最后一步要注意减法后高位可能有多余的0,要去除他们,但也要保证结果至少有一位数。