欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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 分别为被加数 、加数,则最终结果只可能是以下情况:

  1. num1  非负数    num2  非负数
  2. num1  负数        num2  负数            、
  3. num1  非负数    num2  负数              
  4. num1  负数        num2  非负数

上面四种情况可以转为:

  1. plusadd(num1,num2)
  2. - plusadd(- num1,- num2)  
  3. plusminus(num1,- num2)
  4. 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 }