大数加减乘除，一文彻底搞定

[[391003]]

 前言

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

群内情况

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

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

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

大数加法

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

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

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

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

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

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

一个加法流程

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

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

 
 
 
 
    
  
  
  
  
  1. public String addStrings(String num1, String num2) { 
    2. 
  
  
  
  
  2. // 公众号：bigsai 欢迎你的关注 
    3. 
  
  
  
  
  3.     int len1=num1.length()-1,len2=num2.length()-1; 
    4. 
  
  
  
  
  4.     char ch1[]=num1.toCharArray(); 
    5. 
  
  
  
  
  5.     char ch2[]=num2.toCharArray(); 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7.     StringBuilder sb=new StringBuilder(); 
    8. 
  
  
  
  
  8.     int remainder =0;//计算余数 
    9. 
  
  
  
  
  9.     while (len1>=0||len2>=0) 
    10. 
  
  
  
  
  10.     { 
    11. 
  
  
  
  
  11.         int n1=len1>=0?(ch1[len1--]-'0'):0; 
    12. 
  
  
  
  
  12.         int n2=len2>=0?(ch2[len2--]-'0'):0; 
    13. 
  
  
  
  
  13.         int num=n1+n2+remainder;//求和对应数字 
    14. 
  
  
  
  
  14.         remainder=num/10;//是否进位 
    15. 
  
  
  
  
  15.         sb.append(num%10);// 添加到结果字符串中 
    16. 
  
  
  
  
  16.     } 
    17. 
  
  
  
  
  17.  
    18. 
  
  
  
  
  18.     if(remainder>0)//是否还需要进位 
    19. 
  
  
  
  
  19.     { 
    20. 
  
  
  
  
  20.         sb.append(remainder); 
    21. 
  
  
  
  
  21.     } 
    22. 
  
  
  
  
  22.     //反装即为结果 
    23. 
  
  
  
  
  23.     return sb.reverse().toString(); 
    24. 
  
  
  
  
  24. } 
    25.

大数减法

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

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

减法转成大-小

1、执行计算前首先比较减数(num1)和被减数(num2)的大小，如果num1>num2,那么就模拟num1-num2的过程，如果num1

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

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

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

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

一个减法大概流程

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

 
 
 
 
    
  
  
  
  
  1. public static boolean compare(String num1,String num2) 
    2. 
  
  
  
  
  2. { 
    3. 
  
  
  
  
  3.     if(num1.length()
  
  
  
  
  4.         return  false; 
    5. 
  
  
  
  
  5.     else if(num1.length()>num2.length()) 
    6. 
  
  
  
  
  6.         return true; 
    7. 
  
  
  
  
  7.     else 
    8. 
  
  
  
  
  8.         return num1.compareTo(num2)>0; 
    9. 
  
  
  
  
  9. } 
    10. 
  
  
  
  
  10. public static  String subtractString(String num1,String num2) { 
    11. 
  
  
  
  
  11.     char sign='+';//正负号 
    12. 
  
  
  
  
  12.     //让num1>num2 如果num1
  
  
  
  
  13.     //可以先将num1和num2交换和前面情况统一 
    14. 
  
  
  
  
  14.     if(!compare(num1,num2)) 
    15. 
  
  
  
  
  15.     { 
    16. 
  
  
  
  
  16.         sign='-'; 
    17. 
  
  
  
  
  17.         String team = num2; 
    18. 
  
  
  
  
  18.         num2 = num1; 
    19. 
  
  
  
  
  19.         num1 = team; 
    20. 
  
  
  
  
  20.     } 
    21. 
  
  
  
  
  21.     int len1=num1.length()-1; 
    22. 
  
  
  
  
  22.     int len2=num2.length()-1; 
    23. 
  
  
  
  
  23.  
    24. 
  
  
  
  
  24.     char ch1[] = num1.toCharArray(); 
    25. 
  
  
  
  
  25.     char ch2[] = num2.toCharArray(); 
    26. 
  
  
  
  
  26.     StringBuilder sb=new StringBuilder(); 
    27. 
  
  
  
  
  27.     int borrow=0;//借位 
    28. 
  
  
  
  
  28.     while (len1>=0||len2>=0) 
    29. 
  
  
  
  
  29.     { 
    30. 
  
  
  
  
  30.         int n1=len1>=0?(ch1[len1--]-'0'):0; 
    31. 
  
  
  
  
  31.         int n2=len2>=0?(ch2[len2--]-'0'):0; 
    32. 
  
  
  
  
  32.  
    33. 
  
  
  
  
  33.         int num=n1-n2-borrow; 
    34. 
  
  
  
  
  34.         borrow=0; 
    35. 
  
  
  
  
  35.         if(num<0)//需要向前借位 
    36. 
  
  
  
  
  36.         { 
    37. 
  
  
  
  
  37.             borrow=1; 
    38. 
  
  
  
  
  38.             num+=10; 
    39. 
  
  
  
  
  39.         } 
    40. 
  
  
  
  
  40.         sb.append(num); 
    41. 
  
  
  
  
  41.     } 
    42. 
  
  
  
  
  42.  
    43. 
  
  
  
  
  43.     sb=sb.reverse();//需要先翻转 
    44. 
  
  
  
  
  44.     int index = 0;//去掉前面没用的’0‘ 
    45. 
  
  
  
  
  45.     while (index
  
  
  
  
  46.     { 
    47. 
  
  
  
  
  47.         index++; 
    48. 
  
  
  
  
  48.     } 
    49. 
  
  
  
  
  49.     //如果两个数相同 直接返回"0" 
    50. 
  
  
  
  
  50.     if(index==sb.length()) 
    51. 
  
  
  
  
  51.         return "0"; 
    52. 
  
  
  
  
  52.     if(sign=='+')//如果正数  
    53. 
  
  
  
  
  53.         return  sb.substring(index); 
    54. 
  
  
  
  
  54.     else  return sign+sb.substring(index);//负数需要返回 
    55. 
  
  
  
  
  55. } 
    56.

 大数乘法

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

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

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

先计算后进位

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

一个乘法流程

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

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

这题有力扣对应题可以去试试【43字符串相乘】，具体代码为：

 
 
 
 
    
  
  
  
  
  1. public String multiply(String num1, String num2) { 
    2. 
  
  
  
  
  2.     if("0".equals(num1)||"0".equals(num2))return "0"; 
    3. 
  
  
  
  
  3.     char a[]=num1.toCharArray(); 
    4. 
  
  
  
  
  4.     char b[]=num2.toCharArray(); 
    5. 
  
  
  
  
  5.  
    6. 
  
  
  
  
  6.     int value[]=new int[a.length+b.length]; 
    7. 
  
  
  
  
  7.  
    8. 
  
  
  
  
  8.     for(int i=a.length-1;i>=0;i--) 
    9. 
  
  
  
  
  9.     { 
    10. 
  
  
  
  
  10.         for(int j=b.length-1;j>=0;j--) 
    11. 
  
  
  
  
  11.         { 
    12. 
  
  
  
  
  12.             int index=a.length-1-i+b.length-1-j; 
    13. 
  
  
  
  
  13.             value[index]+=(a[i]-'0')*(b[j]-'0'); 
    14. 
  
  
  
  
  14.         } 
    15. 
  
  
  
  
  15.     } 
    16. 
  
  
  
  
  16.     for(int i=0;i
  
  
  
  
  17.     { 
    18. 
  
  
  
  
  18.         value[i+1]+=value[i]/10; 
    19. 
  
  
  
  
  19.         value[i]=value[i]%10; 
    20. 
  
  
  
  
  20.     } 
    21. 
  
  
  
  
  21.     int index=value.length-1; 
    22. 
  
  
  
  
  22.     while(value[index]==0) 
    23. 
  
  
  
  
  23.     {index--;} 
    24. 
  
  
  
  
  24.     StringBuilder sBuilder=new StringBuilder(); 
    25. 
  
  
  
  
  25.     while (index>=0) { 
    26. 
  
  
  
  
  26.         sBuilder.append(value[index--]); 
    27. 
  
  
  
  
  27.     } 
    28. 
  
  
  
  
  28.     return sBuilder.toString(); 
    29. 
  
  
  
  
  29. } 
    30.

大数除法

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

并不是，对于大数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的总词数，将结果要以字符串方式保留，后面一直迭代到最后为止,这虽然是一道除法运算的题，但是也蕴含减法和加法(次数叠加到结果中)。

计算思想

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

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

结语

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

分享名称：大数加减乘除，一文彻底搞定
本文链接：http://www.shufengxianlan.com/qtweb/news42/453892.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

响应式网站知识

分类信息网

成都app开发　　 　绵阳服务器托管　　 　成都网站安全运维　　 　网站推广营销　　 　成都企业网站设计　　 　古蔺网站建设　　 　边坡防护网　　 　成都网站建设　　 　网站优化排名　　 　成都网络推广公司　　 　邛崃做网站　　 　造型师设计　　 　成都模版网站建设　　 　雕琢时光茶叶　　 　成都恒翔机电维修　　 　微信开发　　 　IDC机房托管　　 　响应式网站　　 　免备案虚拟主机　　 　江安网站建设