(加强版)大数加减乘除，一文彻底搞定

缺乏、安全感 2023-01-14 02:55 206阅读 0赞

### 前言 ###

大家好，我是**bigsai**！(上次发布的忘加原创并且今天的把**内容扩充了一下**)最近，大数加减频频登上笔试的舞台，小伙伴们在群里也分享自己遇到面试官碰到大数运算的题目，想着这么**重要而简单**的知识点我还没写过，那得好好和大家一起总结一下。

![445a55789014dc251e97fc6df13fc51d.png][]

群内情况

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

![3f3eeb0b36da5a9592cb761d3fa6802d.png][]

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

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

### 大数加法 ###

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

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

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

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

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

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

![aef35fbbf370565302c7a99926accab7.png][]

一个加法流程

当然在具体实现上方法较多，你可以首先就将字符串逆置然后从前往后就可以计算了。当然我这里实现的是字符串从后向前各个位对应计算，然后将结果顺序添加到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();
    }

### 大数减法 ###

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

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

![430b3c898059a47acee69821716a4918.png][]

减法转成大-小

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),那么处理上一位进行减法时候还要将借位的处理一下。

![5832fdcd5b0acf30504622ec2b91307a.png][]

一个减法大概流程

这题在力扣上没有原题，但是可以在小米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类型数组存储各位的乘积然后从右向左进行进位，如下图所示。

![aef623bfb84f62322bd4d920e1d8bc9f.png][]

先计算后进位

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

![2fff15e10ff69d2991f56cea0d8b7bea.png][]

一个乘法流程

你可能会疑问，如果**两个数组的长度分别为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，一直到不能减为止。

![49e0e388dcc3ea5c560cc32b17a172d8.png][]

除法转成减法运算

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

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

![1a34b0089fbcda2f529fef364a9fd49b.png][]

计算思想

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

这部分代码我也简单给一下(其他函数上面贴过就不重复贴啦)：

//假设 num1>num2
    public static String divideString(String num1,String num2)
    {
        String value="0";//结果
        while (compare(num1,num2))
        {
            StringBuilder sbTeam=new StringBuilder(num2);//用这个往后面不断加0 和num做减法
            StringBuilder sbCount=new StringBuilder("1");//次数 可能很大
            int subLen=num1.length()-num2.length();//统计大概要加几个零 
            for(int i=0;i<subLen;i++)
            {
                sbTeam.append('0');
                sbCount.append('0');
            }
            //如果0 加多了 那么要删一个 类似"12300" / "23" "12300"比"23000"小
            //所以要 "2300" 对应比"23"扩大 "100"倍数，每减一次"2300" 则结果加"100"
            if(!compare(num1,sbTeam.toString()))
            {
                sbTeam=sbTeam.deleteCharAt(sbTeam.length()-1);
                sbCount=sbCount.deleteCharAt(sbCount.length()-1);
            }
            // 一直能减的时候
            while (compare(num1,sbTeam.toString()))
            {
                num1=subtractString(num1,sbTeam.toString());
                value=addStrings(sbCount.toString(),value);
            }
        }
        return  value;
    }

简单测试了下，正确性还是ok的：

![110eb38f23e63415ab8737c394a0c1ed.png][]

除法测试

### 番外篇 ###

除了上面直接的大数加减乘除，还有一些变形的题目需要我们特殊处理一下，比如可能会使用链表等存储处理，下面分享两道题。

两数相加(力扣02)

题目描述：

> 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表
> 
> 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

![0ce07a1d7b4d1ff2952f492d576073cb.png][]

img

**提示：**

*  每个链表中的节点数在范围 `[1, 100]` 内
 *  `0 <= Node.val <= 9`
 *  题目数据保证列表表示的数字不含前导零

本题其实就是用一个链表存储一个数字(逆序存储)，你需要给它计算出结果后在 逆序 存储到一个链表中返回。  
所谓加法的运算规则：**从两个数的最低位进行计算，进行到下一位的时候需要考虑进位问题。一直到最后**，而本题所给的链表刚好可以用来直接计算，因为链表头都是数字最低位可以直接相加，然后一直遍历到结束。可以用一个常数表示进位。

![ac98229156e6f63503f25b6387859044.png][]

运算逻辑

在具体实现(链表)的时候：

*  创建新的链表，每次将计算的数值插入到链表尾部即可。
 *  需要准确表示进位，并且最后要考虑以下进位
 *  妥善返回正确节点，可以用一个头节点用来使得所有节点都正常操作，而不需要特殊判断。  
    通过代码第一次比较啰嗦的写法：

当然，如果你遍历链表把各个数字取出来，使用字符串、数字转换然后相加得到一个数字，最后在转成字符串、链表的理论可以，可以自行实现。

优化后的代码为：

//更简洁的写法
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      ListNode node=new ListNode(0);
      ListNode team=node;
      int jin=0;//进位
      while(l1!=null||l2!=null)
      {
        int num=jin;
        if(l1!=null)
        {
          num+=l1.val;l1=l1.next;
        }
        if(l2!=null)
        {
          num+=l2.val;l2=l2.next;
        }
        jin=num/10;
        num%=10;
        team.next=new ListNode(num);
        team=team.next;
    
      }
      if(jin!=0)team.next=new ListNode(jin);
      return node.next;
    }

两数相加2(力扣445)

题目描述：

> 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
> 
> 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
> 
> 进阶：如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

> 输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
> 
> 输出：7 -> 8 -> 0 -> 7

本题的话和上面不一样链表不是逆置的，但是**加法运算其实需要从最后面对齐开始**，也就是理论上应该从链表尾部开始向前，但是这是个单链表，这样运算的话时间复杂度太高，所以我们**要用空间换时间：用栈来解决。**

将链表的节点依次放到两个栈中，然后两个栈同时取数计算。但是待返回的是个链表，所以采取头插法即可(如果不头插最后反转也可)，具体流程可以参考如下图：

![083442a8aa01c59b185edf548dc4c6fd.png][]

逻辑

实现代码为：

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            Stack<Integer>stack1=new Stack<>();
            Stack<Integer>stack2=new Stack<>();
            while (l1!=null)
            {
                stack1.add(l1.val);
                l1=l1.next;
            }
            while (l2!=null)
            {
                stack2.add(l2.val);
                l2=l2.next;
            }
            ListNode val=new ListNode(0);//带头结点
            int moreadd=0;//余数
            while (!stack1.isEmpty()||!stack2.isEmpty()||moreadd!=0)
            {
                int num=moreadd;//num=余数+链表1+链表2
                if(!stack1.isEmpty())
                    num+=stack1.pop();
                if(!stack2.isEmpty())
                    num+=stack2.pop();
                moreadd=num/10;
                num=num%10;
                //链表头插
                ListNode node=new ListNode(num);
                node.next=val.next;
                val.next=node;
            }
            return val.next;
        }
    }

### 结语 ###

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

光看没有还要多多练习对应的题目，当然本人水平有限上面理解可能有误或者不到位还请指正！

**推荐阅读**：

**[备战实习求职的一些感想(已拿阿里offer)][offer]**

[**花5分钟看这篇之前,你才发现你不懂RESTful**][5_RESTful]

**[Java自学方法和路线，我万字推荐你这样学][Java]**

**[ 面试官会的位运算奇淫技巧][Link 1]**

相互吹捧，共同进步，欢迎**加个好友**交流，也可**拉你进群交流学习**，也可做个朋友圈点赞之交！如果感觉有收获还请**点赞、在看、分享**一波！

![d832b2dba4fe8c9e4873d61aa905232a.png][]

[445a55789014dc251e97fc6df13fc51d.png]: /images/20221022/7b911348ca964a47be404dbf7daec4fa.png
[3f3eeb0b36da5a9592cb761d3fa6802d.png]: /images/20221022/735b39f3c5fb492ca95b167320167940.png
[aef35fbbf370565302c7a99926accab7.png]: /images/20221022/d14a9a9fb95d4f29934a6f161db152d5.png
[430b3c898059a47acee69821716a4918.png]: /images/20221022/97959c7c2d8c428396c90474a62b8c9d.png
[5832fdcd5b0acf30504622ec2b91307a.png]: /images/20221022/22043fe56f36482ca0aae66b33fef683.png
[aef623bfb84f62322bd4d920e1d8bc9f.png]: /images/20221022/22d6dbc3496042678da0168286b8f8f0.png
[2fff15e10ff69d2991f56cea0d8b7bea.png]: /images/20221022/5835de5d48c240db9427a984abae7031.png
[49e0e388dcc3ea5c560cc32b17a172d8.png]: /images/20221022/7417bf91cfee48f28c20ee504e6a1010.png
[1a34b0089fbcda2f529fef364a9fd49b.png]: /images/20221022/3b6747ca227b45c689c1e6920efc1dbf.png
[110eb38f23e63415ab8737c394a0c1ed.png]: /images/20221022/d14d3b5d499d4164bb0f088cdf878f5c.png
[0ce07a1d7b4d1ff2952f492d576073cb.png]: /images/20221022/36e60abb38f145a3ae3cea039c46c2ec.png
[ac98229156e6f63503f25b6387859044.png]: /images/20221022/3211975890c24e13a2e2db41a53a0da6.png
[083442a8aa01c59b185edf548dc4c6fd.png]: /images/20221022/0ad28b5d790b4c2481909da85809f96b.png
[offer]: http://mp.weixin.qq.com/s?__biz=Mzk0MDIxNjU3OA%3D%3D&chksm=c2e4530ff593da19e9edcce5677652ea0c31631a8031faa2c1464537e3253466cc08adb5ab6b&idx=1&mid=2247486306&scene=21&sn=32076924e9c95ab26e3266413869382f#wechat_redirect
[5_RESTful]: http://mp.weixin.qq.com/s?__biz=Mzg2MTE1NjA2Mg%3D%3D&chksm=ce1a2f43f96da6554a60ab9ce7f37ad26992ed2b9791693dd4d7e50fb7efc44e88ac77b3e2c0&idx=1&mid=2247485682&scene=21&sn=e7959e1367394eb6f3a8fe37aa109cb1#wechat_redirect
[Java]: http://mp.weixin.qq.com/s?__biz=Mzk0MDIxNjU3OA%3D%3D&chksm=c2e4539af593da8c5759ec9444e742d4d77bfc3e2ddcae03a68ded425aa1e7f1057768b1047f&idx=1&mid=2247486455&scene=21&sn=e7421f881d97cee9d4fae96638f8306a#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=Mzg2MTE1NjA2Mg%3D%3D&chksm=ce1a2d19f96da40f807426a7322e9a40e6736664e90ab412a0edeaee20dffba0fb7a3637b711&idx=1&mid=2247486120&scene=21&sn=05cf27f6d569a86030f6bef894ee7f7f#wechat_redirect
[d832b2dba4fe8c9e4873d61aa905232a.png]: /images/20221022/1079dc7f096b4916b234673ec6311058.png