Code Kata:大整數比較大小&大整數四則運算---加減法 javascript實現

大整數的四則運算已經是老生常談的問題了。很多的庫也已經包含了各種各樣的解決方案。

作為練習，我們從最簡單的加減法開始。

加減法的核心思路是用倒序數組來模擬一個大數，然後將兩個大數的利用豎式進行運算。

加法函數：

• 異符號相加時調用減法函數（減法函數後面給出）
• 同符號相加先確定符號
• 因為輸入輸出的為字元串，需要去除字元串開頭的0

 1 function add(a, b) { /*輸入兩個字元串類型大數字*/
 2 
 3     if(a.indexOf('-') >= 0 && b.indexOf('-') < 0){
 4 
 5         return minus(b,a);
 6     }
 7     else if(a.indexOf('-') < 0 && b.indexOf('-') >= 0){
 8 
 9         return minus(a,b);
10     }
11 
12     var sign = "";
13 
14     if(a.indexOf('-') >= 0 && b.indexOf('-') >= 0){ /*兩個負數相加，指定符號*/
15 
16         sign = "-";
17 
18         a = a.substr(1);
19 
20         b = b.substr(1);
21     }
22 
23     var aArr = a.replace(/^0+/,'').split('').reverse();
24 
25     var bArr = b.replace(/^0+/,'').split('').reverse(); /*利用倒序數組存儲*/
26 
27     var carry = 0; /*進位值*/
28 
29     var sumArr = [];
30 
31     var len = Math.max(aArr.length, bArr.length); /*取得位數較大的一個數的位數*/
32 
33     for(var i=0;i<=len-1;i++){
34 
35         var digA = parseInt(aArr[i]) ? parseInt(aArr[i]) : 0;
36 
37         var digB = parseInt(bArr[i]) ? parseInt(bArr[i]) : 0;
38 
39         var digTotal = digA + digB + carry;
40 
41         if(i == len-1){/*排除'012' + '012'這樣的情況*/
42 
43             if(digTotal > 0){
44 
45                 sumArr.unshift(digTotal);
46             }
47 
48             break;
49         }
50 
51         carry = Number(digTotal >= 10);
52 
53         digTotal = digTotal % 10;
54 
55         sumArr.unshift(digTotal);
56 
57     }
58 
59     return sign + sumArr.join('');
60 }

在寫減法時，發現需要先比較大小，因此需要一個大數字比較大小的函數

比較小大函數：

• 異符號比較大小，正數大於負數
• 正數比較大小，先比較長度，長度大的數值大
• 正數長度一致，從最高位開始逐位比較，只到出現較大的一方，則數值更大
• 負數比較大小，方法同正數，結果取反即可
• 因為輸入輸出的為字元串，需要去除字元串開頭的0

 1 function compare(a,b){
 2 
 3     var sign = 1;
 4 
 5     if(a.indexOf('-') >= 0 && b.indexOf('-') < 0){ /*異符號比較*/
 6 
 7         return -1;
 8     }
 9     else if(a.indexOf('-') < 0 && b.indexOf('-') >= 0){ /*異符號比較*/
10 
11         return 1;
12     }
13     else if(a.indexOf('-') >= 0 && b.indexOf('-') >= 0){ /*同為負數，指定取反，同時改為正數比較方式*/
14 
15         sign = -1;
16 
17         a = a.substr(1);
18 
19         b = b.substr(1);
20     }
21 
22     a = a.replace(/^0+/,'');
23 
24     b = b.replace(/^0+/,'');
25 
26     var flag;
27 
28     if(a.length < b.length){    /*比較長度*/
29 
30         flag = -1;
31     }
32     else if(a.length > b.length){
33 
34         flag = 1;
35     }
36     else{
37 
38         flag = 0;
39     }
40 
41     if(flag == 0){ /*相同長度逐位比較*/
42 
43         var aArr = a.split('');
44 
45         var bArr = b.split('');
46 
47         for(var i=0;i<=aArr.length;i++){
48 
49             if(aArr[i] > bArr[i]){
50 
51                 flag = 1;
52 
53                 break;
54             }
55             else if(aArr[i] > bArr[i]){
56 
57                 flag = -1;
58 
59                 break;
60             }
61         }
62     }
63 
64     return sign * flag;
65 }

減法函數：

• 異符號相減時調用加法函數
• 同符號相減需要先確定大小
• 因為輸入輸出的為字元串，需要去除字元串開頭的0

 1 function minus(a, b) {
 2 
 3     if(a.indexOf('-') >= 0 && b.indexOf('-') < 0){
 4 
 5         return add(a,"-" + b);
 6     }
 7     else if(a.indexOf('-') < 0 && b.indexOf('-') >= 0){
 8 
 9         a = a.substr(1);
10 
11         return add(a,b);
12     }
13 
14     var sign = "";
15 
16     if(compare(a,b) < 0){
17 
18         var temp = b;
19 
20         b = a;
21 
22         a = temp;
23 
24         sign = "-";
25     }
26 
27     var aArr = a.replace(/^0+/,'').split('').reverse();
28 
29     var bArr = b.replace(/^0+/,'').split('').reverse(); /*利用倒序數組存儲*/
30 
31     var borrow = 0; /*借位值*/
32 
33     var minusArr = [];
34 
35     var len = Math.max(aArr.length, bArr.length); /*取得位數較大的一個數的位數*/
36 
37     for(var i=0;i<=len-1;i++){
38 
39         var digA = parseInt(aArr[i]) ? parseInt(aArr[i]) : 0;
40 
41         var digB = parseInt(bArr[i]) ? parseInt(bArr[i]) : 0;
42 
43         var digMinus;
44 
45         if(i == len-1){
46 
47             if(digA - borrow <= digB){ /*最高位不夠減直接跳出迴圈*/
48 
49                 break;
50             }
51         }
52 
53         if(digA - digB - borrow >= 0){
54 
55             digMinus = digA - digB - borrow;
56 
57         }else{
58 
59             digMinus = digA + 10 - digB - borrow;
60 
61             borrow = 1;
62         }
63 
64         minusArr.unshift(digMinus);
65 
66     }
67 
68     return sign + minusArr.join('');
69 }

以上給出的是帶符號大整數加減法基礎實現，但效率並不是特別高。

網上也有通過10000進位優化的豎式演算法，以及通過位運算實現四則運算的方法，大家也可以搜索看看，今天的練習就到這裡了，下周會給出乘除法的基本實現。

如果喜歡我的文章，可以掃描二維碼關註我的微信公眾號

爭取每天都分享一點我自己的開發和練習體驗～