java.math.BigInteger類

ava中long類型可以表示 -9,223,372,036,854,775,808（即-2^64）到9,223,372,036,854,775,807（即2^64-1）範圍内的整數。有的時候我們希望能夠處理在此範圍之外的整數。

為此，我們設計了一個BigInteger類。它可以支援大整數的加、減、乘操作。請根據提供的代碼架構，完成整個程式。

> 注：

> 1) 請仔細閱讀代碼中的注釋，并在标有// YOU FILL THIS IN 的位置添加你的代碼。你可以添加自己的方法、變量，但是請不要修改已有的代碼。

> 2) 程式中的main函數隻是一個示例測試。在批改作業時，我們會用更多的用例來測試你的程式。是以請保證你的程式的正确性。

> 3) 我們在測試你的程式時，将使用合法的輸入值，是以你無需考慮輸入不合法的情況。輸入值可能有兩種形式："343839939" 或者

  "-394939399390343"，輸入的數字位數不固定，但一定是合法的整數。

> 4)  不允許使用java.math包。

> 5) 請将你的項目打包成rar或者zip格式送出。請注意送出的格式：打開你的壓縮包，應該可以看到BigInteger檔案夾，這個檔案夾裡面包含了src和bin兩個檔案夾。

  如果送出作業格式錯誤，将不能通過測試，沒有得分。

給出的代碼是這樣子的：

Java代碼  

1. public class BigInteger {   
2.     // The sign of this integer - true for a positive number, and false   
3.     // otherwise   
4.     private boolean sign = true;   
5.     // digits[0] is the most significant digit of the integer, and   
6.     // the last element of this array is the least significant digit.   
7.     // For example, if we have a BigInteger of value 34, then   
8.     // digits[0] = 3 and digits[1] = 4.   
9.     private byte[] digits;   
10.     public BigInteger() {   
11.         this.digits = new byte[1];   
12.         this.digits[0] = 0;   
13.     }   
14.     public BigInteger(byte[] digits) {   
15.         this.digits = digits;   
16.     }   
17.     public BigInteger(String numberStr) {   
18.         // YOU FILL THIS IN   
19.         // Note: You should parse the string and initialize the "digits" array   
20.         // properly.   
21.         // You may also need to set the "sign" variable to a correct value.   
22.     }   
23.     public BigInteger add(BigInteger another) {   
24.         // YOU FILL THIS IN   
25.     }   
26.     public BigInteger add(int num) {   
27.         // YOU FILL THIS IN   
28.     }   
29.     public BigInteger subtract(BigInteger another) {   
30.         // YOU FILL THIS IN   
31.     }   
32.     public BigInteger subtract(int num) {   
33.         // YOU FILL THIS IN   
34.     }   
35.     public BigInteger multiply(BigInteger another) {   
36.         // YOU FILL THIS IN   
37.     }   
38.     public BigInteger multiply(int num) {   
39.         // YOU FILL THIS IN   
40.     }   
41.     public String toString() {   
42.         StringBuffer buf = new StringBuffer();   
43.         if (!sign) {   
44.             buf.append("-");   
45.         }   
46.         for (byte d : digits) {   
47.             buf.append(d);   
48.         }   
49.         return buf.toString();   
50.     }   
51.     public static void main(String[] args) {   
52.         BigInteger i1 = new BigInteger("999999999999999999");   
53.         BigInteger i2 = i1.add(1);   
54.         System.out.println(i2); // the output should be 1000000000000000000   
55.         BigInteger i3 = i2.multiply(i1);   
56.         System.out.println(i3); // expected: 999999999999999999000000000000000000   
57.         System.out.println(i3.subtract(-3)); // expected: 999999999999999999000000000000000003   
58.     }   
59. }  

其實，大家不要被這個看似很難的題目吓到，想想國小時我們剛開始學加法和乘法的時候，老師都教我們怎麼算？豎式運算，對！由于BigInteger把每一位數都存在數組中，也為豎式運算提供了友善。

我們需要寫的方法是：

public BigInteger(String numberStr);

public BigInteger add(BigInteger another);

public BigInteger add(int num);

public BigInteger subtract(BigInteger another);

public BigInteger subtract(int num);

public BigInteger multiply(BigInteger another);

public BigInteger multiply(int num);

3個小時，如果真的每個方法都寫的話，估計很難做完。化歸思想大家都學過，我們來運用一下：

Java代碼  

1. public BigInteger(int integer){   
2.     this(String.valueOf(integer));   
3. }   
4.     public BigInteger add(int num) {   
5.     return this.add(new BigInteger(num));   
6. }   
7. public BigInteger subtract(BigInteger another) {   
8.     return this.add(another.negate());   
9. }   
10. public BigInteger subtract(int num) {   
11.     return this.subtract(new BigInteger(num));   
12. }   
13. public BigInteger multiply(int num) {   
14.     return this.multiply(new BigInteger(num));   
15. }  

這裡的negate方法是新加的，就是傳回一個相反數。減法就是加上一個數的相反數，對吧？（注意，為了防止可能的副作用，這裡使用了deep copy）

Java代碼  

1. public BigInteger negate(){   
2.     BigInteger bi = new BigInteger();   
3.     byte[] digitsCopy = new byte[this.digits.length];   
4.     for(int i = 0;i < this.digits.length;i++){   
5.         digitsCopy[i] = this.digits[i];   
6.     }   
7.     bi.sign = !this.sign;   
8.     bi.digits = digitsCopy;   
9.     return bi;   
10. }  

于是，我們需要寫的方法減少到了3個：

public BigInteger(String numberStr);

public BigInteger add(BigInteger another);

public BigInteger multiply(BigInteger another);

第一個方法不難，隻要先判斷第一個字元是不是'-'，然後再把不是負号的部分加到digits數組中就行。（由于明确了輸入格式肯定是正确的，這裡不考慮輸入格式的問題）：

Java代碼  

1. public BigInteger(String numberStr) {   
2.     // YOU FILL THIS IN   
3.     // Note: You should parse the string and initialize the "digits" array   
4.     // properly.   
5.     // You may also need to set the "sign" variable to a correct value.   
6.     if(numberStr.charAt(0) == '-'){   
7.         sign = false;   
8.         StringBuilder sb = new StringBuilder(numberStr);   
9.         sb.deleteCharAt(0);   
10.         numberStr = new String(sb);   
11.     }else{   
12.         sign = true;   
13.     }   
14.     digits = new byte[numberStr.length()];   
15.     for(int i = 0;i < numberStr.length();i++){   
16.         switch(numberStr.charAt(i)){   
17.         case '0': digits[i] = 0;break;   
18.         case '1': digits[i] = 1;break;   
19.         case '2': digits[i] = 2;break;   
20.         case '3': digits[i] = 3;break;   
21.         case '4': digits[i] = 4;break;   
22.         case '5': digits[i] = 5;break;   
23.         case '6': digits[i] = 6;break;   
24.         case '7': digits[i] = 7;break;   
25.         case '8': digits[i] = 8;break;   
26.         case '9': digits[i] = 9;break;   
27.         }   
28.     }   
29. }  

然後來看public BigInteger add(BigInteger another)方法，我們要考慮什麼？首先是符号，如果兩數同号，那好辦，和肯定是和兩數符号相同的；若異号，那麼我們就要看兩數絕對值的大小了，和與絕對值大的數同号。

怎樣判斷絕對值呢？首先看位數，位數大的絕對值肯定大。位數相同，則從首位開始比較，隻要有一位不同，不同位置的數字大的大；如果每一位都相同，那麼我們得到的就是0，省事很多。

然後我們考慮具體的加減，同号相加（其實是絕對值相加），要考慮進位問題，而産生的和的位數最多比絕對值大的數多一位；異号相加，其實是絕對值相減，要考慮借位問題，而得到的差位數不大于絕對值大的數。

這裡要特别注意的是，豎式計算的是從最末尾開始的，而我們的數組首位存儲的是最高位，第二位是第二高位，一次類推；故我們這裡用的循環大多同平日寫的循環有些不同：for(int i = 1;i <= digits.length;i++)。

梳理好以上思路，add方法寫法如下：

Java代碼  

1. public BigInteger add(BigInteger another) {   
2.     // YOU FILL THIS IN   
3.     BigInteger sum = new BigInteger();   
4.     if(this.sign == another.sign){   
5.         //the signs of both are equal   
6.         int length1 = this.digits.length;   
7.         int length2 = another.digits.length;   
8.         int biggerLength = Math.max(length1, length2);   
9.         byte[] temp = new byte[biggerLength];   
10.         byte carry = 0;   
11.         for(int i = 1;i <= biggerLength;i++){   
12.             byte i1 = (length1 - i < 0)?0:this.digits[length1 - i];   
13.             byte i2 = (length2 - i < 0)?0:another.digits[length2 -i];   
14.             int s = i1 + i2 + carry;   
15.             if(s < 10){   
16.                 temp[biggerLength - i] = (byte)s;   
17.                 carry = 0;   
18.             }else{   
19.                 temp[biggerLength - i] = (byte)(s - 10);   
20.                 carry = 1;   
21.             }   
22.         }   
23.         if(carry == 0){   
24.             sum.digits = temp;   
25.         }else{   
26.             sum.digits = new byte[biggerLength + 1];   
27.             sum.digits[0] = carry;   
28.             for(int i = 0;i < biggerLength;i++){   
29.                 sum.digits[i + 1] = temp[i];   
30.             }   
31.         }   
32.         sum.sign = this.sign;   
33.     }else{   
34.         //the signs differ   
35.         boolean isAbsoluteEqual = false;//the default value is false   
36.         boolean isThisAbsoluteBigger = false;// the default value is false   
37.         if(this.digits.length > another.digits.length){   
38.             isThisAbsoluteBigger = true;   
39.         }else if(this.digits.length == another.digits.length){   
40.             isAbsoluteEqual = true;   
41.             for(int i = 0;i < this.digits.length;i++){   
42.                 if(this.digits[i] != another.digits[i]){   
43.                     if(this.digits[i] > another.digits[i]){   
44.                         isThisAbsoluteBigger = true;   
45.                     }   
46.                     isAbsoluteEqual = false;   
47.                     break;   
48.                 }   
49.             }   
50.         }   
51.         //if isAbsoluteEqual is true, the sum should be 0, which is just the default value   
52.         if(!isAbsoluteEqual){   
53.             byte[] temp;   
54.             byte[] bigger;   
55.             byte[] smaller;   
56.             if(isThisAbsoluteBigger){   
57.                 sum.sign = this.sign;   
58.                 temp = new byte[this.digits.length];   
59.                 bigger = this.digits;   
60.                 smaller = another.digits;   
61.             }else{   
62.                 sum.sign = another.sign;   
63.                 temp = new byte[another.digits.length];   
64.                 bigger = another.digits;   
65.                 smaller = this.digits;   
66.             }   
67.             boolean borrow = false;   
68.             for(int index = 1;index <= bigger.length;index++){   
69.                 byte biggerDigit = bigger[bigger.length - index];   
70.                 biggerDigit = (byte) ((borrow)?(biggerDigit - 1):biggerDigit);   
71.                 byte smallerDigit = (smaller.length - index < 0)?0:smaller[smaller.length - index];   
72.                 int s = biggerDigit - smallerDigit;   
73.                 if(s < 0){   
74.                     borrow = true;   
75.                     s += 10;   
76.                 }else{   
77.                     borrow = false;   
78.                 }   
79.                 temp[temp.length - index] = (byte)s;   
80.             }   
81.             int zeroCount = 0;   
82.             for(int i = 0;i < temp.length;i++){   
83.                 if(temp[i] == 0){   
84.                     zeroCount++;   
85.                 }else{   
86.                     break;   
87.                 }   
88.             }   
89.             sum.digits = new byte[temp.length - zeroCount];   
90.             for(int i = 0;i < sum.digits.length;i++){   
91.                 sum.digits[i] = temp[zeroCount + i];   
92.             }   
93.         }   
94.     }   
95.     return sum;   
96. }  

最後就是乘法了，其實還是豎式計算，就是稍微麻煩了一點（暫時還沒找到更好的解法，3個小時，咱就不考慮什麼算法優化了）。第一還是先考慮符号，這個比加法簡單，要是同号，商為正，要是異号，那麼商為負。

第二是具體的豎式計算怎麼做，先看一個例子：

Java代碼  

1.         1 2 3 4  
2.        x  9 3 4  
3. ----------------   
4.         4 9 3 6  
5.       3 7 0 2  
6. + 1 1 1 0 6  
7. ----------------   
8.   1 1 5 2 5 5 6  

規律是什麼？1. 大數在上，小數在下； 2. 大數乘以小數的每一位，分别得到商； 3.最後把各個商按位相加。 聽上去挺簡單，不是嗎？實作1，和加法裡面的循環類似，從低位開始相乘，還要考慮進位。2中的商我們可以儲存在一個二維數組中，數組第一維的大小是較小數的位數，第二維是較大數的位數+1，為什麼有個+1？看看上面的第三個商，最多有可能比大數多一位。 而3呢？位數的便宜似乎比較難實作，但是想想我們上次做過的WordPuzzle，如果是個矩陣呢？其實上面的幾個商，按照矩陣排列就是：

Java代碼  

1. 0 4 9 3 6  
2. 0 3 7 0 2  
3. 1 1 1 0 6  

對應的加法是沿着主對角線方向的！有點感覺了是吧，而這個矩陣就是我們剛剛做的那個二維數組！

乘法實作如下：

Java代碼  

1. public BigInteger multiply(BigInteger another) {   
2.     // YOU FILL THIS IN   
3.     BigInteger product = new BigInteger();   
4.     if(this.sign == another.sign){   
5.         product.sign = true;   
6.     }else{   
7.         product.sign = false;   
8.     }   
9.     int biggerLength;   
10.     int smallerLength;   
11.     byte[] bigger;   
12.     byte[] smaller;   
13.     byte[][] tempProducts;   
14.     if(this.digits.length >= another.digits.length){   
15.         biggerLength = this.digits.length;   
16.         smallerLength = another.digits.length;   
17.         bigger = this.digits;   
18.         smaller = another.digits;   
19.     }else{   
20.         biggerLength = another.digits.length;   
21.         smallerLength = this.digits.length;   
22.         bigger = another.digits;   
23.         smaller = this.digits;   
24.     }   
25.     tempProducts = new byte[smallerLength][];   
26.     for(int i = 1;i <= smallerLength;i++){   
27.         byte[] temp = new byte[biggerLength + 1];//make plenty of space to avoid overflow   
28.         byte carry = 0;   
29.         byte m1 = smaller[smallerLength - i];   
30.         for(int j = 1;j <= biggerLength;j++){   
31.             byte m2 = bigger[biggerLength - j];   
32.             int tempProduct = m1 * m2 + carry;   
33.             temp[biggerLength + 1 - j] = (byte)(tempProduct % 10);   
34.             carry = (byte)(tempProduct / 10);   
35.         }   
36.         temp[0] = carry;   
37.         tempProducts[i - 1] = temp;   
38.     }   
39.     byte[] sum = new byte[smallerLength + biggerLength];   
40.     byte carry = 0;   
41.     int count = 1;   
42.     int row = 0;   
43.     int column = biggerLength;   
44.     while(count <= sum.length){   
45.         int startR = row;   
46.         int startC = column;   
47.         int currentSum = 0;   
48.         while((startR < smallerLength) && (startC < biggerLength + 1)){   
49.             currentSum += tempProducts[startR][startC];   
50.             startR++;   
51.             startC++;   
52.         }   
53.         currentSum += carry;   
54.         if(currentSum < 10){   
55.             sum[sum.length - count] = (byte)(currentSum);   
56.             carry = 0;   
57.         }else{   
58.             sum[sum.length - count] = (byte)(currentSum % 10);   
59.             carry = (byte)(currentSum / 10);   
60.         }   
61.         //System.out.println("processing digit: " + (sum.length - count) + " current digit: " + sum[sum.length - count] + " current carry: " + carry);   
62.         if(column == 0){   
63.             row++;   
64.         }else{   
65.             column--;   
66.         }   
67.         count++;   
68.     }   
69.     int zeroCount = 0;   
70.     for(int i = 0;i < sum.length;i++){   
71.         if(sum[i] == 0){   
72.             zeroCount++;   
73.         }else{   
74.             break;   
75.         }   
76.     }   
77.     product.digits = new byte[sum.length - zeroCount];   
78.     for(int i = 0;i < product.digits.length;i++){   
79.         product.digits[i] = sum[zeroCount + i];   
80.     }   
81.     return product;   
82. }  

以上幾個方法中的zeroCount和接下來跟着的循環是用來去掉數組前幾位不必要的0而設計的。

用java.math包内自帶的BigInteger測試了幾個相同的執行個體：

Java代碼  

1. public static void main(String[] args) {   
2.     BigInteger bi = new BigInteger("-123456789").multiply(new BigInteger("1111111111")).multiply(new BigInteger("-222222222")).multiply(new BigInteger("333333333")).multiply(new BigInteger("-444444444")).multiply(new BigInteger("555555555")).multiply(new BigInteger("678987654"));   
3.     System.out.println(bi);   
4.     BigInteger bi2 = new BigInteger("123456789").multiply(new BigInteger("-999999999").multiply(new BigInteger("2387423749237")));   
5.     System.out.println(bi2);   
6.     System.out.println(bi.subtract(bi2));   
7.     System.out.println(bi.add(bi2));   
8. }  

得到的結果：（沒兩行上面的是java.math包内的BigInteger的結果，下面是我寫的BigInteger的結果）

Java代碼  

1. -1703513391044005504226057865745939441413078537590685258276720  
2. -1703513391044005504226057865745939441413078537590685258276720  
3. -294743669768397549929858780007  
4. -294743669768397549929858780007  
5. -1703513391044005504226057865745644697743310140040755399496713  
6. -1703513391044005504226057865745644697743310140040755399496713  
7. -1703513391044005504226057865746234185082846935140615117056727  
8. -1703513391044005504226057865746234185082846935140615117056727