java 进行超大整数的加减乘除四则运算（自己部分实现BigInteger）
程序员文章站
2022-05-23 12:22:05
问题分析： 加减运算： 两数进行加减，都可以转为两个基本运算： 两个非负数相加 plusAdd（） 一个较大的非负数减去一个不大于前一个数的非负数 plusMinus() 假设num1 , num2 分别为被加数 、加数，则最终结果只可能是以下情况： 上面四种情况可以转为： 减法类似。 乘法运算： ......
问题分析：
加减运算：
两数进行加减，都可以转为两个基本运算：
- 两个非负数相加--------------- plusadd（）
1 private stringbuffer plusadd(string strnum1,string strnum2){
2 //把两个数字字符串倒置，并存入字符数组
3 char [] num1 = new stringbuffer(strnum1).reverse().tostring().tochararray();
4 char [] num2 = new stringbuffer(strnum2).reverse().tostring().tochararray();
5 int maxlength = math.max(num1.length,num2.length);
6 int minlength = math.min(num1.length,num2.length);
7 //n位和m位的非负整数相加的和，要么是max（n，m）位，要么是max（n，m）+1位。
8 stringbuffer value = new stringbuffer();
9
10 /*--------------计算和数开始------------------------*/
11 int i,jinwei=0;
12 for(i=0;i<minlength;i++){
13 int temp = jinwei + num1[i] - '0' +num2[i] - '0';
14 value.append((char)(temp%10 + '0'));
15 jinwei = temp/10;
16 }
17 if(maxlength == num1.length)
18 jinwei = onebitadd(jinwei,num1,i,maxlength,value);
19 else
20 jinwei = onebitadd(jinwei,num2,i,maxlength,value);
21 if(jinwei != 0)
22 value.append((char)(jinwei +'0'));
23 /*--------------计算和数结束------------------------*/
24 return deletezero(value).reverse();
25 }
- 一个较大的非负数减去一个不大于前一个数的非负数 ----- plusminus()
1 private stringbuffer plusminus(string bignumstr,string smallnumstr){
2 //把两个数字字符串倒置，并存入字符数组
3 char [] num1 = new stringbuffer(bignumstr).reverse().tostring().tochararray();
4 char [] num2 = new stringbuffer(smallnumstr).reverse().tostring().tochararray();
5 stringbuffer value = new stringbuffer();
6
7 /*--------------计算减法开始------------------------*/
8 int i,temp,jiewei = 0;
9 for(i = 0;i<smallnumstr.length();i++){
10 temp = num1[i] - jiewei - num2[i];
11 jiewei = onebitminus(temp,value,i);
12 }
13 //处理较大数比较小数多出来的位
14 for(;i<bignumstr.length();i++){
15 temp = num1[i] - '0' - jiewei;
16 jiewei = onebitminus(temp,value,i);
17 }
18 /*--------------计算减法结束------------------------*/
19 return deletezero(value).reverse();
20 }
假设num1 , num2 分别为被加数 、加数，则最终结果只可能是以下情况：
- num1 非负数 num2 非负数
- num1 负数 num2 负数 、
- num1 非负数 num2 负数
- num1 负数 num2 非负数
上面四种情况可以转为：
- plusadd(num1,num2)
- - plusadd(- num1,- num2)
- plusminus(num1,- num2)
- plusminus(num2,- num2)
减法类似。
乘法运算：
乘法也可以转化为一个基本运算： 两个正整数相乘----plusmulti()
private stringbuffer plusmulti(stringbuffer str1,stringbuffer str2) {
//新建两个stringbuffer，存储两数的前后倒置。
stringbuffer num1 = new stringbuffer(str1.substring(0)).reverse();
stringbuffer num2 = new stringbuffer(str2.substring(0)).reverse();
stringbuffer array = new stringbuffer();
//n位数和m位数相乘，得到的结果的位数只能是n+m或者n+m-1。
int len = str1.length() + str2.length();
for(int i = 0;i<len-1;i++){
array.append('0');
}
//标志n+m位
array.append('+');
//模拟竖式计算
for(int i = 0,j,jinwei = 0 ; i < str2.length() ; i++){
jinwei = 0; //进位归位
for(j = 0 ; j < str1.length() ; j++){
int temp = (num2.charat(i)-'0')*(num1.charat(j)-'0') + jinwei + array.charat(i+j) - '0';
array.setcharat(i+j,(char)(temp%10 + '0'));
jinwei = temp /10;
}
if(jinwei !=0)
array.setcharat(i+j, (char)(jinwei +'0'));
}
if(array.charat(len -1) == '+')
array.setlength(len-1);
return array.reverse();
}
各种情况只和plusmulti()有正负号的区别。其中一个数为0时，直接返回0即可。
除法运算：
模拟手算除法的过程。
除法也可以转化为一个基本运算，两个非负数相除，除数不为0。-------------plusdivide()
1 private stringbuffer plusdivide(string str1,string str2){ //str1 / str2
2 stringbuffer division = new stringbuffer();
3 stringbuffer remain = new stringbuffer();
4
5 int end = 0;
6 boolean flag = false; //标志在不够除时，是否需要上0。
7 while(end < str1.length()){
8 remain.append(str1.charat(end)); //从被除数那里取一位
9 if(str1thanstr2(remain.tostring(),str2)){//能整除
10 flag = true;
11 int fullnum = greatst(remain,str2);
12 stringbuffer fullnumstr2 = plusmulti(new stringbuffer(str2),new stringbuffer(""+fullnum));
13 division.append(""+fullnum);
14 remain = plusminus(remain.tostring(),fullnumstr2.tostring());
15 }
16 else if(flag)//不够除，补0
17 division.append("0");
18 if(remain.tostring().equals("0"))
19 remain.setlength(0);
20 end++;
21 }
22 if(division.length() == 0){
23 return division.append('0');
24 }
25 return division;
26 }
各种情况至于plusdivide()只有符号的区别，除数为0时，特别处理下即可。
代码简介：
对外开放了四个方法：加减乘除。
- public mybiginteger minus(mybiginteger t) 减法
- public mybiginteger multi(mybiginteger t) 乘法
- public mybiginteger add(mybiginteger str) 加法
- public mybiginteger divide(mybiginteger t) 除法
测试：
乘法：进行10000！的运算，与用biginteger类得到的结果一样。四种情况都测试了，结果一致。至少一个数为0时，也得到了了0。值得信赖！
其他的三种，测试没有乘法详细，如果有bug欢迎指出。
下面的main函数中，提供了
(175 + 231 - 143)*(-1978654)/(-54)
完整代码如下：
1
2 public class mybiginteger {
3 private stringbuffer data;
4
5
6 public mybiginteger(){
7 data = new stringbuffer("0");
8 }
9 public mybiginteger(string str){
10 data = new stringbuffer(str);
11 }
12 public mybiginteger(stringbuffer str){
13 data = new stringbuffer(str);
14 }
15
16 public int length(){
17 return data.length();
18 }
19 public string tostring(){
20 return data.tostring();
21 }
22
23 public boolean equals(object obj){
24 return data == ((mybiginteger)obj).data;
25 }
26
27 /**
28 * 功能：进行两个非负整数的相加
29 */
30 private stringbuffer plusadd(string strnum1,string strnum2){
31 //把两个数字字符串倒置，并存入字符数组
32 char [] num1 = new stringbuffer(strnum1).reverse().tostring().tochararray();
33 char [] num2 = new stringbuffer(strnum2).reverse().tostring().tochararray();
34 int maxlength = math.max(num1.length,num2.length);
35 int minlength = math.min(num1.length,num2.length);
36 //n位和m位的非负整数相加的和，要么是max（n，m）位，要么是max（n，m）+1位。
37 stringbuffer value = new stringbuffer();
38
39 /*--------------计算和数开始------------------------*/
40 int i,jinwei=0;
41 for(i=0;i<minlength;i++){
42 int temp = jinwei + num1[i] - '0' +num2[i] - '0';
43 value.append((char)(temp%10 + '0'));
44 jinwei = temp/10;
45 }
46 if(maxlength == num1.length)
47 jinwei = onebitadd(jinwei,num1,i,maxlength,value);
48 else
49 jinwei = onebitadd(jinwei,num2,i,maxlength,value);
50 if(jinwei != 0)
51 value.append((char)(jinwei +'0'));
52 /*--------------计算和数结束------------------------*/
53 return deletezero(value).reverse();
54 }
55 /**
56 * 进位加上字符数组一部分
57 * @return
58 */
59 private int onebitadd(int jinwei,char []array,int beginindex,int endindex,stringbuffer value){
60 int temp;
61 for(int i = beginindex;i<endindex;i++){
62 temp = jinwei + array[i] - '0';
63 jinwei = temp/10;
64 value.append((char)(temp%10+'0'));
65 }
66 return jinwei;
67 }
68
69 /**
70 * 功能：较大的非负整数bignumstr减去较小的非负整数smallnumstr
71 */
72 private stringbuffer plusminus(string bignumstr,string smallnumstr){
73 //把两个数字字符串倒置，并存入字符数组
74 char [] num1 = new stringbuffer(bignumstr).reverse().tostring().tochararray();
75 char [] num2 = new stringbuffer(smallnumstr).reverse().tostring().tochararray();
76 stringbuffer value = new stringbuffer();
77
78 /*--------------计算减法开始------------------------*/
79 int i,temp,jiewei = 0;
80 for(i = 0;i<smallnumstr.length();i++){
81 temp = num1[i] - jiewei - num2[i];
82 jiewei = onebitminus(temp,value,i);
83 }
84 //处理较大数比较小数多出来的位
85 for(;i<bignumstr.length();i++){
86 temp = num1[i] - '0' - jiewei;
87 jiewei = onebitminus(temp,value,i);
88 }
89 /*--------------计算减法结束------------------------*/
90 return deletezero(value).reverse();
91 }
92 /**
93 * 删去多余的0
94 */
95 private stringbuffer deletezero(stringbuffer str){
96 int num=0;
97 for(int i = str.length()-1;i>=0;i--){
98 if(str.charat(i) == '0')
99 num++;
100 else
101 break;
102 }
103 if(num != str.length())
104 str.setlength(str.length()-num);
105 else
106 str = new stringbuffer("0");
107 return str;
108 }
109 /**
110 * 一位减法
111 */
112 private int onebitminus(int flag,stringbuffer value,int num){
113 int jiewei;
114 if(flag <0){
115 value.append((char)(10 +flag + '0'));
116 jiewei = 1;
117 }
118 else{
119 jiewei = 0;
120 value.append((char)(flag + '0'));
121 }
122 return jiewei;
123 }
124
125 /**
126 * 名称：内部调用的减法。
127 * 功能：两个非负数相减。
128 * 结果：返回运算结果的前后倒置。
129 */
130 private stringbuffer innerminus(string str1,string str2){
131 stringbuffer temp;
132 if(str1thanstr2(str1,str2))//若str1更大
133 temp = plusminus(str1,str2);
134 else{
135 temp = plusminus(str2,str1);
136 if(!temp.tostring().equals("0"))
137 temp.reverse().append('-').reverse();
138 }
139 return temp;
140 }
141 /**
142 * 判断正负
143 * true -- 非负 false -- 负
144 */
145 public boolean isnonegative(mybiginteger t){
146 if(t.data.charat(0) == '-')
147 return false;
148 return true;
149 }
150
151 /**
152 * 对外开放的加法接口
153 * 计算str1 + str2
154 */
155 public mybiginteger add(mybiginteger str){
156 //两数都非负
157 if(isnonegative(this) && isnonegative(str))
158 data = plusadd(data.tostring(),str.data.tostring());
159 else if(!isnonegative(this) && !isnonegative(str)){
160 stringbuffer temp = plusadd(data.substring(1),str.data.substring(1));
161 if(!temp.tostring().equals("0"))
162 data = temp.reverse().append('-').reverse();
163 else
164 data = temp;
165 }
166 else if(!isnonegative(this) && isnonegative(str))
167 data = innerminus(str.data.tostring(),data.substring(1));
168 else
169 data = innerminus(data.tostring(),str.data.substring(1));
170 return this;
171 }
172 /**
173 * 对外开放的减法。
174 * 计算str1 - str2
175 */
176 public mybiginteger minus(mybiginteger t){
177 //两数都为正。
178 if(isnonegative(this) && isnonegative(t))
179 data = innerminus(this.data.tostring(),t.data.tostring());
180 //两数都为负时，需要对innerminus得到的结果逆转正负。
181 else if(!isnonegative(this) && !isnonegative(t))
182 data = innerminus(t.data.substring(1),data.substring(1));
183 //this 为负，t为非负。
184 else if(!isnonegative(this) && isnonegative(t)){
185 stringbuffer temp = plusadd(data.substring(1),t.data.tostring());
186 if(!temp.tostring().equals("0"))
187 data = temp.reverse().append('-').reverse();
188 else
189 data = temp;
190 }
191 //this 为非负，str为负。
192 else
193 data = plusadd(data.tostring(),t.data.substring(1).tostring());
194 return this;
195 }
196
197 /**
198 * 内部使用的两个正整数乘法
199 */
200 private stringbuffer plusmulti(stringbuffer str1,stringbuffer str2) {
201 //新建两个stringbuffer，存储两数的前后倒置。
202 stringbuffer num1 = new stringbuffer(str1.substring(0)).reverse();
203 stringbuffer num2 = new stringbuffer(str2.substring(0)).reverse();
204 stringbuffer array = new stringbuffer();
205 //n位数和m位数相乘，得到的结果的位数只能是n+m或者n+m-1。
206 int len = str1.length() + str2.length();
207 for(int i = 0;i<len-1;i++){
208 array.append('0');
209 }
210 //标志n+m位
211 array.append('+');
212
213 //模拟竖式计算
214 for(int i = 0,j,jinwei = 0 ; i < str2.length() ; i++){
215 jinwei = 0; //进位归位
216 for(j = 0 ; j < str1.length() ; j++){
217 int temp = (num2.charat(i)-'0')*(num1.charat(j)-'0') + jinwei + array.charat(i+j) - '0';
218 array.setcharat(i+j,(char)(temp%10 + '0'));
219 jinwei = temp /10;
220 }
221 if(jinwei !=0)
222 array.setcharat(i+j, (char)(jinwei +'0'));
223 }
224 if(array.charat(len -1) == '+')
225 array.setlength(len-1);
226 return array.reverse();
227 }
228 /**
229 * 对外开放的乘法
230 */
231 public mybiginteger multi(mybiginteger t){
232 //两数至少有一个为0
233 if(data.tostring().equals("0") || t.data.tostring().equals("0"))
234 data = new stringbuffer("0");
235 else{
236 //两数都是正数
237 if(isnonegative(this) && isnonegative(t))
238 data = plusmulti(data,t.data).reverse();
239 //两数都是负数
240 else if(!isnonegative(this) && !isnonegative(t))
241 data = plusmulti(new stringbuffer(data.substring(1)),new stringbuffer(t.data.substring(1)));
242
243 //两数一正一负
244 else if(isnonegative(this) && !isnonegative(t))
245 data = plusmulti(data,new stringbuffer(t.data.substring(1))).reverse().append('-').reverse();
246 else
247 data = plusmulti(new stringbuffer(data.substring(1)),t.data).reverse().append('-').reverse();
248 }
249 return this;
250 }
251 /**
252 * 两个非负数相除，除数不为0
253 * 返回：没有前后倒置的正确的结果
254 */
255 private stringbuffer plusdivide(string str1,string str2){
256 stringbuffer division = new stringbuffer();
257 stringbuffer remain = new stringbuffer();
258
259 int end = 0;
260 boolean flag = false;
261 while(end < str1.length()){
262 remain.append(str1.charat(end));
263 if(str1thanstr2(remain.tostring(),str2)){//能整除
264 flag = true;
265 int fullnum = greatst(remain,str2);
266 stringbuffer fullnumstr2 = plusmulti(new stringbuffer(str2),new stringbuffer(""+fullnum));
267 division.append(""+fullnum);
268 remain = plusminus(remain.tostring(),fullnumstr2.tostring());
269 }
270 else if(flag)//不够除，补0
271 division.append("0");
272 if(remain.tostring().equals("0"))
273 remain.setlength(0);
274 end++;
275 }
276 if(division.length() == 0){
277 return division.append('0');
278 }
279 return division;
280 }
281 /**
282 * 对外开放的减法
283 */
284 public mybiginteger divide(mybiginteger t){
285 if(t.data.tostring().equals("0"))
286 system.out.println("除零异常");
287 else{
288 if(isnonegative(this) && isnonegative(t))
289 data = plusdivide(data.tostring(),t.data.tostring());
290 else if(!isnonegative(this) && !isnonegative(t)){
291 data = plusdivide(data.substring(1),t.data.substring(1));
292 }
293 else{
294 stringbuffer temp;
295 if(!isnonegative(this) && isnonegative(t))
296 temp = plusdivide(data.substring(1),t.data.tostring());
297 else
298 temp = plusdivide(data.tostring(),t.data.substring(1));
299 if(temp.tostring().equals("0"))
300 data = temp;
301 else
302 data = temp.reverse().append('-').reverse();
303 }
304 }
305 return this;
306 }
307
308 /*
309 * 找出最大
310 */
311 private int greatst(stringbuffer str1,string str2){
312 for(int i = 1;i<10;i++){
313 stringbuffer num2 = new stringbuffer(str2);
314 for(int j =0;j<i;j++){//(i +1)倍
315 num2 = plusadd(num2.tostring(),str2);
316 }
317 if(!str1thanstr2(str1.tostring(),num2.tostring())){
318 return i;
319 }
320 }
321 return -1;
322 }
323 /**
324 * 判断str1、str2的大小
325 * 返回：str1>= str2 -----true
326 * str1< str2 -----false
327 */
328 private static boolean str1thanstr2(string str1,string str2){
329 boolean flag;//1 代表str1大些；2代表str2大些
330 //判断两个非负数，谁大。
331 if(str1.length() == str2.length()){
332 if(str1.compareto(str2)<0)
333 flag = false;
334 else
335 flag =true;
336 }
337 else{
338 if(str1.length() >str2.length())
339 flag = true;
340 else
341 flag = false;
342 }
343 return flag;
344 }
345
346
347 public static void main(string[] args) {
348 mybiginteger a1 = new mybiginteger("175");
349 mybiginteger a2 = new mybiginteger("231");
350 mybiginteger a3 = new mybiginteger("143");
351 mybiginteger a4 = new mybiginteger("-1978654");
352 mybiginteger b = new mybiginteger("-54");
353 mybiginteger b1 = new mybiginteger("0");
354 //175 + 231 - 143
355 system.out.println(a1.add(a2).minus(a3));
356 //(175 + 231 - 143)*(-1978654)
357 system.out.println(a1.multi(a4));
358 //(175 + 231 - 143)*(-1978654)/(-54)
359 system.out.println(a1.divide(b));
360 //0
361 system.out.println(a1.multi(b1));
362 }
363 }
上一篇： Java集合排序（面试必考点之一）
下一篇： 手把手教你写一个java的orm（完）