自己实现超大整数加法运算

问题

 

1.使用超大整数，请你设计一个数据结构来存储这个超大型数字以及设计一种算法来实现超大整数加法运算怎么作？

 

 

解答 ：
 * 如果现实中使用肯定使用BigInteger类，如果在JavaME等环境中可以考虑自己实现(但是一定考虑效率和Java中接口一致)
 * 自己实现可以用数组实现一个简单的
 * 如果仅仅加法就简单了。
 * 如果有乘法、除法、模除(RSA加密的基础)则较麻烦，一定要参考Java源代码，如果你的是商业代码，请勿参考OpenJDK，请参考harmony .

 

核心代码

 

package mymath;

import java.util.List;
import java.util.Vector;

/**
 * 整数模型版，未优化版本，和BigInteger不兼容.优化请详见java.math.BigInteger的实现
 * 
 * @author nisen
 * 
 */
public class MyBigInteger {
	List bytes = new Vector<Byte>();

	// 内部数据表示:列表高位表示数的高位, 如4455566 表示为{4,45,55,66}
	// 位数= bytes.size()*2
	public MyBigInteger(String val) {

		for (int i = val.length() - 1; i >= 0; i--) {
			int lowValue, heightValue;
			char lowChar = val.charAt(i);
			try {
				lowValue = Integer.parseInt("" + lowChar); // 个位
			} catch (NumberFormatException e) {
				throw new IllegalArgumentException("argument:" + val
						+ " must be number");
			}

			i--; // 十位
			if (i < 0) {
				heightValue = 0;
			} else {
				char highChar = val.charAt(i);
				try {
					heightValue = Integer.parseInt("" + highChar); // 十位
				} catch (NumberFormatException e) {
					throw new IllegalArgumentException("argument:" + val
							+ " must be number");
				}
			}

			bytes.add(0, new Byte((byte) (heightValue * 10 + lowValue)));
		}
	}

	private MyBigInteger(byte[] val) {
		for (int i = 0; i < val.length; i++) {
			bytes.add(new Byte(val[i]));
		}
	}

	private MyBigInteger() {
	}

	public String toString() {

		StringBuffer buf = new StringBuffer();
		for (int i = 0; i < bytes.size(); i++) {
			buf.append(bytes.get(i));
		}
		return buf.toString();

	}

	/**
	 * 生成一个新的MyBigInteger
	 * 
	 * @param val
	 * @return
	 */
	public MyBigInteger add(MyBigInteger val) {
		MyBigInteger result = new MyBigInteger();

		int maxlength = this.bytes.size() > val.bytes.size() ? this.bytes
				.size() : val.bytes.size(); // 最大位数

		boolean isCarry = false;// 是否进位

		for (int i = 0; i < maxlength; i++) {
			
			int valIndex = val.bytes.size() - i-1;
			int thisIndex = this.bytes.size() - i-1;
			
			
			Byte valByte = valIndex<0?0:(Byte) val.bytes.get(valIndex);			
			Byte thisByte =thisIndex<0?0:(Byte) this.bytes.get(thisIndex);
			
			
			int resultByte = valByte + thisByte + (isCarry ? 1 : 0);
			if (resultByte >= 100) { //是否有进位
				isCarry = true;
				resultByte = resultByte - 100;
			} else {
				isCarry = false;
			}

			result.bytes.add(0,(byte)resultByte);
		}
		return result;
	}
}

 

 

测试代码

public class MyBigIntegerTest {
	public static void main(String[] args) {
		MyBigInteger bi=new MyBigInteger("4455566");
		
		MyBigInteger val = new MyBigInteger("123");
		MyBigInteger result = bi.add(val).add(val);
		System.out.println("result="+result); //4455812
		System.out.println("bi="+bi); //4455566
		System.out.println("val="+val); //123
	}
}