大整数的加法运算_大整数相减

大整数的加法运算_大整数相减问题:如果给出两个很大很大的整数,这两个数大到long类型也装不下,如何求他们的和呢?回顾起小学数学,当我们需要计算两个较大数目的加减乘除,我们是用列竖式的方式来计算的。因为对于较大的整数,我们无法一步就直接计算出结果,所以不得不把计算过程拆分成一个一个小步骤来完成。不仅仅是人脑,对于计算机来说也可以这样解决。程序不可能通过一条指令计算出两个大整数之和,却可以像列竖式一样将运算拆解成若干小…

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

问题:

如果给出两个很大很大的整数,这两个数大到long类型也装不下,比如100位整数,如何求它们的和呢?

分析:

回顾起小学数学,当我们需要计算两个较大数目的加减乘除,我们是用列竖式的方式来计算的。
在这里插入图片描述

因为对于较大的整数,我们无法一步就直接计算出结果,所以不得不把计算过程拆分成一个一个小步骤来完成。

不仅仅是人脑,对于计算机来说也可以这样解决。程序不可能通过一条指令计算出两个大整数之和,却可以像列竖式一样将运算拆解成若干小运算。

可是,如果大整数超出了long型的范围,该如何存储这个数呢?
我们想到了数组,可以用数组的每一个元素存储整数的每一个数位

在程序中列出的 “竖式” 究竟是什么样子呢?我们以 426709752318 + 95481253129 为例,来看看大整数相加的详细步骤:
  1. 第一步,把整数倒序存储,整数的个位存于数组0下标位置,最高位存于数组长度-1下标位置。之所以倒序存储,更加符合我们从左到右访问数组的习惯。
    在这里插入图片描述

  2. 第二步,创建结果数组,结果数组的最大长度是较大整数的位数+1,原因是可以存储进位。
    在这里插入图片描述

  3. 第三步,遍历两个数组,从左到右按照对应下标把元素两两相加,结果存储在结果数组对应下标的位置上,进位存储在下一个位置,就像小学生计算竖式一样。

例子中,最先相加的是数组A的第1个元素8和数组B的第1个元素9,结果是7,进位1。把7填充到Result数组的对应下标,进位的1填充到下一个位置:
在这里插入图片描述
第二组相加的是数组A的第2个元素1和数组B的第2个元素2,结果是3,再加上刚才的进位1,把4填充到Result数组的对应下标:
在这里插入图片描述
依此类推…一直把数组的所有元素都相加完毕:
在这里插入图片描述

  1. 第四步,把结果数组的全部元素再次逆序,去掉首位的,就是最终结果。
    在这里插入图片描述

代码如下:

    /**
     * 大整数求和
     * @param bigNumberA  大整数A
     * @param bigNumberB  大整数B
     */

    public static String bigNumberSum(String bigNumberA, String bigNumberB) {

        //1.把两个大整数用数组逆序存储,数组长度等于较大整数位数+1

        int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();

        int[] arrayA = new int[maxLength+1];
        for(int i=0; i< bigNumberA.length(); i++){
            arrayA[i] = bigNumberA.charAt(bigNumberA.length()-1-i) - '0';//“ - '0'”是将String型转化为int型
        }

        int[] arrayB = new int[maxLength+1];
        for(int i=0; i< bigNumberB.length(); i++){
            arrayB[i] = bigNumberB.charAt(bigNumberB.length()-1-i) - '0';
        }

        //2.构建result数组,数组长度等于较大整数位数+1
        int[] result = new int[maxLength+1];

        //3.遍历数组,按位相加
        for(int i=0; i<result.length; i++){
            int temp = result[i];				//加上前一位的进位
            temp += arrayA[i];
            temp += arrayB[i];
            
            //判断是否进位
            if(temp >= 10){
                temp = temp-10;				//有进位的话将temp化为一位数
                result[i+1] = 1;					//将进位1存储到结果数组的下一位
            }

            result[i] = temp;					//将1位数存储到结果数组对应位

        }

        //4.把result数组再次逆序并转成String
        StringBuilder sb = new StringBuilder();

        //用于标记是否找到大整数的最高有效位
        boolean findFirst = false;

        for (int i = result.length - 1; i >= 0; i--) {//从后往前
            if(!findFirst){
                if(result[i] == 0){				//用于跳过结果数组末尾的0
                    continue;
                }
                findFirst = true;
            }
            sb.append(result[i]);
        }

        return sb.toString();

    }

    public static void main(String[] args) {
        System.out.println(bigNumberSum("426709752318", "95481253129"));
    }

时间复杂度:

那么,这个算法的时间复杂的是多少呢?
如果给定大整数的最长位数是n,那么创建数组、按位计算、结果逆序的时间复杂度各自是O(n),整体的时间复杂度也是O(n)。

优化:

其实这个算法还存在可以优化的地方。如何优化呢?

我们之前是把大整数按照每一个十进制数位来拆分,比如较大整数的长度有50位,那么我们需要创建一个51位的数组,数组的每个元素存储其中一位。

我们真的有必要把原整数拆分得那么细吗?
显然不需要,只需要拆分到可以被直接计算的程度就够了。

int类型的取值范围是 -2147483648——2147483647,最多有10位整数。为了防止溢出,我们可以把大整数的每9位作为数组的一个元素,进行加法运算。如此一来,占用空间和运算次数,都被压缩了9倍。

本文来源于公众号程序员小灰,有删改。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/125207.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • vue删除数组中指定元素_如何删除数组中的元素

    vue删除数组中指定元素_如何删除数组中的元素vue删除数组中指定的元素exportdefault{ data(){ return{ mpList:[‘测试一’,’测试二’,’测试三’] } }, methods:{ del(item){ letlistVar=newArray for(leti=0;i<this.mpList.length;i++){ listVar.push(this.mpList) if(this.mpList[i]==item){

  • cmd查询mysql端口占用_windows cmd快速查看端口占用情况

    cmd查询mysql端口占用_windows cmd快速查看端口占用情况在调试服务或者程序的时候我们经常会通过检测对应端口是否打开来判断服务是否成功启动,本例就拿mysql的3306来实验。再看看3306端口是否已经被占用一、查看端口占用netstat-aon|findstr”3306″二、查看id对应的程序tasklist|findstr”6572″==============================C:\Users\Administrator>…

  • vmware15最新激活码2021【中文破解版】[通俗易懂]

    (vmware15最新激活码2021)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

  • map的遍历方式「建议收藏」

    map的遍历方式「建议收藏」@org.junit.TestpublicvoidtestHashMap(){Map<String,String>map=newHashMap<>(4);

  • php错误处理_MSVCP120.dll

    php错误处理_MSVCP120.dll当您搜索“phpMSVCR110.dll”时,由于此问题的链接显示在返回结果的最上方(更不用说它的浏览量已超过10万,并且还在不断增长),因此,这里有一些其他说明,在您寻求以下内容时可能会派上用场解决MSVCR110.dll错误…答案中描述的方法不仅对MSVCR110.dll情况有效,而且在寻找其他版本(例如较新的MSVCR71.dll)时也适用,并且我将答案更新为包括VC15,即使它不…

    2022年10月25日
  • python 菜鸟教程 正则_华为mate30好用不

    python 菜鸟教程 正则_华为mate30好用不正则表达式简介正则表达式,是一个特殊的字符序列,又称规则表达式(英语:RegularExpression,在代码中常简写为regex、regexp或RE),本质而言是一种小型的,高度专业化的编程语言。Python自1.5版本起增加了re模块,re模块使Python语言拥有全部的正则表达式功能。正则语法表关于正则语法表,别想其他的都背过就行了。不管你是python还是其他…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号