期中考试题2：BigInteger的部分实现
Java中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两个文件夹。
如果提交作业格式错误，将不能通过测试，没有得分。
给出的代码是这样子的：
public class BigInteger {
// The sign of this integer - true for a positive number, and false
// otherwise
private boolean sign = true;
// digits[0] is the most significant digit of the integer, and
// the last element of this array is the least significant digit.
// For example, if we have a BigInteger of value 34, then
// digits[0] = 3 and digits[1] = 4.
private byte[] digits;
public BigInteger() {
this.digits = new byte[1];
this.digits[0] = 0;
}
public BigInteger(byte[] digits) {
this.digits = digits;
}
/**
* Initializes a <code>BigInteger</code> according to a string. The form of
* <code>numberStr</code> is a string consisting of all digits ranging from
* 0 to 9, following an OPTIONAL minus symbol (i.e., "-"). For example,
* "1234567891234567" and "-17788399934334388347734" are both valid.
*
* @param numberStr
* a number expressed as a string
*/
public BigInteger(String numberStr) {
// YOU FILL THIS IN
// Note: You should parse the string and initialize the "digits" array
// properly.
// You may also need to set the "sign" variable to a correct value.
}
/**
* Performs addition.
*
* @param another
* another <code>BigInteger</code> object
* @return this+another
*/
public BigInteger add(BigInteger another) {
// YOU FILL THIS IN
}
/**
* Performs addition.
*
* @param num
* an integer
* @return this+num
*/
public BigInteger add(int num) {
// YOU FILL THIS IN
}
/**
* Performs subtraction.
*
* @param another
* another <code>BigInteger</code> object
* @return this-another
*/
public BigInteger subtract(BigInteger another) {
// YOU FILL THIS IN
}
/**
* Performs subtraction.
*
* @param num
* an integer
* @return this-num
*/
public BigInteger subtract(int num) {
// YOU FILL THIS IN
}
/**
* Performs multiplication.
*
* @param another
* another <code>BigInteger</code> object
* @return this*another
*/
public BigInteger multiply(BigInteger another) {
// YOU FILL THIS IN
}
/**
* Performs multiplication.
*
* @param num
* an integer
* @return this*num
*/
public BigInteger multiply(int num) {
// YOU FILL THIS IN
}
public String toString() {
StringBuffer buf = new StringBuffer();
if (!sign) {
buf.append("-");
}
for (byte d : digits) {
buf.append(d);
}
return buf.toString();
}
public static void main(String[] args) {
BigInteger i1 = new BigInteger("999999999999999999");
BigInteger i2 = i1.add(1);
System.out.println(i2); // the output should be 1000000000000000000
BigInteger i3 = i2.multiply(i1);
System.out.println(i3); // expected: 999999999999999999000000000000000000
System.out.println(i3.subtract(-3)); // expected: 999999999999999999000000000000000003
}
}
其实，大家不要被这个看似很难的题目吓到，想想小学时我们刚开始学加法和乘法的时候，老师都教我们怎么算？竖式运算，对！由于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个小时，如果真的每个方法都写的话，估计很难做完。化归思想大家都学过，我们来运用一下：
public BigInteger(int integer){
this(String.valueOf(integer));
}
public BigInteger add(int num) {
return this.add(new BigInteger(num));
}
public BigInteger subtract(BigInteger another) {
return this.add(another.negate());
}
public BigInteger subtract(int num) {
return this.subtract(new BigInteger(num));
}
public BigInteger multiply(int num) {
return this.multiply(new BigInteger(num));
}
这里的negate方法是新加的，就是返回一个相反数。减法就是加上一个数的相反数，对吧？（注意，为了防止可能的副作用，这里使用了deep copy）
public BigInteger negate(){
BigInteger bi = new BigInteger();
byte[] digitsCopy = new byte[this.digits.length];
for(int i = 0;i < this.digits.length;i++){
digitsCopy[i] = this.digits[i];
}
bi.sign = !this.sign;
bi.digits = digitsCopy;
return bi;
}
于是，我们需要写的方法减少到了3个：
public BigInteger(String numberStr);
public BigInteger add(BigInteger another);
public BigInteger multiply(BigInteger another);
第一个方法不难，只要先判断第一个字符是不是'-'，然后再把不是负号的部分加到digits数组中就行。（由于明确了输入格式肯定是正确的，这里不考虑输入格式的问题）：
public BigInteger(String numberStr) {
// YOU FILL THIS IN
// Note: You should parse the string and initialize the "digits" array
// properly.
// You may also need to set the "sign" variable to a correct value.
if(numberStr.charAt(0) == '-'){
sign = false;
StringBuilder sb = new StringBuilder(numberStr);
sb.deleteCharAt(0);
numberStr = new String(sb);
}else{
sign = true;
}
digits = new byte[numberStr.length()];
for(int i = 0;i < numberStr.length();i++){
switch(numberStr.charAt(i)){
case '0': digits[i] = 0;break;
case '1': digits[i] = 1;break;
case '2': digits[i] = 2;break;
case '3': digits[i] = 3;break;
case '4': digits[i] = 4;break;
case '5': digits[i] = 5;break;
case '6': digits[i] = 6;break;
case '7': digits[i] = 7;break;
case '8': digits[i] = 8;break;
case '9': digits[i] = 9;break;
}
}
}
然后来看public BigInteger add(BigInteger another)方法，我们要考虑什么？首先是符号，如果两数同号，那好办，和肯定是和两数符号相同的；若异号，那么我们就要看两数绝对值的大小了，和与绝对值大的数同号。
怎样判断绝对值呢？首先看位数，位数大的绝对值肯定大。位数相同，则从首位开始比较，只要有一位不同，不同位置的数字大的大；如果每一位都相同，那么我们得到的就是0，省事很多。
然后我们考虑具体的加减，同号相加（其实是绝对值相加），要考虑进位问题，而产生的和的位数最多比绝对值大的数多一位；异号相加，其实是绝对值相减，要考虑借位问题，而得到的差位数不大于绝对值大的数。
这里要特别注意的是，竖式计算的是从最末尾开始的，而我们的数组首位存储的是最高位，第二位是第二高位，一次类推；故我们这里用的循环大多同平日写的循环有些不同：for(int i = 1;i <= digits.length;i++)。
梳理好以上思路，add方法写法如下：
public BigInteger add(BigInteger another) {
// YOU FILL THIS IN
BigInteger sum = new BigInteger();
if(this.sign == another.sign){
//the signs of both are equal
int length1 = this.digits.length;
int length2 = another.digits.length;
int biggerLength = Math.max(length1, length2);
byte[] temp = new byte[biggerLength];
byte carry = 0;
for(int i = 1;i <= biggerLength;i++){
byte i1 = (length1 - i < 0)?0:this.digits[length1 - i];
byte i2 = (length2 - i < 0)?0:another.digits[length2 -i];
int s = i1 + i2 + carry;
if(s < 10){
temp[biggerLength - i] = (byte)s;
carry = 0;
}else{
temp[biggerLength - i] = (byte)(s - 10);
carry = 1;
}
}
if(carry == 0){
sum.digits = temp;
}else{
sum.digits = new byte[biggerLength + 1];
sum.digits[0] = carry;
for(int i = 0;i < biggerLength;i++){
sum.digits[i + 1] = temp[i];
}
}
sum.sign = this.sign;
}else{
//the signs differ
boolean isAbsoluteEqual = false;//the default value is false
boolean isThisAbsoluteBigger = false;// the default value is false
if(this.digits.length > another.digits.length){
isThisAbsoluteBigger = true;
}else if(this.digits.length == another.digits.length){
isAbsoluteEqual = true;
for(int i = 0;i < this.digits.length;i++){
if(this.digits[i] != another.digits[i]){
if(this.digits[i] > another.digits[i]){
isThisAbsoluteBigger = true;
}
isAbsoluteEqual = false;
break;
}
}
}
//if isAbsoluteEqual is true, the sum should be 0, which is just the default value
if(!isAbsoluteEqual){
byte[] temp;
byte[] bigger;
byte[] smaller;
if(isThisAbsoluteBigger){
sum.sign = this.sign;
temp = new byte[this.digits.length];
bigger = this.digits;
smaller = another.digits;
}else{
sum.sign = another.sign;
temp = new byte[another.digits.length];
bigger = another.digits;
smaller = this.digits;
}
boolean borrow = false;
for(int index = 1;index <= bigger.length;index++){
byte biggerDigit = bigger[bigger.length - index];
biggerDigit = (byte) ((borrow)?(biggerDigit - 1):biggerDigit);
byte smallerDigit = (smaller.length - index < 0)?0:smaller[smaller.length - index];
int s = biggerDigit - smallerDigit;
if(s < 0){
borrow = true;
s += 10;
}else{
borrow = false;
}
temp[temp.length - index] = (byte)s;
}
int zeroCount = 0;
for(int i = 0;i < temp.length;i++){
if(temp[i] == 0){
zeroCount++;
}else{
break;
}
}
sum.digits = new byte[temp.length - zeroCount];
for(int i = 0;i < sum.digits.length;i++){
sum.digits[i] = temp[zeroCount + i];
}
}
}
return sum;
}
最后就是乘法了，其实还是竖式计算，就是稍微麻烦了一点（暂时还没找到更好的解法，3个小时，咱就不考虑什么算法优化了）。第一还是先考虑符号，这个比加法简单，要是同号，商为正，要是异号，那么商为负。
第二是具体的竖式计算怎么做，先看一个例子：
1 2 3 4
x 9 3 4
----------------
4 9 3 6
3 7 0 2
+ 1 1 1 0 6
----------------
1 1 5 2 5 5 6
规律是什么？1. 大数在上，小数在下； 2. 大数乘以小数的每一位，分别得到商； 3.最后把各个商按位相加。 听上去挺简单，不是吗？实现1，和加法里面的循环类似，从低位开始相乘，还要考虑进位。2中的商我们可以保存在一个二维数组中，数组第一维的大小是较小数的位数，第二维是较大数的位数+1，为什么有个+1？看看上面的第三个商，最多有可能比大数多一位。 而3呢？位数的便宜似乎比较难实现，但是想想我们上次做过的WordPuzzle，如果是个矩阵呢？其实上面的几个商，按照矩阵排列就是：
0 4 9 3 6 0 3 7 0 2 1 1 1 0 6
对应的加法是沿着主对角线方向的！有点感觉了是吧，而这个矩阵就是我们刚刚做的那个二维数组！
乘法实现如下：
public BigInteger multiply(BigInteger another) {
// YOU FILL THIS IN
BigInteger product = new BigInteger();
if(this.sign == another.sign){
product.sign = true;
}else{
product.sign = false;
}
int biggerLength;
int smallerLength;
byte[] bigger;
byte[] smaller;
byte[][] tempProducts;
if(this.digits.length >= another.digits.length){
biggerLength = this.digits.length;
smallerLength = another.digits.length;
bigger = this.digits;
smaller = another.digits;
}else{
biggerLength = another.digits.length;
smallerLength = this.digits.length;
bigger = another.digits;
smaller = this.digits;
}
tempProducts = new byte[smallerLength][];
for(int i = 1;i <= smallerLength;i++){
byte[] temp = new byte[biggerLength + 1];//make plenty of space to avoid overflow
byte carry = 0;
byte m1 = smaller[smallerLength - i];
for(int j = 1;j <= biggerLength;j++){
byte m2 = bigger[biggerLength - j];
int tempProduct = m1 * m2 + carry;
temp[biggerLength + 1 - j] = (byte)(tempProduct % 10);
carry = (byte)(tempProduct / 10);
}
temp[0] = carry;
tempProducts[i - 1] = temp;
}
byte[] sum = new byte[smallerLength + biggerLength];
byte carry = 0;
int count = 1;
int row = 0;
int column = biggerLength;
while(count <= sum.length){
int startR = row;
int startC = column;
int currentSum = 0;
while((startR < smallerLength) && (startC < biggerLength + 1)){
currentSum += tempProducts[startR][startC];
startR++;
startC++;
}
currentSum += carry;
if(currentSum < 10){
sum[sum.length - count] = (byte)(currentSum);
carry = 0;
}else{
sum[sum.length - count] = (byte)(currentSum % 10);
carry = (byte)(currentSum / 10);
}
//System.out.println("processing digit: " + (sum.length - count) + " current digit: " + sum[sum.length - count] + " current carry: " + carry);
if(column == 0){
row++;
}else{
column--;
}
count++;
}
int zeroCount = 0;
for(int i = 0;i < sum.length;i++){
if(sum[i] == 0){
zeroCount++;
}else{
break;
}
}
product.digits = new byte[sum.length - zeroCount];
for(int i = 0;i < product.digits.length;i++){
product.digits[i] = sum[zeroCount + i];
}
return product;
}
以上几个方法中的zeroCount和接下来跟着的循环是用来去掉数组前几位不必要的0而设计的。
用java.math包内自带的BigInteger测试了几个相同的实例：
public static void main(String[] args) {
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"));
System.out.println(bi);
BigInteger bi2 = new BigInteger("123456789").multiply(new BigInteger("-999999999").multiply(new BigInteger("2387423749237")));
System.out.println(bi2);
System.out.println(bi.subtract(bi2));
System.out.println(bi.add(bi2));
}
得到的结果：（没两行上面的是java.math包内的BigInteger的结果，下面是我写的BigInteger的结果）
-1703513391044005504226057865745939441413078537590685258276720 -1703513391044005504226057865745939441413078537590685258276720 -294743669768397549929858780007 -294743669768397549929858780007 -1703513391044005504226057865745644697743310140040755399496713 -1703513391044005504226057865745644697743310140040755399496713 -1703513391044005504226057865746234185082846935140615117056727 -1703513391044005504226057865746234185082846935140615117056727
评论 (0)