关于java:一文搞懂大数加减乘除运算

前言

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

各位有过分类刷题的小伙伴，可能看到很多人分类 字符串、贪婪、动静布局、bfs、dfs、大数、数论等，初听大数，你可能会差别：大数是个啥？听起来怪高大上的。

大数，其实就是很大很大数字(可能远超32、64位，根底类型无奈示意)的加减法，在Java中咱们能够应用一个大数类(BigInteger等)很容易解决大数的各种运算，但如果遇到面试官他必定会让你手写的。

这个数字个别用字符串、链表等模式示意、返回，大数运算的外围就是：模仿，模仿咱们日常用纸笔算数字的加减乘除流程，而后再依据计算机、编程语言等个性适当存储计算即可，不过，大数除法运算略微非凡一点，和咱们间接模仿的思维形式稍有不同。

大数加法

大数加法是最简略的，简略模仿即可。首先，咱们想一下两个数加法的流程：从右向左计算求和、进位，始终到最初。

在编程语言中同样也是模仿从右向左逐位相加的过程，不过在具体实现上须要留神一些细节。

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

2、从右往左进行计算，能够将后果放到一个数组中最初组成字符串，也能够应用StringBuider拼接，拼接的时候最初要逆置一下程序。

3、余数每次叠加过须要清零，两数相加如果大于等于10即有余数，增加到后果中该地位的数也应该是该数%10的后果。

4、计算完最初还要看看余数是否为1，如果为1须要将其增加到后果，例如 "991"+"11"算三个地位为002但还有一个余数须要增加，所以应该是1002。

当然在具体实现上办法较多，你能够首先就将字符串逆置而后从前往后就能够计算了。当然我这里实现的是字符串从后向前各个位对应计算，而后将后果程序增加到StringBuilder上。

这题在力扣【415两数相加】能够测验本人代码，实现代码为：

<code class="java">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();
}

大数减法

加法对应的就是减法，有了下面大数加法的实现思路，那么我想你在大数减法也应该有点想法，然而减法和加法不同的是减法有地位的区别，加法须要进位而减法须要借位。并且大整负数减法可能产生正负也不肯定。

两个负数，如果大数减去小数，那么一切正常，后果是一个负数；但如果小数减去大数，那么后果将是一个正数，并且后果解决起来源gaodai#ma#com搞*代#码网来比拟麻烦。 所以在这里全副转成大-小解决(大-小不存在不能借位的状况)。

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【大数相减】上验证本人代码的正确性，具体实现的代码为：

<code class="java">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字符串相乘】，具体代码位：

<code class="java">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

下次再见！

喜欢 (0)赏

[搞代码]

分享 (0)