【非递归求解】大整数加法

  

问题描述:

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

 

算法思路:

将大整数分割成可以用基本类型表现的几段,然后采用分治的思想,由低段到高段的顺序,将各段相加.

低位的进位参入紧挨的下一段求和.

 

/**
 * 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.*;
/*
 * TODO 大整数加法
 */
public class BigIntAdd
{
	private static final String x = "12345678901234567";		// 加数x
	private static final String y = "12345678901234567890625";	// 加数y
	//12345691246913469125192
	private static final int wlen = weightExp();				// 权值长度
	private static final long weight = (long)Math.pow(10,wlen);	// 权值
	
	
	/* @TODO for debugging. */
	public static void main(String[] args)
	{
		add(x,y);	// 大整数x,y相加
	}

	/* @TODO 求权值指数,int型最大数长度-1 */
	private static int weightExp()
	{
		/* 可表示的段长 */
		int length = (""+Long.MAX_VALUE).length() - 1;
		return length;
	}

	/* TODO 大整数分割成可表示的几段 */
	private static List<Long> numberDivide(String value)
	{
		/* 用以存储分割后的各段 */
		List<Long> list = new ArrayList<Long>();

		/* 计算分割段数 */
		int size = value.length()/wlen;
		/* 若不能整除,说明还有数据,得在size基础上加1 */
		if(value.length()%wlen != 0)
		{
			size = size + 1;
		}

		int beginIndex;	// 记录读取数据的位置

		/* 以wlen长度为单位,从低位向高位读取数据 */
		for(int i=0; i<size; i++)
		{
			beginIndex = value.length()-wlen*(i+1);
			/* 开始的位置若小于0,则从0开始读 */
			if(beginIndex<0)
				beginIndex = 0;
			String str = value.substring(beginIndex,value.length()-wlen*i);
			
			list.add(Long.parseLong(str));	// 分割的数据存入list
		}

		//display(list);		// 输出各段值
		return list;
	}

	/* TODO 输出显示分割后的大整数各段 */
	private static void display(List<Long> list)
	{
		/* 高段到低段顺序 */
		for(int i=list.size()-1; i>=0; i--)
		{
			System.out.println("value" + i + "=" + list.get(i));
		}
		System.out.println("------------------");
	}

	/* TODO 大整数各段相加 */
	private static void add(String x,String y)
	{
		/* 大整数x,y分割后的存储容器 */
		List<Long> listX = numberDivide(x);
		List<Long> listY = numberDivide(y);
		
		/* 
			二加数分割后的段数不一定相等
			段数多的为准
		 */
		int size = listX.size()>listY.size()?listX.size():listY.size();

		long tempNum = 0;	// 用于计算进位
		long sum = 0;		// 保存各段加法结果
		String result = "";	// 大整数加法结果

		/* 先计算低段,后高段 */
		for(int i=0; i<size; i++)
		{
			long a = 0,b = 0;	// 段值
			if(listX.size()-1>=i)
			{
				a = listX.get(i);
			}

			if(listY.size()-1>=i)
			{
				b = listY.get(i);
			}

			/* 除了加上当前段值外,还要加上上一段进位 */
			sum = tempNum + a + b;
			tempNum = sum/weight; // 当前段进位

			/* result在加号后面,之前算出的result是低段 */
			result = sum%weight + result;	
			//System.out.println(a + "\t" + b + "\t" + tempNum + "\t" + weight);
		}

		/* 最后还得判断一次最高段是否有进位 */
		if(tempNum != 0)
		{
			result = tempNum + result;
		}

		System.out.println("result:" + result);
	}
}