前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Java实现大整数乘法

Java实现大整数乘法

作者头像
全栈程序员站长
发布2022-09-05 11:33:03
3460
发布2022-09-05 11:33:03
举报
文章被收录于专栏:全栈程序员必看

大家好,又见面了,我是你们的朋友全栈君。

1 问题描述 计算两个大整数相乘的结果。

2 解决方案 2.1 蛮力法

代码语言:javascript
复制
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字符串长度小于A时,在B字符串前补0,使得两个字符串长度一致
            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字符串前补0,使得两字符串长度一致
            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)+" 毫秒");
    }
}

运行结果:

代码语言:javascript
复制
大整数A*B的结果:121932631386721831198089710747298668585104317165230580938992491445929653074852215402191571860797295610655490
验证后A*B的结果:121932631386721831198089710747298668585104317165230580938992491445929653074852215402191571860797295610655490
耗时:4 毫秒

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/137009.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022年6月2,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档