算法：两个大数相加。

た入场券 2022-02-05 07:23 176阅读 0赞

两个大数相加

听说这是个频繁出现的算法题，在某某网站是的排行很靠前。  
在找工作之前，同事提过一次，我没当回事，恰恰在我第一家面试时就碰到了。

两个大数相加。  
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相加，处理进位。

public static void main(String[] args) {
    	String str1 = "123459";
    	String str2 = "123";
    	System.out.println(add(str1, str2));//123582
    }
     
    private 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();
     
    	//反转后的结果分别为：
    	//954321
    	//321
    	int minLength = Math.min(str1.length(), str2.length());
    	//进位
    	int carry = 0;
    	//当前位上的数值
    	int currentNum = 0;
    	//循环变量
    	int i = 0;
    	for (; i < minLength; i++) {
    		//分别获取两个字符对应的字面数值，然后相加，再加上进位
    		currentNum = str1.charAt(i) + str2.charAt(i) - 2 * '0' + carry;
    		//获取进位
    		carry = currentNum / 10;
    		//处理当前位的最终值
    		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();
    }

转载：[https://blog.csdn.net/fesdgasdgasdg/article/details/80953829][https_blog.csdn.net_fesdgasdgasdg_article_details_80953829]

[https_blog.csdn.net_fesdgasdgasdg_article_details_80953829]: https://blog.csdn.net/fesdgasdgasdg/article/details/80953829