当前位置：首页 > news >正文

大整数运算详解升级版

news 来源：原创 2024/9/20 9:37:05

大整数的存储

大整数的四则运算

高精度加法

高精度减法

高精度与低精度的乘法

高精度与低精度的除法

大整数的存储

对于大整数使用数组存储，例如定义int型数组d[1000]，那么这个数组中的每一位就代表了存放的整数的每一位。如将整数235813存储到数组中，则有d[0]=3,d[1]=1,d[2]=8,d[3]=5,d[4]=3,d[5]=2,即整数的高位存储在数组的高位，整数的低位存储在数组的低位。不反过来存储的原因是，在进行运算的时候都是从整数低位到高位进行枚举，顺位存储和这种思维相和。但是也会由此产生一个需要注意的问题：把整数按照字符串%s读入的时候，实际上是逆位存储的，即str[0]='2',str[1]='3',……,str[5]='3'，因此在读入之后需要在另存为d[]数组的时候反转一下。

而为了方便随时获取大整数的长度，一般都会定义一个int型变量len来记录其长度，并和d数组组合成结构体。

struct bign{int d[1000];int len;
};

显然，在定义结构体变量之后，需要马上初始化结构体，为了减少在实际输入代码时总是忘记初始化的问题，在结构体内部加上以下代码：

	bign(){memset(d,0,sizeof(d));len=0;}

因此大整数结构体就变成了这样：

struct bign{int d[1000];int len;bign(){memset(d,0,sizeof(d));len=0;}
};

这样在每次定义结构体变量时，都会自动对该变量进行初始化。

而输入大整数时，一般都是先用字符串读入，然后再把字符串另存为bign结构体。由于使用char数组进行读入时，整数的高位会变成数组的低位，而整数的低位会变成数组的高位，因此为了让整数在bign中是顺序存储，需要让字符串倒着赋给d[]数组。

bign change(char str[]){bign a;a.len=strlen(str);for(int i=0;i<a.len;i++){a.d[i]=str[a.len-i-1]-'0';}return 0;
}

如果要比较两个bign变量的大小，规则也很简单：先判断两者的 len大小，如果不相等，则以长的为大；如果相等，则从高位到低位进行比较，直到出现某一位不等，就可以判断两个数的大小。具体代码如下：

int compare(bign a,bign b){if(a.len>b.len){return 1;//a大 }else if(a.len<b.len){return -1;//b大 }else{for(int i=a.len-1;i>=0;i--){if(a.d[i]>b.d[i]){return 1;}else if(a.d[i]<b.d[i]){return -1;}}return 0;//两数相等 }
}

接下来主要介绍四个运算：（1）高精度加法；（2）高精度减法；（3）高精度与低精度的乘法；（4）高精度与低精度的除法。

大整数的四则运算

高精度加法

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

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!=0){c.d[c.len++]=carry;}return 0;
}

下面是完整的A+B的代码。

#include<stdio.h>
#include<string.h>
struct bign{int d[1000];int len;bign(){memset(d,0,sizeof(d));len=0;}
};
bign change(char str[]){bign a;a.len=strlen(str);for(int i=0;i<a.len;i++){a.d[i]=str[a.len-i-1]-'0';}return a;
}
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!=0){c.d[c.len++]=carry;}return c;
}
void print(bign a){for(int i=a.len-1;i>=0;i--){printf("%d",a.d[i]);}
}
int main(){char str1[1000],str2[1000];scanf("%s%s",str1,str2);bign a=change(str1);bign b=change(str2);print(add(a,b));return 0;
}

最后指出，这样写法的条件是两个对象都是非负整数。如果有一方是负的，可以在转换到数组这一步时去掉其负号，然后采用高精度减法；如果两者都是负的，就都去掉负号后用高精度加法，最后把负号再加回去即可。

高精度减法

对某一步，比较被减位和减位，如果不够减，则令被减位的高位减1，被减位加10再进行减法；如果够减，则直接减。最后一步要注意减法后高位可能有多余的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>=1&&c.d[c.len-1]==0){c.len--;}return c;
}

高精度减法的完整代码即为把上面的sub函数替代高精度加法中add函数的位置即可，记得调用的时候也是用sub函数。

高精度与低精度的乘法

取bign的某位与int型整体相乘，再与进位相加，所得结果的个位数作为该位结果，高位部分作为新的进位。

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!=0){c.d[c.len++]=carry%10;carry/=10;}return c;
}

完整的A*B的代码只需要把高精度加法中的add函数改成这里的multi函数，并注意输入的时候b是作为int型输入即可。

高精度与低精度的除法

上一步的余数乘以10加上该步的位，得到该步临时的被除数，将其与除数比较：如果不够除，则该位的商为0；如果够除，则商即为对应的商，余数即为对应的余数。最后一位要注意减法后高位可能有多余的0，要忽视它们，但也要保证结果至少有一位数。

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>=1&&c.d[c.len-1]==0){c.len--;}return c;
}

在上述代码中，考虑到函数每次只能返回一个数据，而很多题目里面会经常要求得到余数，因此把余数写成引用的形式直接作为参数传入，或是把r设成全局变量。