java大数加法

上次屁颠屁颠的跑了1k多公里去ucweb面试，本来自我感觉还不错的，可是还是很郁闷得就给打回来了……
其中有个笔试题是求两个大数（比如100位）的和，我当时知道怎么做，思路也没问题，但是在纸上划的时候估计有些细节没处理好，比如判断输入等。回来后自己重新做了一遍，把它贴出来共享，奉献给即将面试的兄弟伙，有什么问题请拍砖。

/**
 * @author zhangyong
 * 
 */
public class BigInt {

/**
	 * @param args
	 */
	public static void main(String[] args) {
		BigInt b = new BigInt();
		b.add("999", "999");
	}

public String add(String a, String b) {
		//检查输入
		if (!a.matches("\\d+") || !a.matches("\\d+")) {
			return null;
		}
		final int BASE = 10;//10进制
		int lenA = a.length();//加数的长度
		int lenB = b.length();//被加数的长度
		int maxLen, partialSum, carry = 0;//大数的长度，和，进位
		maxLen = (lenA > lenB) ? lenA : lenB;
		StringBuffer sum = new StringBuffer();
		int temA, temB = 0;
		for (int i = 0; i < maxLen; i++) {
			if (i >= lenA) {
				temA = 0;
			} else {
				temA = Integer.valueOf(a.charAt(lenA - i - 1) - 48);
			}
			if (i >= lenB) {
				temB = 0;
			} else {
				temB = Integer.valueOf(b.charAt(lenB - i - 1) - 48);
			}
			partialSum = temA + temB + carry;
			carry = partialSum / BASE;
			sum.append(partialSum % BASE);
		}
		if (carry == 1)
			sum.append(carry);
		System.out.println(a + "+" + b + "=" + sum.reverse().toString());
		return sum.reverse().toString();
	}
}

网络上还有另外一个版本：

package test;

public class VeryBigNumAdd {

public static void main(String[] args) {
		VeryBigNumAdd vbn = new VeryBigNumAdd();
		String a = "123453243455535634535252345234677576252241234123523453664563634";
		String b = "123453243455535634535252345234677576252241234123523453664563634";
		String result = vbn.doAdd(a, b);
		System.out.println("result:" + result);
	}

String doAdd(String a, String b) {
		String str = "";
		int lenA = a.length();
		int lenB = b.length();
		int maxLen = (lenA > lenB) ? lenA : lenB;
		int minLen = (lenA < lenB) ? lenA : lenB;
		String strTmp = "";
		for (int i = maxLen - minLen; i > 0; i--) {
			strTmp += "0";
		}
		// 把长度调整到相同
		if (maxLen == lenA) {
			b = strTmp + b;
		} else
			a = strTmp + a;
		int JW = 0;// 进位
		for (int i = maxLen - 1; i >= 0; i--) {
			int tempA = Integer.parseInt(String.valueOf(a.charAt(i)));
			int tempB = Integer.parseInt(String.valueOf(b.charAt(i)));
			int temp;
			if (tempA + tempB + JW >= 10 && i != 0) {
				temp = tempA + tempB + JW - 10;
				JW = 1;
			} else {
				temp = tempA + tempB + JW;
				JW = 0;
			}
			str = String.valueOf(temp) + str;
		}
		return str;
	}
}

这又是一个版本：

import java.util.ArrayList;
import java.util.Collections;

public class VeryLongInt {

ArrayList digits;

// Postcondition: The VeryLongInt is empty.
	public VeryLongInt() {
		final int INITIAL_CAPACITY = 500;
		digits = new ArrayList(INITIAL_CAPACITY);
	} // default constructor

// Precondition: n >= 0.
	// Postcondition: The VeryLongInt has been initialized from the
	// not-very-long int n.
	public VeryLongInt(int n) {
		final int BASE = 10;
		digits = new ArrayList();
		do {
			digits.add(new Integer(n % BASE));
			n = n / BASE;
		} // while
		while (n > 0);
		// digits is now in reverse order, so we reverse:
		Collections.reverse(digits);

} // constructor

// Postcondition: The number of elements in the VeryLongInt has
	// been returned.
	public int size() {
		return digits.size();
	} // method size

// Precondition: The string s consists of a sequence of characters
	// with non-digit characters ignored.
	// There are no leading zeroes, except for 0
	// itself, which has a single '0'.
	// Postcondition: The VeryLongInt has been initialized from s.
	public VeryLongInt(String s) {
		final char LOWEST_DIGIT_CHAR = '0';
		final char HIGHEST_DIGIT_CHAR = '9';
		digits = new ArrayList(s.length());
		char c;
		int digit;
		for (int i = 0; i < s.length(); i++) {
			c = s.charAt(i);
			if ((LOWEST_DIGIT_CHAR <= c) && (c <= HIGHEST_DIGIT_CHAR)) {

digit = c - LOWEST_DIGIT_CHAR;
				digits.add(new Integer(digit));
			} // if a digit
		} // for
	} // constructor with string parameter

// Postcondition: The VeryLongInt has been returned as a string of digits.
	public String toString() {
		final String EMPTY_STRING = "";
		String s = EMPTY_STRING;
		for (int i = 0; i < digits.size(); i++)
			s += digits.get(i);
		return s;

} // method toString

// Postcondition: If i >= digits.size(), 0 has been returned; else
	// the ith least significant digit in digits has
	// been returned. The least significant digit is
	// the 0th least significant digit.
	private int least(int i) {
		if (i >= digits.size())
			return 0;
		else
			return ((Integer) (digits.get(digits.size() - i - 1))).intValue();
	} // least

// Postcondition: The VeryLongInt has been incremented by otherVeryLong.
	public void add(VeryLongInt otherVeryLong) {
		final int BASE = 10;
		int largerSize, partialSum, carry = 0;
		VeryLongInt sum = new VeryLongInt();
		if (digits.size() > otherVeryLong.digits.size())
			largerSize = digits.size();
		else
			largerSize = otherVeryLong.digits.size();

for (int i = 0; i < largerSize; i++) {

partialSum = least(i) + otherVeryLong.least(i) + carry;
			carry = partialSum / BASE;
			sum.digits.add(new Integer(partialSum % BASE));

} // for

if (carry == 1)
			sum.digits.add(new Integer(carry));
		Collections.reverse(sum.digits);
		digits = sum.digits;
	} // method add

// Postcondition: A copy of the calling object has been returned.
	public Object clone() {
		VeryLongInt temp = new VeryLongInt();
		temp.digits = (ArrayList) digits.clone();
		return temp;
	} // method clone

// Postcondition: true has been returned if the
	// value of the VeryLongInt is less than the value
	// of otherVeryLong. Otherwise, false
	// has been returned.
	public boolean less(VeryLongInt otherVeryLong) {

if (digits.size() < otherVeryLong.digits.size())
			return true;
		if (digits.size() > otherVeryLong.digits.size())
			return false;
		for (int i = 0; i < digits.size(); i++) {
			if (((Integer) (digits.get(i))).intValue() < ((Integer) (otherVeryLong.digits
					.get(i))).intValue())
				return true;
			if (((Integer) (digits.get(i))).intValue() > ((Integer) (otherVeryLong.digits
					.get(i))).intValue())
				return false;
		} // for
		return false; // the two objects have the same value
	} // method less

// Postcondition: true has been returned if the value of the VeryLongInt
	// is greater than the value of otherVeryLong. Otherwise,
	// false has been returned.
	public boolean greater(VeryLongInt otherVeryLong) {
		return otherVeryLong.less(this);
	} // method greater

// Postcondition: true has been returned if the value of the VeryLongInt
	// is equal to the value of otherVeryLong. Otherwise,
	// false has been returned.
	public boolean equals(VeryLongInt otherVeryLong) {
		return !less(otherVeryLong) && !otherVeryLong.less(this);
	} // method equals

// Precondition: n > 0.
	// Postcondition: The calling object contains the nth Fibonacci
	// number.
	public void fibonacci(int n) {
		VeryLongInt previous = new VeryLongInt(1), current = new VeryLongInt(1), temp = new VeryLongInt();
		digits.clear();
		if (n <= 2)
			digits.add(new Integer(1));
		else {
			for (int i = 3; i <= n; i++) {
				temp = (VeryLongInt) current.clone();
				current.add(previous);
				previous = temp;
			} // for
			digits = current.digits;
		} // else

} // method fibonacci

} // class VeryLongInt

By：残梦追月

posted on 2009-03-10 12:58 残梦追月阅读(5551) 评论(20) 编辑收藏

常用链接

留言簿(6)

随笔分类(48)

随笔档案(42)

文章分类(6)

文章档案(4)

收藏夹

友情链接

搜索

积分与排名

最新随笔

最新评论

阅读排行榜

评论排行榜


只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻知识库 C++博客博问管理