数据结构与算法:BigInt超大整数设计_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > 数据结构与算法:BigInt超大整数设计

数据结构与算法:BigInt超大整数设计

 2011/10/10 8:06:08  jsczxy2  http://jsczxy2.iteye.com  我要评论(0)
  • 摘要:中兴的一道笔试题:如果系统要使用超大整数(超过long长度范围),请你设计一个数据结构来存储这种超大型数字以及设计一种算法来实现超大整数加法运算)。packagecom.test;importorg.apache.commons.lang.StringUtils;/***@authorjsczxy2**/publicclassBigInt{publicstaticvoidmain(String[]args){BigInta=newBigInt
  • 标签:数据结构 数据 设计 算法

中兴的一道笔试题:如果系统要使用超大整数(超过long长度范围),请你设计一个数据结构来存储这种超大型数字以及设计一种算法来实现超大整数加法运算)。

?

package com.test;

import org.apache.commons.lang.StringUtils;

/**
 * @author jsczxy2
 * 
 */
public class BigInt {
	
	public static void main(String[] args) {
		BigInt a = new BigInt("367892732043217489143432876442367892732043217489143432876442367892732043217489143432876442367892732043217489143432876442");
		BigInt b = new BigInt("3678927329999999999999994328736789273299999999999999943287367892732043217489143432876442367892732043217489143432876442");
		System.out.println(a.toString());
		System.out.println(b.toString());
		System.out.println(a.add(b));
	}

	private int[] arrayint = new int[100];

	public BigInt(String num) {
		//分解数字到int数组中
		splitNumToArray(num);
	}

	public void splitNumToArray(String num) {
		int j = 0;
		StringBuffer sb = new StringBuffer();
		//数字全部翻转后分组截取后再翻转回来加入int数组,这里控制数组中每一个int元素恒定为8位不超过int最大长度
		num = new StringBuffer(num).reverse().toString();
		for (int i = 0; i <num.length(); i++) {
			if (i % 8 == 0) {
				if (sb != null && !sb.toString().equals("")){
					arrayint[j] = Integer.valueOf(sb.reverse().toString());
					j++;
					sb = new StringBuffer();
				}
			}
				sb.append(num.charAt(i));
			
		}
		if (sb != null) {
			arrayint[j] = Integer.valueOf(sb.reverse().toString());
		}
	}

	//数组从后开始打印数字,不满8位补齐8位数字用0进行左填充
	public String printArray(int[] array) {
		StringBuffer sb = new StringBuffer();
		boolean isNotFirstInt = false;
		for (int i = array.length-1; i >=0 ; i--) {
			if (array[i] != 0) {
				System.out.println(i+":"+array[i]);
				if(isNotFirstInt && String.valueOf(array[i]).length()<8){
					sb.append(StringUtils.leftPad(String.valueOf(array[i]), 8,"0"));
				}else{
					sb.append(array[i]);
					if(!isNotFirstInt)
						isNotFirstInt = true;
				}
				
			}
		}
		return sb.toString();
	}

	//BigInt数字进行加法运算
	public String add(BigInt bigInt) {
		int[] a = this.arrayint;
		int[] b = bigInt.arrayint;
		int[] result = new int[100];
		//根据各种情况进行结果赋值
		for(int i=0;i<a.length;i++){
			if(a[i]==0&&b[i]!=0){
				result[i]=b[i];
			}else if(a[i]!=0&&b[i]==0){
				result[i]=a[i];
			}else if(a[i]!=0&&b[i]!=0){
				result[i]=a[i]+b[i];
			}else{
				result[i]=0;
			}
		}
		//处理结果数组中超过8位的int元素的进位,该int元素截掉1位后再把其后一个元素值加一
		for(int i=0;i<result.length;i++){
			if(String.valueOf(result[i]).length()>8){
				result[i] = Integer.valueOf(String.valueOf(result[i]).substring(1));
				result[i+1] = result[i+1] + 1;
			}
		}
		return printArray(result);
	}

	//打印BigInt数字
	@Override
	public String toString() {
		return printArray(arrayint);
	}

}
上一篇: 搭积木 下一篇: Java基础之内部类
发表评论
用户名: 匿名