首页 > 代码库 > java-两个大数相加
java-两个大数相加
题目要求：用字符串模拟两个大数相加。
一、使用BigInteger类、BigDecimal类
public static void main(String[] args) {
String a="8888899999999888";
String b="88888888888888";
String str=new BigInteger(a).add(new BigInteger(b)).toString();
System.out.println(str);
}
二、反转字符串、对齐字符串缺位补0、将两个正整数相加
public class AddTwoNumber {
public static String add(String n1,String n2){
String result="";
//反转字符串
String num1=new StringBuffer(n1).reverse().toString();
String num2=new StringBuffer(n2).reverse().toString();
int len1=num1.length();
int len2=num2.length();
int maxLen=len1>len2?len1:len2;
//定义和(可能)
int nSum[]=new int[maxLen+1];
boolean nOverFlow=false;
//对齐字符串
if(len1<len2){
for (int i = len1; i < len2; i++) {
num1+="0";
}
}else if(len1>len2){
for (int i = len2; i < len1; i++) {
num2+="0";
}
}
//两个数相加
for (int i = 0; i < maxLen; i++) {
//进位数从第二次开始算
if (nOverFlow) {
nSum[i]=Integer.parseInt(num1.charAt(i)+"")+
Integer.parseInt(num2.charAt(i)+"")+1;
}else{
nSum[i]=Integer.parseInt(num1.charAt(i)+"")+
Integer.parseInt(num2.charAt(i)+"");
}
//处理溢出位
nOverFlow=handleSumOverTen(nSum,i);
}
//处理最高位
if(nOverFlow) {
nSum[maxLen] = 1;
}else {
nSum[maxLen] =0 ;
}
for (int i = 0; i < nSum.length; i++) {
result+=String.valueOf(nSum[i]);
}
String result1=new StringBuffer(result).reverse().toString();
return result1;
}
private static boolean handleSumOverTen(int[] nSum, int i) {
boolean flag = false;
if(nSum[i] >= 10) {
nSum[i] = nSum[i] - 10;
flag = true;
}
else {
flag = false;
}
return flag;
}
public static void main(String[] args) {
String num=add("8888899999999888", "88888888888888");
System.out.println(num);
}
}
三、补齐字符串(使用StringBuffere中的insert方法在字符串索引为0的位置插入len个0)、对齐相加
public class BigNumSum2 {
public static void main(String[] args) {
int[] result = bigNumSum("8888899999999888", "88888888888888");
for(int i=0; i < result.length; i++) {
System.out.print(result[i]);
}
}
public static int[] bigNumSum(String num1, String num2) {
String number1 = num1;
String number2 = num2;
int len1=number1.length();
int len2=number2.length();
int len=Math.abs(len1-len2);
char insertNum[]=new char[len];
for (int i = 0; i < insertNum.length; i++) {
insertNum[i]=‘0‘;
}
String str1="";
String str2="";
//补齐两个字符串
if (len1<len2) {
str1=new StringBuffer(number1).insert(0, insertNum).toString();
str2=number2;
}else if(len1>len2){
str1=number1;
str2=new StringBuffer(number2).insert(0, insertNum).toString();
}
//字符串转换成字符数组
char[] ch1 = str1.toCharArray();
char[] ch2 = str2.toCharArray();
int[] sum;
//为true时表示两数相加>=10
boolean flag = false;
//相加结果的长度为任一长度+1，因为最高位相加可能>10
sum = new int[ch1.length+1];
//从个位开始相加
for(int i=ch1.length-1; i>=0; i--) {
//如果上一次相加和大于1，本次相加结果加1
if(flag) {
//
sum[i+1] = (int)(ch1[i] - ‘0‘) + (int)(ch2[i] - ‘0‘) + 1;
}else {
sum[i+1] = (int)(ch1[i] - ‘0‘) + (int)(ch2[i] - ‘0‘);
}
flag = handleSumOverTen(sum, i); //处理两数相加是否>10
}
handleTopDigit(flag, sum); //处理最高位
return sum;
}
/*
* 处理两数相加是否>10
*/
public static boolean handleSumOverTen(int[] sum, int i) {
boolean flag = false;
if(sum[i+1] >= 10) {
sum[i+1] = sum[i+1] - 10;
flag = true;
}
else {
flag = false;
}
return flag;
}
/*
* 处理最高位
*/
public static void handleTopDigit(Boolean flag, int[] sum) {
if(flag) {
sum[0] = 1;
}else {
sum[0] = 0;
}
}
}
四、此方法与三中方法基本一致，不同之处是三中方法因为将两个字符串长度通过补0相等而不需要分步进行判断，但整体运行效率还是四分法高
public class BigNumSum {
public static void main(String[] args) {
int[] result = bigNumSum("8888899999999888", "88888888888888");
for(int i=0; i < result.length; i++) {
System.out.print(result[i]);
}
}
public static int[] bigNumSum(String num1, String num2) {
String number1 = num1;
String number2 = num2;
//字符串转换成字符数组
char[] ch1 = number1.toCharArray();
char[] ch2 = number2.toCharArray();
int[] sum;
//取位数之差
int len = Math.abs(ch1.length - ch2.length);
//为true时表示两数相加>=10
boolean flag = false;
//如果两个数的长度相等
if(ch1.length == ch2.length) {
//相加结果的长度为任一长度+1，因为最高位相加可能>10
sum = new int[ch1.length+1];
//从个位开始相加
for(int i=ch1.length-1; i>=0; i--) {
//如果上一次相加和大于1，本次相加结果加1
if(flag) {
//
sum[i+1] = (int)(ch1[i] - ‘0‘) + (int)(ch2[i] - ‘0‘) + 1;
}else {
sum[i+1] = (int)(ch1[i] - ‘0‘) + (int)(ch2[i] - ‘0‘);
}
flag = handleSumOverTen(sum, i, len); //处理两数相加是否>10
}
handleTopDigit(flag, sum); //处理最高位
return sum;
}
else if(ch1.length > ch2.length) { //如果数1的长度大于数2的长度
sum = new int[ch1.length+1]; //结果的长度为数1的长度+1
for(int i=ch2.length-1; i>=0; i--) {
if(flag) {
sum[i+len+1] = (int)(ch1[i+len] - ‘0‘) + (int)(ch2[i] - ‘0‘) + 1;
}
else {
sum[i+len+1] = (int)(ch1[i+len] - ‘0‘) + (int)(ch2[i] - ‘0‘);
}
flag = handleSumOverTen(sum, i, len);
}
for(int i=ch1.length-ch2.length-1; i>=0; i--) { //处理数1多出来的位数
if(flag) {
sum[i+1] = (int)(ch1[i] - ‘0‘) + 1;
}
else {
sum[i+1] = (int)(ch1[i] - ‘0‘);
}
flag = handleSumOverTen(sum, i, 0);
}
handleTopDigit(flag, sum);
return sum;
}
else {
sum = new int[ch2.length+1];
for(int i=ch1.length-1; i>=0; i--) {
if(flag) {
sum[i+len+1] = (int)(ch1[i] - ‘0‘) + (int)(ch2[i+len] - ‘0‘) + 1;
}
else {
sum[i+len+1] = (int)(ch1[i] - ‘0‘) + (int)(ch2[i+len] - ‘0‘);
}
flag = handleSumOverTen(sum, i, len);
}
for(int i=ch2.length-ch1.length-1; i>=0; i--) {
if(flag) {
sum[i+1] = (int)(ch2[i] - ‘0‘) + 1;
}
else {
sum[i+1] = (int)(ch2[i] - ‘0‘);
}
flag = handleSumOverTen(sum, i, 0);
}
handleTopDigit(flag, sum);
return sum;
}
}
/*
* 处理两数相加是否>10
*/
public static boolean handleSumOverTen(int[] sum, int i, int len) {
boolean flag = false;
if(sum[i+len+1] >= 10) {
sum[i+len+1] = sum[i+len+1] - 10;
flag = true;
}
else {
flag = false;
}
return flag;
}
/*
* 处理最高位
*/
public static void handleTopDigit(Boolean flag, int[] sum) {
if(flag) {
sum[0] = 1;
}else {
sum[0] = 0;
}
}
}
java-两个大数相加