6272人阅读
数据结构之算法面试题（5）
在不使用BigInteger这个类的情况下，如何自己去实现两个超级大的数相加呢？
首先我们来看一下加法的原则: 1.同号相加，把两数相加，结果符号位取任意一个数的符号
2.异号相加，取较大的数减去较小的数，结果符号位取较大的数的符号位
由于是超级大数，我们使用String来存储。首先要判断这两个大数的符号位，以及正确性（不能是0开头的数，也不能含有其它字母和符号）
* 大整数求和
* @param num1
* @param num2
public static String bigNumberSum(String num1, String num2) {
// 最后的符号
char sign = '+';
char sign1 = num1.charAt(0);
char sign2 = num2.charAt(0);
String number1 = "";
String number2 = "";
// 去符号位操作
if (sign1 == '-' || sign1 == '+') {
number1 = num1.substring(1);
sign1 = '+';
number1 = num1;
// 去符号位操作
if (sign2 == '-' || sign2 == '+') {
number2 = num2.substring(1);
sign2 = '+';
number2 = num2;
boolean isDig1 = number1.matches("[1-9][0-9]*");
boolean isDig2 = number2.matches("[1-9][0-9]*");
if (!isDig1 || !isDig2) {
throw new NumberFormatException("输入的数据不是正确的整数");
return "";
}首先要知道的是两个数相加，结果的最大长度是两数最长的长度+1。所以我们用一个int[len]数组来存储各位相加的结果。
int length1 = number1.length();
int length2 = number2.length();
// 两数相加结果最长为求最长的数的长度+1
int len = length1 & length2 ? length1 + 1 : length2 + 1;
int[] result = new int[len];为了从个位开始，我们需要对字符进行反转
char[] chars1 = new StringBuffer(number1).reverse().toString().toCharArray();
char[] chars2 = new StringBuffer(number2).reverse().toString().toCharArray();
接着开始讨论一些情况，首先是同号相加。如果两个数的长度不一致，应该先以长度最短的数开始遍历相加，接着就是最长的数组剩下的那部分的值，因为超出部分不用相加。同号相加时会有进位的情况，最后一步 便是处理进位了。比如说99+2，2比99的长度短，所以以2的长度为临界点。result[0] = 2+9=11; 2已经遍历完了，所有剩下就是直接取值于99中剩下的位数。result[1] = 9; reuslt[0] = 11&=10所以result[0] = 11%10=1; 将进位提交到下一位result[0+1]
= result[0+1] +1;以此类推，result[1] = 0, result[2] = 1；所以最终结果为101,符号为正，不做处理。boolean longerIs1 = length1 & length2 ? true :
// 同号则直接相加
if (sign1 == sign2) {
sign = sign1;
if (longerIs1) {
for (int i = 0; i & length2; i++) {
result[i] = (chars1[i] - '0') + (chars2[i] - '0');
for (int j = length2; j & length1; j++) {
result[j] = (chars1[j] - '0');
for (int i = 0; i & length1; i++) {
result[i] = (chars1[i] - '0') + (chars2[i] - '0');
for (int j = length1; j & length2; j++) {
result[j] = (chars2[j] - '0');
// 处理进位
for (int i = 0; i & i++) {
if (result[i] &= 10) {
result[i + 1] += result[i] / 10;
result[i] = result[i] % 10;
}接着来讨论一个整数一个负数相加的情况。长度不等，拿长的数减去短的数，便于处理借位的情况。如果长度相等，这拿较大的数减去较小的。比如说。通过String的compareTo方法比较，获取哪个数较大。当然啦，这里是相减，所以会出现借位的情况。所有最后要对借位进行处理。
else {// 异号相加,如果length1&length2,拿长的数减去小的数
if (longerIs1) {
sign = sign1;
for (int i = 0; i & length2; i++) {
result[i] = (chars1[i] - '0') - (chars2[i] - '0');
for (int j = length2; j & length1; j++) {
result[j] = chars1[j] - '0';
if (length1 == length2) {
// 拿大的数减去小的数
boolean lager = number1.compareTo(number2)&0 ? true :
if (lager) {
sign = sign1;
for (int i = 0; i & length1; i++) {
result[i] = (chars1[i] - '0') - (chars2[i] - '0');
sign = sign2;
for (int i = 0; i & length1; i++) {
result[i] = (chars2[i] - '0') - (chars1[i] - '0');
} else {// length1&length2
sign = sign2;
for (int i = 0; i & length1; i++) {
result[i] = (chars2[i] - '0') - (chars1[i] - '0');
for (int j = length1; j & length2; j++) {
result[j] = chars2[j] - '0';
// 处理借位
for (int i = 0; i & i++) {
if (result[i] & 0) {
result[i] += 10;
result[i + 1]--;
剩下的就是处理结果result数组了。因为长度是len&length1和length2,所以会有最高位是0的情况。比如说88+2=90，但是result的长度是3,所以result得到的结果是090，这不是我们想要的，应该把0去掉。
// 结果没有进位时的0处理
boolean flag =
StringBuffer resultStr = new StringBuffer();
for (int i = result.length - 1; i &= 0; i--) {
if (result[i] == 0 && flag) {
resultStr.append(result[i]);
// 符号处理
if (sign == '-') {
return "-" + resultStr.toString();
return resultStr.toString();
完整代码如下
* 大整数求和
* @param num1
* @param num2
public static String bigNumberSum(String num1, String num2) {
// 最后的符号
char sign = '+';
char sign1 = num1.charAt(0);
char sign2 = num2.charAt(0);
String number1 = "";
String number2 = "";
// 去符号位操作
if (sign1 == '-' || sign1 == '+') {
number1 = num1.substring(1);
sign1 = '+';
number1 = num1;
// 去符号位操作
if (sign2 == '-' || sign2 == '+') {
number2 = num2.substring(1);
sign2 = '+';
number2 = num2;
boolean isDig1 = number1.matches("[1-9][0-9]*");
boolean isDig2 = number2.matches("[1-9][0-9]*");
if (!isDig1 || !isDig2) {
throw new NumberFormatException("输入的数据不是正确的格式的整数");
char[] chars1 = new StringBuffer(number1).reverse().toString().toCharArray();
char[] chars2 = new StringBuffer(number2).reverse().toString().toCharArray();
int length1 = number1.length();
int length2 = number2.length();
// 两数相加结果最长为求最长的数的长度+1
int len = length1 & length2 ? length1 + 1 : length2 + 1;
int[] result = new int[len];
boolean longerIs1 = length1 & length2 ? true :
// 同号则直接相加
if (sign1 == sign2) {
sign = sign1;
if (longerIs1) {
for (int i = 0; i & length2; i++) {
result[i] = (chars1[i] - '0') + (chars2[i] - '0');
for (int j = length2; j & length1; j++) {
result[j] = (chars1[j] - '0');
for (int i = 0; i & length1; i++) {
result[i] = (chars1[i] - '0') + (chars2[i] - '0');
for (int j = length1; j & length2; j++) {
result[j] = (chars2[j] - '0');
// 处理进位
for (int i = 0; i & i++) {
if (result[i] &= 10) {
result[i + 1] += result[i] / 10;
result[i] = result[i] % 10;
} else {// 异号相加,如果length1&length2,拿长的数减去小的数
if (longerIs1) {
sign = sign1;
for (int i = 0; i & length2; i++) {
result[i] = (chars1[i] - '0') - (chars2[i] - '0');
for (int j = length2; j & length1; j++) {
result[j] = chars1[j] - '0';
if (length1 == length2) {
// 拿大的数减去小的数
boolean lager = number1.compareTo(number2)&0 ? true :
if (lager) {
sign = sign1;
for (int i = 0; i & length1; i++) {
result[i] = (chars1[i] - '0') - (chars2[i] - '0');
sign = sign2;
for (int i = 0; i & length1; i++) {
result[i] = (chars2[i] - '0') - (chars1[i] - '0');
} else {// length1&length2
sign = sign2;
for (int i = 0; i & length1; i++) {
result[i] = (chars2[i] - '0') - (chars1[i] - '0');
for (int j = length1; j & length2; j++) {
result[j] = chars2[j] - '0';
// 处理借位
for (int i = 0; i & i++) {
if (result[i] & 0) {
result[i] += 10;
result[i + 1]--;
// 结果没有进位时的0处理
boolean flag =
StringBuffer resultStr = new StringBuffer();
for (int i = result.length - 1; i &= 0; i--) {
if (result[i] == 0 && flag) {
resultStr.append(result[i]);
// 符号处理
if (sign == '-') {
return "-" + resultStr.toString();
return resultStr.toString();
在我写完上面的代码时，回头去看瞬间懵比了。那么多的if else，要看好久才能看懂这些逻辑啊。要是面试官看到这些代码，估计机会都不给了。所以打算改进一下逻辑，让整体的代码结构更加清晰易懂。从头分析一遍，我们的思路，我们可以发现同号异号这两种情况是必然要判断的，我们的代码主要用在了什么方面呢。我猜你应该发现了吧，大量的代码用来处理两个数的长度不一致的情况了。我们可以看到当它们的长度相等的时候，只需要执行一个for循环即可。
if (length1 == length2) {
&span style="white-space:pre"& &/span&// 拿大的数减去小的数
boolean lager = number1.compareTo(number2)&0 ? true :
if (lager) {
sign = sign1;
for (int i = 0; i & length1; i++) {
&span style="white-space:pre"& &/span&result[i] = (chars1[i] - '0') - (chars2[i] - '0');
sign = sign2;
for (int i = 0; i & length1; i++) {
&span style="white-space:pre"& &/span&result[i] = (chars2[i] - '0') - (chars1[i] - '0');
加入相加的两个数"一开始"就是长度相等的，那么我们也不许要搞那么多的事情了，逻辑会更加清晰。所以一开始我们应该先对两个数进行预处理，让它们的长度一致。即往短的数前面补0，不存在的位置补上0。你百位上没有数字，没关系，我给你个0，然后我们再相加或者相减。改进的代码如下：
* 求超大整数的和
* @param num1
* @param num2
public static String bigNumberSumBetter(String num1, String num2) {
char sign = '+';
char sign1 = num1.charAt(0);
char sign2 = num2.charAt(0);
String number1 = "";
String number2 = "";
// 去符号位操作
if (sign1 == '-' || sign1 == '+') {
number1 = num1.substring(1);
sign1 = '+';
number1 = num1;
// 去符号位操作
if (sign2 == '-' || sign2 == '+') {
number2 = num2.substring(1);
sign2 = '+';
number2 = num2;
boolean isDig1 = number1.matches("[1-9][0-9]*");
boolean isDig2 = number2.matches("[1-9][0-9]*");
if (!isDig1 || !isDig2) {
throw new NumberFormatException("输入的数据不是正确的格式的整数");
//两个数的长度
int length1 = number1.length();
int length2 = number2.length();
int len = length1&=length2? length1+1:length2+1;
StringBuffer number1Buffer = new StringBuffer();
StringBuffer number2Buffer = new StringBuffer();
//扩展数据的长度,使它们的长度一样
if(length1&length2){
for(int i=0; i&length1-length2; i++){
number2Buffer.append("0");
}else if(length1&length2){
for(int i=0; i&length2-length1; i++){
number1Buffer.append("0");
number1Buffer.append(number1);
number2Buffer.append(number2);
char[] chars1 = number1Buffer.reverse().toString().toCharArray();
char[] chars2 = number2Buffer.reverse().toString().toCharArray();
//存储每位相加的结果
int[] result = new int[len];
//同号相加
if(sign1==sign2){
sign = sign1;
for(int i=0; i&len-1; i++){
result[i] = (chars1[i]-'0')+(chars2[i]-'0');
// 处理进位
for (int i = 0; i & i++) {
if (result[i] &= 10) {
result[i + 1] += result[i] / 10;
result[i] = result[i] % 10;
// 拿大的数减去小的数
boolean lager = number1.compareTo(number2)&0 ? true :
if (lager) {
sign = sign1;
for (int i = 0; i & len-1; i++) {
result[i] = (chars1[i] - '0') - (chars2[i] - '0');
sign = sign2;
for (int i = 0; i & len-1; i++) {
result[i] = (chars2[i] - '0') - (chars1[i] - '0');
// 处理借位
for (int i = 0; i & i++) {
if (result[i] & 0) {
result[i] += 10;
result[i + 1]--;
// 结果没有进位时的0处理
boolean flag =
StringBuffer resultStr = new StringBuffer();
for (int i = result.length - 1; i &= 0; i--) {
if (result[i] == 0 && flag) {
resultStr.append(result[i]);
// 符号处理
if (sign == '-') {
return "-" + resultStr.toString();
return resultStr.toString();
}代码结构更清晰了，也更容易让人读懂。package interview_10_10;
import org.junit.T
public class T1 {
* 如果系统要使用超大整数（超过long长度范围），请你设计一个数据结构来存储这种超大型数字以及设计一种算法来实现超大整数加法运算）。
public void test1() {
String number1 = "9";
String number2 = "4325898";
String result = doAdd(number1, number2);
System.out.println(result);
* @param num1
* @param num2
* 1.计算小的那个左边需要补几个0
* 2.从右边开始一个个的开始相加
public static String doAdd(String num1, String num2) {
String str = "";
int lena = num1.length();
int lenb = num2.length();
int maxlength = lena & lenb ? lena :
int minlength = lena & lenb ? lena :
String strtemp = "";
for (int i = (maxlength - minlength); i & 0; i--) { // 计算左边需要补几个0
strtemp += 0;
if (maxlength == lena) { // 左边补零
num2 = strtemp + num2;
num1 = strtemp + num1;
int jw = 0;
for (int i = (maxlength - 1); i &= 0; i--) {
int temp = 0;
int number1 = Integer.valueOf(String.valueOf(num1.charAt(i)));
int number2 = Integer.valueOf(String.valueOf(num2.charAt(i)));
if (number1 + number2 + jw & 10 && i != 0) {
temp = number1 + number2 + jw - 10;
temp = number1 + number2 +
str = String.valueOf(temp) +
阅读(...) 评论()HugeInteger
说明：&&创建一个大整数类HugeInteger，该类用一个40个元素的数组来存放一个大整数（最多不超过40位）。（1）定义几个大整数算术运算的成员函数，包括inputHugeInteger、outputHugeInteger、addHugeIntegers和substractHugeIntegers(Create a large integer class HugeInteger, with such an array of 40 elements to store a large integer (up to no more than 40). (1) define a few large integer arithmetic member functions, including inputHugeInteger, outputHugeInteger, addHugeIntegers and substractHugeIntegers)
文件列表：
HugeInteger
HugeInteger\HugeInteger.java
HugeInteger\test.java
近期下载者：
相关文件：java 如何创建一个类或方法能够给出指定位数的一个随机“大数”？_百度知道
java 如何创建一个类或方法能够给出指定位数的一个随机“大数”？
java 如何创建一个类或方法能够给出指定位数的一个随机“大数”？例如 bignumb（100000）可以给出一个100000位的数字，注意是100000位。可否结合BigInteger 和 Random？最好有具体代码，谢谢！
我有更好的答案
一个大数一般都是使用数组存储的。比如使用byte[]，一个byte可以表示0-99,或者使用字符串存储大数.那么，class&BigInteger&{&&public&byte[]&x;&&public&String&y;&&public&BigInteger&bignumbX(int&len)&{&&&&if(len&=0)&return&&&&&BigInteger&r&=&new&BigInteger();&&&&r.x&=&new&byte[(len+1)/2];&//&得到需要多少个byte表示大数&&&&int&i&=&0;&Random&rnd&=&new&Random();&&&&while(len&2)&{&&&&&&r.x[i++]&=&rnd.nextInt(100);&len-=2;&&&&}&&&&if(len==1)&r.x[i]&=&rnd.nextInt(9)+1;&//1-9,&最高位不为0&&&&else&r.x[i]&=&rnd.nextInt(90)+10;&//&10-99&&&&return&r;&//&结果为r.x&&}&&public&BigInteger&bignumbY(int&len)&{&&&&if(len&=0)&return&&&&&BigInteger&r&=&new&BigInteger();&&&&Random&rnd&=&new&Random();&&&&r.y&=&&&+(rnd.nextInt(9)+1);&len--;&//&1-9,&最高位不为0&&&&while(len&0)&r.y&+=&rnd.nextInt(10);&&&&return&r;&//&结果为r.y&&}}处理加减乘除需要自己再写其他函数。
采纳率：61%
我查了下biginteger的api，有这么一个构造方法：BigInteger(String val)，你可以通过String生成一个大数的字符串，在通过这个字符串来得到一个biginteger对象。StringBuffer bigstring=new StringBuffer();int length=10;//自定义的位数for（int i=0;i&i++）{bigstring.append(Random.nextInt(10));}BigInteger big=new BigInteger(temp);这样就得到一个大数，我的这台机器上没有eclipse，所以代码都是手写的，你自己在机器上调试看看，不要什么都要看被人的具体代码，自己多思考看看。个人看法，仅供参考！
MARK！！！
为您推荐：
其他类似问题
大数的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。2954人阅读
算法竞赛入门经典（第2版）第5章 C++与STL入门（10）
竞赛入门经典（第2版）
第5章C++与STL入门
大整数类BigInteger
跟踪调试后的感悟。
1、=(long long num)该赋值方式实际运用价值不大，输入数据一长容易越界。=(const
string& str)赋值方式极具实用价值，只要string不越界，就可以处理该整数。
2、将大整数分块处理，BASE=,WIDTH=8，每八位数为一个单元，进行处理:第一个八位数据的得来，num%BASE；下一个8位数据，num/=BASE;num%BASE；依此类推。
3、此类问题的核心在于四则运算的处理，在看代码之前，猜测，加法难在进位的处理，即不同单元数据衔接（每8位为一个单元），故应从低位向高位处理。
4、函数处理过程中，BigInteger引用&的目的是为使避免不必要的值被复制。
5、每个单元选择8位数理由：32位整数-2^31~2^31-1即-~7，八位数相加包括进位，最多9位数，没有超过上述整数范围，故本程序，如果只处理加法，极限可以考虑到BASE=,WIDTH=9。经测试验证通过。
6、四则运算，经跟踪，发现不同单元中进位联系完全靠变量g，程序在此处处理得十分巧妙。
7、通过http://blog.csdn.net/no_retreats/article/details/7853066研究了substr的用法：
string a=s.substr(0,5);
//获得字符串s中 从第0位开始的长度为5的字符串//默认时的长度为从开始位置到尾
8、通过http://blog.csdn.net/nancy_m/article/details/7583550研究了c_str()的用法：
c_str() 以 char* 形式传回 string 内含字符串
如果一个函数要求char*参数，可以使用c_str()方法：
string s = "Hello World!";
printf("%s", s.c_str()); //输出 "Hello World!"
9、通过http://blog.sina.com.cn/s/blog_7b3an.html学习了vector中back()的用法：
返回当前vector容器中末尾元素的引用。
10、力争能独立编码，该代码阅读比想象的要复杂。
11、基本处理思路，从低位向高位处理。如按如下方式存储于数组中：
s[0]= s[1]= s[2]=1234
12、将operator =,operator +放入BigInteger类中，可以减少只用一个参数，另一个默认参数是该类的实例。若放类外部，则要用两个参数。
13、len=(str.length()-1)/WIDTH-1;技巧如下，若有32位，分成(32-1)/8+1=4块；若有31位，分成(31-1)/8+1=4块；若有33位，分成(33-1)/8+1=5块，所有情况通吃，好技巧。
14、vector元素访问可以参考数组，但赋值处理只能用push_back，若用v[i]=x%BASE；会报错，只能用v.push_back(x%BASE);
15、BigInteger分析暂告一段落，已将核心代码研究了，等功力深厚了，再回过头来研究。
附上代码：
#include &iostream&
#include &vector&
#include &string&
struct BigInteger{
static const int BASE=;
static const int WIDTH=8;
vector&int&
BigInteger operator = (const string& s){
blocks=(s.length()-1)/WIDTH+1;
for(i=0;i&i++){
end=s.length()-i*WIDTH;
start=max(0,end-WIDTH);
sscanf(s.substr(start,end).c_str(),"%d",&x);
v.push_back(x);
BigInteger operator + (const BigInteger &b){
for(i=0,g=0;;i++){
if(g==0&&i&=v.size()&&i&=b.v.size()){//无进位，两个BigInteger实例均已遍历完成
if(i&v.size())
if(i&b.v.size())
x+=b.v[i];
c.v.push_back(x%BASE);
istream& operator && (istream &in, BigInteger &b){
ostream& operator && (ostream &out,const BigInteger &b){
char buf[20];
out&&b.v.back();//最高位不足8位的预防处理
for(i=b.v.size()-2;i&=0;i--){
sprintf(buf,"%08d",b.v[i]);//不足8位补0
int main(){
BigInteger a,b;
cin&&a&&b;
cout&&a+b&&