目录
1 问题描述
计算两个大整数相乘的结果。
2 解决方案
2.1 蛮力法
package com.liuzhen.chapter5;
import java.math.BigInteger;
public class BigNumber {
/*
* 参数A:进行乘法运算的大整数A，用字符串形式表示
* 参数B：进行乘法运算的另一个大整数B，用字符串形式表示
* 函数功能：以字符串形式返回A*B的结果
*/
public String getMultiBigNumber(String A,String B){
if(A.length() > B.length()){ //当B字符串长度小于Ａ时，在Ｂ字符串前补０，使得两个字符串长度一致
char[] temp = new char[A.length()-B.length()];
for(int i = 0;i < A.length() - B.length();i++)
temp[i] = '0';
B = String.valueOf(temp) + B;
}
if(A.length() < B.length()){ //当A字符串长度小于B时，在A字符串前补０，使得两字符串长度一致
char[] temp = new char[B.length()-A.length()];
for(int i = 0;i < B.length() - A.length();i++)
temp[i] = '0';
A = String.valueOf(temp) + A;
}
int len = A.length() + B.length();
char[] arrayA = A.toCharArray();
char[] arrayB = B.toCharArray();
for(int i = 0;i < arrayA.length;i++) //检查字符串A中是否有非数字的字符
if(arrayA[i] < '0' || arrayA[i] > '9')
return null;
for(int i = 0;i < arrayB.length;i++) //检查字符串B中是否有非数字的字符
if(arrayB[i] < '0' || arrayB[i] > '9')
return null;
char[] result = new char[len]; //用于存放最终乘法运算结果，长度len表示A*B的最长长度
for(int i = 0;i < len;i++) //初始化字符数组result，各个元素均为'0'
result[i] = '0';
int countI = 0; //用于计算当前B中已经和A中每个字符进行完乘法运算的字符个数
for(int i = arrayB.length-1;i >= 0;i--){
int tempB = arrayB[i] - '0';
int countJ = 0; //用于计算当前A中正在进行乘法运算的字符个数
for(int j = arrayA.length - 1;j >= 0;j--,countJ++){
int tempA = arrayA[j] - '0';
int tempRe = (tempB * tempA) % 10; //用于计算当前位置的数
int tempResult = result[(len-1-countJ)-countI] - '0'; //当前位置已包含的结果
tempResult += tempRe;
//count--表示当前A字符串中进行乘法运算的字符位置，countI表示当前B字符串中进行乘法运算的字符位置
//(count--)-countI则表示当前进行乘法运算两个数字结果的最低位的位置
result[(len-1-countJ)-countI] = (char) (tempResult%10 + 48); //当前位置数最终结果
int tempDi = tempB * tempA / 10 + tempResult / 10; //用于计算进位
for(int k = 1;tempDi > 0;k++){ //处理进位操作
//当前下第k个位置包含的结果
int tempResultK = result[(len-1-countJ)-countI-k] - '0';
tempResultK += tempDi;
result[(len-1-countJ)-countI-k] = (char) (tempResultK%10 + 48);
tempDi = tempResultK / 10;
}
}
countI++;
}
return getNoneZeroString(result);
}
//去掉字符串前面的0
public String getNoneZeroString(char[] result){
int count = 0;
for(int i = 0;i < result.length;i++){
if(result[i] == '0')
count++;
else
break;
}
char[] A = new char[result.length-count];
for(int i = 0;i < result.length-count;i++)
A[i] = result[count+i];
return String.valueOf(A);
}
public static void main(String[] args){
long t1 = System.currentTimeMillis();
BigNumber test = new BigNumber();
String A = "123456789123232342432423441345342523452534235443253254";
String B = "987654322234242424332423414324532542354325235345435435";
System.out.println("大整数A*B的结果："+test.getMultiBigNumber(A, B));
BigInteger bigInteger1 = new BigInteger("123456789123232342432423441345342523452534235443253254");
BigInteger bigInteger2 = new BigInteger("987654322234242424332423414324532542354325235345435435");
bigInteger2 = bigInteger2.multiply(bigInteger1);
System.out.println("验证后A*B的结果："+bigInteger2);
long t2 = System.currentTimeMillis();
System.out.println("耗时："+(t2-t1)+" 毫秒");
}
}
运算结果：
大整数A*B的结果：121932631386721831198089710747298668585104317165230580938992491445929653074852215402191571860797295610655490
验证后A*B的结果：121932631386721831198089710747298668585104317165230580938992491445929653074852215402191571860797295610655490
耗时：4 毫秒