【递归求解】大整数加法

问题描述:

整数大到超过所有的基本数据所能表示的数据范围时的加法运算.

 

算法思路:

递归的将大整数分割成二段,直至分割后的段可以用基本类型表示.

由低段到高段的顺序,合并各段.值得注意的是,这种顺序是不可颠倒的,因为高段需要用到低段的进位.也就是说,低段的进位要参入紧挨的下一段的加和运算.所以,add(mid+1,endIndex);在add(beginIndex,mid);语句前.

实现程序:

 

/**
 * Copyright (c) 2011 Trusted Software and Mobile Computing(TSMC)
 * All right reserved.
 *
 * Created on 2011
 *
 *		http://jarg.iteye.com/
 *
 */
// Contributors:  Jarg Yee <[e-mail]>
import java.util.*;
/*
 * 大整数加法
 * @author jarg
 * @version 1.0
 */
public class BigIntAdd
{
	/** 加数 */
	private static String x = "123456789012345678901234567890123456789012";
	/** 加数 */
	private static String y = "123456789012345678901234567890625";
	/** 边界,段最大长度 */
	private static final int wLen = String.valueOf(Long.MAX_VALUE).length()-1;
	/** 大整数加法结果 */
	private static String result = "";

	/** 
		补齐二加数.
		使得二加数长度一致,省去了很多不繁琐的边界检测.
	*/
	private static void init()
	{
		int maxLength = getMaxLength(x,y);	// 二加数最大长度
		int minLength = getMinLength(x,y);	// 二加数最小长度

		/* 补齐二加数 */
		for(int i=0;i<maxLength-minLength;i++)
		{
			if(x.length()==minLength)
				x = "0" + x;
			else
				y = "0" + y;
		}
	}

	/** for debugging. */
	public static void main(String[] args)
	{
		init();		/* 补齐加数,使二加数等长 */
		add(0,getMaxLength(x,y)-1);
		System.out.println("result:" + result);
	}

	/** 大整数加法 */
	private static int add(int beginIndex,int endIndex)
	{
		long value = 0;	// 加和值
		int carry = 0;	// 进位
		long weight = (long)Math.pow(10,endIndex-beginIndex+1);	// 权值

		if(endIndex-beginIndex+1<=wLen)
		{
			/* 单段加法 */
			value = Long.parseLong(x.substring(beginIndex,endIndex+1)) + Long.parseLong(y.substring(beginIndex,endIndex+1));
		}
		else
		{
			int mid = (beginIndex + endIndex)/2;	// 中间,从中间将大整数分割成二段
			
			/* 二个add的函数,有先后顺序,得先求出进位,然后加到高位上 */
			/* 进位 */
			carry = add(mid+1,endIndex);
			/* 合并结果,将结果与权值的余数保存到结果中 */
			value = carry + add(beginIndex,mid);
		}
		if(value%weight!=0)
			result = (value%weight) + result;	
		System.out.println("begin:" + beginIndex + "\tend:" + endIndex + "\tvalue:" + value + "\t进位:" + (int)(value/weight));

		/* 返回进位 */
		return (int)(value/weight);
	}

	/** 计算二字符串最大字符长度 */
	private static int getMaxLength(String strX,String strY)
	{
		return strX.length()>strY.length()?strX.length():strY.length();
	}

	/** 计算二字符串最小字符长度 */
	private static int getMinLength(String strX,String strY)
	{
		return strX.length()<=strY.length()?strX.length():strY.length();
	}
}