`
nisen
  • 浏览: 77754 次
  • 性别: Icon_minigender_1
  • 来自: 河北 石家庄
社区版块
存档分类
最新评论

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

阅读更多

问题

 

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
	}
}
 

 

 

 

分享到:
评论

相关推荐

    C++堆栈实现超长整数加法

    总结来说,通过堆栈实现超长整数加法的关键在于利用堆栈的特性进行逐位操作,并处理好进位的问题。这种实现方式简洁且高效,适用于各种需要处理大整数的场景。理解并掌握这一方法,对于提升C++编程能力和算法设计...

    任意长的整数进行加法运算

    利用双向循环链表实现长整数的存储,每个结点含一个整形变量。任何整形变量的范围是 -(2^15 - 1)~ (2^15 - 1)。输入和输出形式:按中国对于长整数的表示习惯,每四位一组,组间用逗号隔开。 这是我用java写的,使用...

    数据结构(大整数加法)

    当我们处理大整数加法时,由于普通整数类型在计算机内存中的限制,不能直接存储和运算超大的数值,这就需要利用特定的数据结构和算法来解决。本主题主要探讨如何使用数据结构来实现大整数的加法操作。 首先,我们...

    vc6.0实现大整数加法

    在本文中,我们将深入探讨如何使用Microsoft Visual C++ 6.0(简称VC6.0)集成开发环境,结合MFC(Microsoft Foundation Classes)库来实现大整数加法的功能。MFC是微软提供的一套面向对象的C++类库,它极大地简化了...

    可以实现实现长整数的加法运算

    ,基本要求:利用双向循环链表实现长整数的存储,每个结点含一个整形变量。任何整形变量的范围是 -(2^15 - 1)~(2^15 - 1)。输入和输出形式:按中国对于长整数的表示习惯,每四位一组,组间用逗号隔开。

    任意长整数加法课程设计

    在本次课程设计中,主要目标是使用C++编程语言实现一个能够处理任意长度整数加法的程序。设计者王博文在指导教师黄道昌的指导下,选择了数据结构中的双向循环链表作为主要的数据结构来解决这个问题。这个设计不仅...

    双向链表任意长整数加法.c

    任意长的整数加法 问题描述:设计一个程序实现两个...基本要求:利用双向循环链表,设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组,组间用逗号隔开。如:1,0000,0000,0000,0000。

    C/C++:任意长的整数加法.rar(含完整注释)

    问题描述:设计一个程序实现两个任意长的整数的求和运算。...基本要求:利用双向循环链表,设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组,组间用逗号隔开。如:1,0000,0000,0000,0000.

    mfc 实现加法运算

    在本文中,我们将深入探讨如何使用Microsoft Foundation Class (MFC) 库来实现一个简单的加法运算程序,并展示如何在Windows应用程序中运用模态对话框。MFC 是微软为C++开发者提供的一套面向对象的类库,它使得构建...

    数据结构-任意长整数加法.doc

    当需要进行长整数加法运算时,简单的加法运算符难以达到要求,或者当两个较大整数相加的值超过了整型变量所能储存的数值时,程序将发生溢出。因此,需要一种新的加法模式来解决上述问题,来实现任意长的整数进行加法...

    大整数加法C语言程序

    本项目提供了一个使用C语言实现大整数加法的简单程序,它能够处理两个200位的整数进行加法运算,这对于初学者来说是一个很好的实践案例。 首先,我们来理解大整数的概念。在标准的C语言中,int类型通常只能表示32位...

    易语言加法运算源码.zip

    通过这个加法运算的源码示例,你可以学习到易语言的基本语法结构,理解加法运算在程序中的实现方式,以及如何编写和调试简单的程序。这将为你后续学习更复杂的易语言程序打下基础。在学习过程中,不仅要关注代码的...

    任意长的整数加法.cpp

    长整数加法的总体目标:在VC6.0的开发环境下,利用...(1)设计一个实现任意长的整数加法运算演示程序。 (2)利用双向链表实现长整数的存储,每个结点含一个整型变量。 (3)输入输出形式,每四位一组,用逗号隔开。

    大整数加法 c++

    能够实现超出int类型表示的大整数的加法运算

    任意长整数加法

    3. ** 加法运算:** 使用`add()`方法进行加法运算。例如,`BigInteger a = new BigInteger("123456"); BigInteger b = new BigInteger("789012"); BigInteger sum = a.add(b);` 这将计算123456和789012的和。 4. **...

    计算机加法运算原理计算机加法运算原理

    浮点数在计算机内部是以特定格式存储的,包括指数和尾数部分,其加法运算比整数加法更为复杂,需要考虑对齐、规格化和溢出等问题。 总之,计算机加法运算原理是计算机科学的基石,它贯穿于从底层硬件到高层软件的每...

    c语言编写程序实现两个超长正整数(每个最长80位数字)的减法运算

    编写程序实现两个超长正整数(每个最长80位数字)的减法运算。 [输入形式] 从键盘读入两个整数,要考虑输入高位可能为0的情况(如00083)。 1.第一行是超长正整数A; 2.第二行是超长正整数B; [输出形式] 输出只有一行,是...

    易语言位运算实现加法运算

    在实现加法运算时,我们可能需要先将参与运算的数字转换成符号整数,以便正确处理正负数的情况。在二进制表示中,最高位(符号位)为1表示负数,为0则表示正数。 加法运算在位运算是通过逐位相加并处理进位来完成的...

Global site tag (gtag.js) - Google Analytics