阿里面试题：计算两个字符串正整数的和

前言

​ 今天朋友给我发了一个面试题，让我想起了ACM的练习题,用C语言实现大数字的加法运算得出结果。这个面试题针对于java来计算两个字符串的和，不能转成int类型计算，也不能使用包装类计算。这两个字符串都只包含0到9的数字，并且都为正数。

两个正整数相加的思路

​ 首先考虑到需要一个变量存储结果，可以用字符数组存储相加后的结果。也考虑到有进位的情况,需要预留一位，以防止进位。

两个正整数相加的实现

根据题，实现的代码：

private static String javaAdd1(String num1, String num2) {
        // 补位为0，让两个数位数相等
        while (true)
        {
            if(num1.length() == num2.length())
            {
                break;
            }else
            {
                if(num1.length() < num2.length())
                {
                    num1 = "0" + num1;
                }else
                {
                    num2 = "0" + num2;
                }
            }
        }
        //将两个数字字符分成字符串进行计算
        char[] num1Char = num1.toCharArray();
        char[] num2Char = num2.toCharArray();
        int length = num1.length();
        //准备存储结果的数组
        //预留一位，以供进位
        char[] num = new char[length+1];
        for(int i=0;i<length+1;i++)
        {
            num[i] = '0';
        }

        for(int i = length-1;i >= 0;i--) {
            char num1_i = num1Char[i];
            char num2_i = num2Char[i];
            int addResult = 0;
            int index = i+1;
            addResult = (num1_i + num2_i) - ('0' * 2);
            if(num[index] >'0')
            {
                addResult += 1;
            }
            if (addResult > 9)
            {
                //代表有进位
                num[index-1] = '1';
                addResult = addResult -10;
            }
            num[index] = (char) (addResult+'0');
        }
        // 去除前置0
        int index = 0;
        for(int i=0;i<num.length;i++)
        {
            if(num[i] == '0')
            {
                index = i+1;
            }else
            {
                break;
            }
        }
        String s = "";
        for(int i=index;i<num.length;i++)
        {
            s = s+ num[i];
        }
        return s;
    }

可以对其进行优化，优化之后：

private static String javaAdd2(String num1, String num2) {
        // 补位为0，让两个数位数相等
        int lengthNum = num1.length() - num2.length();
        StringBuilder zero = new StringBuilder();
        int abs = Math.abs(lengthNum);
        for(int i = 0;i<abs;i++)
        {
            zero.append('0');
        }
        if (lengthNum > 0) {
            num2 = zero.append(num2).toString();
        } else {
            num1 = zero.append(num1).toString();
        }
        //将两个数字字符分成字符串进行计算
        char[] num1Char = num1.toCharArray();
        char[] num2Char = num2.toCharArray();
        int length = num1.length();
        //准备存储结果的数组
        //预留一位，以供进位
        char[] num = new char[length+1];
        for(int i=0;i<length+1;i++)
        {
            num[i] = '0';
        }
        //开始计算
        for(int i = length-1;i >= 0;i--) {
            char num1_i = num1Char[i];
            char num2_i = num2Char[i];
            int addResult = 0; // 两个数字相加的结果
            int index = i+1;// 指向结果数组的索引
            addResult = (num1_i + num2_i) - ('0' * 2);
            // 如果有进位的情况下
            if(num[index] >'0')
            {
                addResult += 1;
            }
            // 如果相加的结果大于9
            if (addResult > 9)
            {
                //代表有进位
                num[index-1] = '1';
                addResult = addResult -10;
            }
            num[index] = (char) (addResult+'0');
        }
        // 去除前导0
        String s = new String(num);
        s = s.replaceAll("^(0+)", "");
        return s;
    }

最近在学汇编，汇编用一个寄存器来存储进位，那么我们也可以用一个变量来存储进位的结果。

0代表无进位，1代表有进位。

private static String javaAdd3(String num1, String num2) {
        // 补位为0，让两个数位数相等
        int lengthNum = num1.length() - num2.length();
        StringBuilder zero = new StringBuilder();
        int abs = Math.abs(lengthNum);
        for(int i = 0;i<abs;i++)
        {
            zero.append('0');
        }
        if (lengthNum > 0) {
            num2 = zero.append(num2).toString();
        } else {
            num1 = zero.append(num1).toString();
        }
        //将两个数字字符分成字符串进行计算
        char[] num1Char = num1.toCharArray();
        char[] num2Char = num2.toCharArray();
        int length = num1.length();
        //准备存储结果的数组
        //预留一位，以供进位
        char[] num = new char[length+1];
        for(int i=0;i<length+1;i++)
        {
            num[i] = '0';
        }
        int flag = 0;//进位标志符
        //开始计算
        for(int i = length-1;i >= 0;i--) {
            char num1_i = num1Char[i];
            char num2_i = num2Char[i];
            int addResult = 0; // 两个数字相加的结果
            int index = i+1;// 指向结果数组的索引
            addResult = (num1_i + num2_i) - ('0' * 2);
            // 如果有进位的情况下
            if(flag == 1)
            {
                addResult += 1;
                flag = 0;
            }
            // 如果相加的结果大于9
            if (addResult > 9)
            {
                //代表有进位
                addResult = addResult -10;
                flag = 1;
            }
            num[index] = (char) (addResult+'0');
        }
        //代表最高位有进位
        if(flag == 1)
        {
            num[0] = '1';
        }
        // 去除前导0
        String s = new String(num);
        s = s.replaceAll("^(0+)", "");
        return s;
    }

结尾

​ 这个实现也可以移植到C语言上，用来实现大数字的加法运算。