欢迎光临
我们一直在努力

一文搞懂大数加减乘除运算

前言

大家好,我是bigsai!最近,大数加减频频登上笔试的舞台,小伙伴们在群里也分享自己遇到面试官碰到大数运算的题目,想着这么重要而简单的知识点我还没写过,那得好好和大家一起总结一下。

image-20210331190632569

各位有过分类刷题的小伙伴,可能看到很多人分类 字符串、贪心、动态规划、bfs、dfs、大数、数论等,初听大数,你可能会差异:大数是个啥?听起来怪高大上的。

image-20210329191141360

大数,其实就是很大很大数字(可能远超32、64位,基础类型无法表示)的加减法,在Java中我们可以使用一个大数类(BigInteger等)很容易解决大数的各种运算,但如果遇到面试官他肯定会让你手写的。

这个数字一般用字符串、链表等形式表示、返回,大数运算的核心就是:模拟,模拟我们日常用纸笔算数字的加减乘除流程,然后再根据计算机、编程语言等特性适当存储计算即可,不过,大数除法运算稍微特殊一点,和我们直接模拟的思维方式稍有不同。

大数加法

大数加法是最简单的,简单模拟即可。首先,我们想一下两个数加法的流程:从右向左计算求和、进位,一直到最后。

在编程语言中同样也是模拟从右向左逐位相加的过程,不过在具体实现上需要注意一些细节。

1、枚举字符串将其转换程char[]提高效率

2、从右往左进行计算,可以将结果放到一个数组中最后组成字符串,也可以使用StringBuider拼接,拼接的时候最后要逆置一下顺序。

3、余数每次叠加过需要清零,两数相加如果大于等于10即有余数,添加到结果中该位置的数也应该是该数%10的结果。

4、计算完最后还要看看余数是否为1,如果为1需要将其添加到结果,例如 "991"+"11"算三个位置为002但还有一个余数需要添加,所以应该是1002

一个加法流程

当然在具体实现上方法较多,你可以首先就将字符串逆置然后从前往后就可以计算了。当然我这里实现的是字符串从后向前各个位对应计算,然后将结果顺序添加到StringBuilder上。

这题在力扣【415两数相加】可以检验自己代码,实现代码为:

public String addStrings(String num1, String num2) {
// 公众号:bigsai 欢迎你的关注
    int len1=num1.length()-1,len2=num2.length()-1;
    char ch1[]=num1.toCharArray();
    char ch2[]=num2.toCharArray();

    StringBuilder sb=new StringBuilder();
    int remainder =0;//计算余数
    while (len1>=0||len2>=0)
    {
        int n1=len1>=0?(ch1[len1--]-'0'):0;
        int n2=len2>=0?(ch2[len2--]-'0'):0;
        int num=n1+n2+remainder;//求和对应数字
        remainder=num/10;//是否进位
        sb.append(num%10);// 添加到结果字符串中
    }

    if(remainder>0)//是否还需要进位
    {
        sb.append(remainder);
    }
    //反装即为结果
    return sb.reverse().toString();
}

大数减法

加法对应的就是减法,有了上面大数加法的实现思路,那么我想你在大数减法也应该有点想法,但是减法和加法不同的是减法有位置的区别,加法需要进位而减法需要借位。并且大整正数减法可能产生正负也不一定。

两个正数,如果大数减去小数,那么一切正常,结果是一个正数;但如果小数减去大数,那么结果将是一个负数,并且结果处理起来比较麻烦。 所以在这里全部转成大-小处理(大-小不存在不能借位的情况)。

减法转成大-小

1、执行计算前首先比较减数(num1)和被减数(num2)的大小,如果num1>num2,那么就模拟num1-num2的过程,如果num1<num2,那么结果就为-(num2-num1) 。当然可以为了稳定模拟时候一个大一个小,可将num1始终指向较大的那个数,少写一个if/else.

2、在比较两个数字大小的时候,因为是字符形式,首先比较两个字符串的长度,长的那个更大短的那个更小,如果两个字符串等大,那么就可以通过字典序从前往后进行比较(Java可直接使用compareTo方法)。

3、和加法不同的是,减法前面可能产生若干前缀0,这些0是需要你去掉的,例如"1100"-"1000"计算得到的结果位"0100",你就要吧前面的0去掉返回"100"

4、具体实现的时候和加法相似,如果使用StringBuilder存储,需要逆置顺序,如果是个负数,前面还要加上'-'.

5、每个位置正常进行减法运算,如果值小于0,那么就需要向上借位(+10),那么处理上一位进行减法时候还要将借位的处理一下。

一个减法大概流程

这题在力扣上没有原题,但是可以在小米OJ【大数相减】上验证自己代码的正确性,具体实现的代码为:

public static boolean compare(String num1,String num2)
{
    if(num1.length()<num2.length())
        return  false;
    else if(num1.length()>num2.length())
        return true;
    else
        return num1.compareTo(num2)>0;
}
public static  String subtractString(String num1,String num2) {
    char sign='+';//正负号
    //让num1>num2 如果num1<num2 那么结果就是—(num2-num1) 
    //可以先将num1和num2交换和前面情况统一
    if(!compare(num1,num2))
    {
        sign='-';
        String team = num2;
        num2 = num1;
        num1 = team;
    }
    int len1=num1.length()-1;
    int len2=num2.length()-1;

    char ch1[] = num1.toCharArray();
    char ch2[] = num2.toCharArray();
    StringBuilder sb=new StringBuilder();
    int borrow=0;//借位
    while (len1>=0||len2>=0)
    {
        int n1=len1>=0?(ch1[len1--]-'0'):0;
        int n2=len2>=0?(ch2[len2--]-'0'):0;

        int num=n1-n2-borrow;
        borrow=0;
        if(num<0)//需要向前借位
        {
            borrow=1;
            num+=10;
        }
        sb.append(num);
    }

    sb=sb.reverse();//需要先翻转
    int index = 0;//去掉前面没用的’0‘
    while (index<sb.length()&&sb.charAt(index) == '0')
    {
        index++;
    }
    //如果两个数相同 直接返回"0"
    if(index==sb.length())
        return "0";
    if(sign=='+')//如果正数 
        return  sb.substring(index);
    else  return sign+sb.substring(index);//负数需要返回
}

大数乘法

大数乘法乍一想可能比较复杂,因为乘法比起加法可能进位不光是1,还有两个数各种位置都需要相乘计算,这时候就需要我们化繁为简了。

多*多考虑起来可能有些麻烦,但是如果多*一考虑起来呢?如果是多位乘以一位数,那么就拿一位的分别乘以多位数的个位、十位、百位,在计算的同时考虑一下进位的情况。

但是也可以先直接用int类型数组存储各位的乘积然后从右向左进行进位,如下图所示。

先计算后进位

多*多 也是这个道理,将不同位乘积先叠加到对应位置上,然后从右向左进位,一直到不需要进位为止。

一个乘法流程

你可能会疑问,如果两个数组的长度分别为a和b这个数组到底该开多大呢

  • a+b大小就够了,怎么分析呢?其中一个a不变。另一个b变成最小b+1数字即十的倍数,那么这样在相乘的时候也不过是a+b长度,所以这里a+b长度就够了。

这题有力扣对应题可以去试试【43字符串相乘】,具体代码位:

public String multiply(String num1, String num2) {
    if("0".equals(num1)||"0".equals(num2))return "0";
    char a[]=num1.toCharArray();
    char b[]=num2.toCharArray();
    
    int value[]=new int[a.length+b.length];
    
    for(int i=a.length-1;i>=0;i--)
    {
        for(int j=b.length-1;j>=0;j--)
        {
            int index=a.length-1-i+b.length-1-j;
            value[index]+=(a[i]-'0')*(b[j]-'0');
        }
    }
    for(int i=0;i<value.length-1;i++)
    {
        value[i+1]+=value[i]/10;
        value[i]=value[i]%10;
    }
    int index=value.length-1;
    while(value[index]==0)
    {index--;}
    StringBuilder sBuilder=new StringBuilder();
    while (index>=0) {
        sBuilder.append(value[index--]);
    }
    return sBuilder.toString();
}

大数除法

大数加减乘都搞定了,通过模拟来实现,但是大数除法也通过模拟来实现?

并不是,对于大数a/b,一般最多要求求到其整数解或者余数,即a/b=c……d(a,b,c,d均为整);也就是a里面有c个b,并且还剩下d。核心是先求c是多少,对于程序来说,可以通过枚举啊,将除法变成减法,从a中不断减d,一直到不能减为止。

除法转成减法运算

但是有个问题,如果被除数a很大很大,可能有居多个b,那么这样时间复杂度太高了,不可能执行那么多次,那么需要怎么样去优化这个方法呢?

那就要加速寻找次数,减少这个减法的次数了,减法次数减小的一个最好方案就是能不能扩大除数b。如果b后面加个'0',那么算出来的结果就乘以10,减法的次数变成原来十分之一。根据这个思想我们可以一直每次找到b的最大10的倍数(小于a)计算减的次数再换算成减b的总词数,将结果要以字符串方式保留,后面一直迭代到最后为止,这虽然是一道除法运算的题,但是也蕴涵减法和加法(次数叠加到结果中)。

优化思想

当然,也有一些人使用二分法来压缩寻找可以被减的次数也是可以的(加法可以迭代数字实现二分倍数),具体实现的话也不是很困难,但是代码量可能比较多所以一般的面试笔试不会让你现场写的,所以好好掌握前面的减法、减法、乘法的代码即可。

当然,如果你依然很想看大数除法部分的代码,可以百度搜一下或者在文末评论催更一下,如果有感兴趣的可以后面把代码补充上。

结语

到这里,大数的加减乘除基本都讲解完啦,不知道你有没有收获,因为这里的大数都是用字符串的方式存储和处理,遇到的最多,但是也可能遇到一些链表、数组等其他形式存储的需要处理,但是整体的思想都是一样的。

文章已收录在 全网都在关注的数据结构与算法学习仓库 欢迎star
也欢迎大家关注我的同名原创公众号:bigsai

下次再见!

https://segmentfault.com/a/1190000039761875

赞(0)
未经允许不得转载:ITyet » 一文搞懂大数加减乘除运算
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址