两个大数相加（面试题）

小鱼儿 2021-12-13 03:03 293阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODIwMTkzNg_size_16_color_FFFFFF_t_70][]

两个大数相加。  
1、是整数；  
2、两个数无限大，long都装不下；  
3、不能用BigInteger；  
4、不能用任何包装类提供的运算方法；  
5、两个数都是以字符串的方式提供。

两个字符串的数字，怎么相加？  
其实也简单，核心点考的是ASCII码和相加进位的问题。

比喻字符类型的'9'怎么转换成int的9？  
'9' - '0' = 9。这个算法能理解吗？  
char类型进行算数运算时是不是自动转换为int类型的了？  
字符9的ASCII值是不是比字符0的多9个？这是第一个关键点。  
第二个关键点是，注意相加时的进位。

对两个字符串的数字，可以使用字符数组的方式处理，也可以用StringBuffer。  
有人会问，StringBuffer每次append都是在后面追加，但是处理数字进位时需要在前面处理。  
其实StringBuffer有个方法reverse()，翻转字符串

举个例子比喻下整个处理过程：  
String str1 = "123459";  
string str2 = "123";  
两个字符串需要翻转，为什么？  
因为相加处理是从最右边的个位开始的，还有进位处理。  
调用reverse()方法处理后：  
String str1 = "954321";  
string str2 = "321";  
现在就好办了，个位对齐了。可以开始相加了，注意进位。  
int carry = 0;  
计算个位：  
int value = str1.charAt(0) + str2.charAt(0) - 2\*'0' + carry;  
上面这行代码能理解吗？  
翻译过来就是：'9' + '3' - 2\*'0' + carry;  
为什么 - 2\*'0' ？  
字符进行算术运算时，会转换成ASCII值在进行运算。  
故继续翻译为：57 + 51 - 2\*48 + 0；  
是不是等于 9 + 3 + 0 ?  
好，不多废话了。相加后的值为12。  
直接把12存储在个位上吗？当然不是，把进位的10部分存储到carry变量中，便于进行十位数字相加时使用：  
carry = 12 / 10;  
value = 12 % 10;  
然后把value的值保存到最终的个位上。

一次上述步骤。

最后需要注意的是，输入的两个字符串数字长度不一定相等。  
第一次循环时要以较短的字符串未结束点，计算两个数字和carry的相加和进位。  
然后在基于较长的字符串长出的部分循环，与carry相加，处理进位。

上面都把核心点说了，直接来撸代码吧，有注释的：

/**
     *@Author:759057893@qq.com Lyz
     *@Date: 2019/7/13 10:06
     *@Description:
     **/
    public class twoAdd {
        public static void main(String[] args) {
            String str1 ="123456789";
            String str2 ="528468";
            String s = add(str1,str2);
            System.out.println(s);
        }
    
        public static String add(String str1,String str2){
            //任何一个字符串为null或者空字符串，都不需要相加啦
            if(str1==null||"".equals(str1)){
                return  str2;
            }
            if(str2==null||"".equals(str2)){
                return  str1;
            }
            int maxLength = Math.max(str1.length(),str2.length());
            //定义一个存储结果的字符串，长度要比最大长度的字符串还要长一位，用于存储可能出现的进位
            StringBuffer result = new StringBuffer(maxLength+1);
            //翻转两个字符串
            str1 =new StringBuffer(str1).reverse().toString();
            str2 =new StringBuffer(str2).reverse().toString();
    
            int minLength = Math.min(str1.length(),str2.length());
            //当前数
            int currentNum = 0;
            //进位
            int carry = 0;
            int i =0;
            for(;i<minLength;i++){
                //分别获取两个字符对应的字面数值，然后相加，再加上进位
                currentNum = str1.charAt(i)+str2.charAt(i)-2*'0'+carry;
                //获取进位
                carry = currentNum/10;
                //处理当前位的最终值
                currentNum = currentNum%10;
                //保存当前位的值到最终的字符缓冲区中
                result.append(String.valueOf(currentNum));
            }
            if(str1.length()<str2.length()){
                //选择
                str1 =str2;
            }
            for(;i<str1.length();i++){
                //分别获取两个字符对应的字面数值，然后相加，再加上进位
                currentNum = str1.charAt(i)-'0'+carry;
                //获取进位
                carry = currentNum/10;
                //处理当前位的最终值
                currentNum%=10;
                //保存当前位的值到最终的字符缓冲区中
                result.append(String.valueOf(currentNum));
            }
            //处理最后一个的进位(当循环结束后，是不是还可能会有一个进位)
            if(carry>0){
                result.append(String.valueOf(carry));
            }
            //最后翻转恢复字符串，再返回
            return  result.reverse().toString();
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODIwMTkzNg_size_16_color_FFFFFF_t_70]: /images/20211210/a6c325cac2b84685b117df35a67c6f2c.png