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