大数相加

最近在找工作，有一些面试，有一些面试题，做点整理和回顾吧。

题目是：

有两个大数（Int32放不下的），要求他们的和

一接手我就考虑用字符串的模拟加法来做，然后就和面试官说了，可能当时时间有点赶，面试官没要求我写代码出来。

今天自己计时写了一下，这里给下代码：

public String computer(String one,String another) throws IllegalArgumentException{
	
	if(one == null || another == null 
			|| one.isEmpty() || another.isEmpty()){
		throw new IllegalArgumentException("input is empty");
	}
	int olength = one.length();
	int alength = another.length();
	int minlength = Math.min(olength,alength);
	int length = Math.max(olength,alength) + 1;
	
	byte[] out = new byte[length];
	
	char zero = '0';
	int o,a;
	int current = 0 ;
	boolean flag = false;
	int k = length - 1;
	for(int i = olength - 1,j = alength - 1; i >= 0 && j >= 0 ; i--,j--){
		o = one.charAt(i) - zero;
		a = another.charAt(j) - zero;
		if(o < 0 || o > 9 || a < 0 || a > 9){
			throw new IllegalArgumentException("input not a num(0~9),check your input");
		}
		current = o + a ;
		if(flag) {current ++;}
		if(current > 9){
			flag = true;
			current -= 10; 
		}else{
			flag = false;
		}
		out[k] = (byte)(zero + current);
		k--;
	}
	if(olength > minlength){
		flag = addLast(zero,one,flag,k,out);
	}else if(alength > minlength){
		flag = addLast(zero,another,out);
	}
	
	out[0] = '1';
	if(flag){
		return new String(out);
	}else{
		return new String(out).substring(1);
	}
}

private boolean addLast(char zero,String s,boolean flag,int k,byte[] out)throws IllegalArgumentException{
	int t;
	int current;
	for(int i = k - 1 ; i >= 0 ; i-- ){
		t = s.charAt(i) -zero;
		if(t < 0 || t > 9){
			throw new IllegalArgumentException("input not a num(0~9),check your input");
		}
		current = t;
		if(flag){current++;}
		
		if(current > 9){
			flag = true;
			current -= 10; 
		}else{
			flag = false;
		}
		out[k] = (byte)(zero + current);
		k--;
	}
	return flag;
}

简单测试用例：

System.out.println("-----test1------");
try{
	String a =  	  "789";
	String b ="90009999999";
	String c = computer(a,b);
	System.out.println(a);
	System.out.println(b);
	System.out.println(c);
}catch(IllegalArgumentException e){
	e.printStackTrace();
}

System.out.println("-----test2------");
try{
	String a = "1116666666666666666666622222188789";
	String b = "1";
	String c = computer(a,b);
	System.out.println(a);
	System.out.println(b);
	System.out.println(c);
}catch(IllegalArgumentException e){
	e.printStackTrace();
}

System.out.println("-----test3------");
try{
	String a =  "123456789";
	String b =	"809999999";
	String c = computer(a,b);
	System.out.println(a);
	System.out.println(b);
	System.out.println(c);
}catch(IllegalArgumentException e){
	e.printStackTrace();
}

System.out.println("-----test4------");
try{
	String a =  "999";
	String b =	"111";
	String c = computer(a,b);
	System.out.println(a);
	System.out.println(b);
	System.out.println(c);
}catch(IllegalArgumentException e){
	e.printStackTrace();
}

System.out.println("-----test5------");
try{
	String a =  "1234num56789";
	String b =	"809999999";
	String c = computer(a,b);
	System.out.println(a);
	System.out.println(b);
	System.out.println(c);
}catch(IllegalArgumentException e){
	e.printStackTrace();
}

回头看网上的代码，找到一个代码行数大概在35行的，他对string做了反转，再用了一个int[]的数字去存结果，最后才转化过去。

然后我就发现可以直接用一行代码实现：

new BigInteger(one).add(new BigInteger(another)).toString();

（实践中确实很少遇见这种要求，所以，真不知道有这个库函数-_-）

顺便看看一下openjdk中是怎么写的吧：

看了下代码行数，有三千多行，我只挑重点的看吧。

1、先把字符串按照正负、进制（2~36）存在一个符号位和数据位int[]中

2、如果符号位相同（加法）分段求和

    /**
     * Adds the contents of the int arrays x and y. This method allocates
     * a new int array to hold the answer and returns a reference to that
     * array.
     */
    private static int[] add(int[] x,int[] y) {
        // If x is shorter,swap the two arrays
        if (x.length < y.length) {
            int[] tmp = x;
            x = y;
            y = tmp;
        }

        int xIndex = x.length;
        int yIndex = y.length;
        int result[] = new int[xIndex];
        long sum = 0;

        // Add common parts of both numbers
        while(yIndex > 0) {
            sum = (x[--xIndex] & LONG_MASK) +
                  (y[--yIndex] & LONG_MASK) + (sum >>> 32);
            result[xIndex] = (int)sum;
        }

        // Copy remainder of longer number while carry propagation is required
        boolean carry = (sum >>> 32 != 0);
        while (xIndex > 0 && carry)
            carry = ((result[--xIndex] = x[xIndex] + 1) == 0);

        // Copy remainder of longer number
        while (xIndex > 0)
            result[--xIndex] = x[xIndex];

        // Grow result if necessary
        if (carry) {
            int bigger[] = new int[result.length + 1];
            System.arraycopy(result,bigger,1,result.length);
            bigger[0] = 0x01;
            return bigger;
        }
        return result;
    }

3、如果是减法

    /**
     * Subtracts the contents of the second int arrays (little) from the
     * first (big).  The first int array (big) must represent a larger number
     * than the second.  This method allocates the space necessary to hold the
     * answer.
     */
    private static int[] subtract(int[] big,int[] little) {
        int bigIndex = big.length;
        int result[] = new int[bigIndex];
        int littleIndex = little.length;
        long difference = 0;

        // Subtract common parts of both numbers
        while(littleIndex > 0) {
            difference = (big[--bigIndex] & LONG_MASK) -
                         (little[--littleIndex] & LONG_MASK) +
                         (difference >> 32);
            result[bigIndex] = (int)difference;
        }

        // Subtract remainder of longer number while borrow propagates
        boolean borrow = (difference >> 32 != 0);
        while (bigIndex > 0 && borrow)
            borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);

        // Copy remainder of longer number
        while (bigIndex > 0)
            result[--bigIndex] = big[bigIndex];

        return result;
    }

4、输出就默认转成十进制

小结一下：

我花的时间大概在一个小时，代码行数在70行上下，没反转，尽量不存数据，中间处理过程细节多了一点，面试的时候可能要注意的是：

0、漏了一种边界情况，输入的大数是负数

1、想清楚再动手写代码

2、不要太扣细节，保存简单 ?快速

最近找了一些leetcode的题在看，发现不少都是需要思考很久的。就和编程珠玑中那个”老家伙“一样，他遇到一些难题，和几个好友讨论了N论之后，出版成书，你不去看根本就不知道有这种解法（或者说是不能在几分钟内给解决方案）。

所以结论是，不是聪明到随时都能灵机一动，还是要刷算法题。

至少知道解决的可能性思路。