bignumber.java

一个数据结构来存储超大型数字以及一种算法来实现超大整数加法运算。

package properties;

import java.util.Scanner;

public class BigNumber {
	// 如果系统要使用超大整数（超过long长度范围），
	// 请你设计一个数据结构来存储这种超大型数字以及设计一种算法来实现超大整数加法运算。

	private int[] numberBody;
	
	private void setNumberBody(int[] numberBody) {
		this.numberBody = numberBody;
	}
	
	private int[] getNumberBody() {
		return numberBody;
	}

	public BigNumber(String bigNum) {
		saveNum(bigNum);
	}
	
	public BigNumber(BigNumber bn) {
		//setNumberBody(bn.numberBody);
		this.numberBody = bn.numberBody;
	}

	private void saveNum(String bigNum) {
		int len = bigNum.length();
		int bit = len / 9;
		int mod = len % 9;
		if (mod != 0) {
			numberBody = new int[bit + 2];
		} else {
			numberBody = new int[bit + 1];
		}
		numberBody[0] = len;
		int arrayLen = numberBody[0];
		for (int i = 1; i < numberBody.length; i++) {
			int prostion = i - 1;
			int endSite = arrayLen - prostion * 9;
			int startSite = arrayLen - (prostion + 1) * 9;
			if (startSite < 0) {
				startSite = 0;
			}
			numberBody[i] = Integer.parseInt(bigNum.substring(startSite, endSite));
		}
	}

	private String showNum() {
		StringBuilder result = new StringBuilder();
		int len = numberBody.length;
		if (numberBody[len - 1] == 0) {
			len = len - 1;
		}
		for (int i = len; i > 1; i--) {
			String num = String.valueOf(numberBody[i - 1]);
			if (i < len && num.length() < 9) {
				int zeroCount = 0;
				zeroCount = 9 - num.length();
				for (int j = 0; j < zeroCount; j++) {
					result.append("0");
				}
			}
			result.append(num);
		}
		return result.toString();
	}

	private void addNum(BigNumber bn02) {
		int[] num02 = bn02.getNumberBody();
		int[] result;
		int loopCount = numberBody.length, resultSize = num02.length;
		boolean isEquals = false;
		if (loopCount > num02.length) {
			loopCount = num02.length;
			resultSize = numberBody.length;
		} else if (loopCount == resultSize) {
			isEquals = true;
		}
		result = new int[resultSize + 1];
		result[0] = resultSize;
		int carry = 0;
		for (int i = 1; i < loopCount; i++) {
			// carry
			String addResult = String.valueOf(numberBody[i] + num02[i] + carry);
			carry = 0;
			int resultLen = addResult.length();
			if (resultLen > 9) {
				carry = Integer.parseInt(addResult.substring(0, 1));
				result[i] = Integer.parseInt(addResult.substring(1, resultLen));
			} else {
				result[i] = Integer.parseInt(addResult.substring(0, resultLen));
			}
		}
		//如果相加的两个数字位数不等
		if (!isEquals) {
			int[] bigArray;
			if (resultSize == numberBody.length) {
				bigArray = numberBody;
			} else {
				bigArray = num02;
			}
			for (int i = loopCount; i < resultSize; i++) {
				String addResult = String.valueOf(bigArray[i] + carry);
				carry = 0;
				int resultLen = addResult.length();
				if (resultLen > 9) {
					carry = Integer.parseInt(addResult.substring(9, 10));
				}
				result[i] = Integer.parseInt(addResult.substring(0, resultLen));
			}
		}
		//数组最后一位保存最高位的进位
		if (carry != 0) {
			result[resultSize] = carry;
			carry = 0;
		}
		setNumberBody(result);
	}	
	
	public static void main(String args[]) {
		Scanner s = new Scanner(System.in);
		String bigNum01 = s.nextLine();
		String bigNum02 = s.nextLine();
		BigNumber bn01 = new BigNumber(bigNum01);
		BigNumber bn02 = new BigNumber(bigNum02);
		bn01.addNum(bn02);
		System.out.print(bn01.showNum());
	}
}