唉,作为一个重度拖延症患者,我差不多已经没救了。好了,说正题。前几天无意中看到一道题,想起来自己去面试的时候也遇到过,所以就想把自己的解法写出来和大家交流一下,但是当时写完代码后,就去干别的事了,所有把这个就耽搁了,今天想起来了,那就写一下吧。
题目:两个 500 位的大数相加,不使用 BigDecimal
题目大概就是这样,相信很多人都见过类似的题目。现在说一下我的思路:500 位,早已经超过了 Java 基本数据类型的承载范围,而且不能使用 BigDecimal,那么就意味着无法直接把这两个数相加。我的思路很简单,就是从个位开始,逐位相加,然后记录进位,加到相邻的高位,就这样,简单的加法,只要循环就可以完成大数相加。
我将题目稍微改变了一下,即不特意限定位数相同,以便适用于所有超过基本类型范围的大数相加。为了便于输入,我选择了使用 String 来承载数据,在此也不特意判断输入是否是有效,是否是数字。好了,废话不多说,直接贴代码。
- public class BigDigitalSum {
- public static String sumByBit(String str1, String str2) {
- if (str1.length() > str2.length()) {
- int diff = str1.length() - str2.length();
- str2 = fillZero(str2, diff); //这里我加了一个fillzero方法,以补齐长度,使两字符串(数字)长度相等
- }
- if (str1.length() < str2.length()) {
- int diff = str2.length() - str1.length();
- str1 = fillZero(str1, diff);
- }
- char[] arr1 = str1.toCharArray();
- char[] arr2 = str2.toCharArray();
- StringBuffer result = new StringBuffer();
- int i = arr1.length - 1; //循环初始值,即数字的个位
- int carryFlag = 0; // 进位标识
- int c0 = '0'; // '0'的ASCII值
- while (i >= 0) {
- int temp = arr1[i] + arr2[i] - 2 * c0 + carryFlag; //一定要加上低位的进位
- carryFlag = 0; //每次循环把进位标志清0
- if (temp >= 10) {
- temp -= 10;
- carryFlag = 1;
- }
- result.insert(0, temp); //因为用StringBuffer承载结果,所以可以把每次的运算结果插入到最前面。也可以往后append,最后把字符串反转就可以得到正确结果
- i--;
- }
- //循环结束后,两数最高位之和如果还有进位,则一定要记得把这个进位写到结果的最高位
- if (carryFlag == 1) {
- result.insert(0, "1");
- }
- return result.toString();
- }
- /*
- * 该方法往位数少的数的高位补0,使两数位数相同
- */
- private static String fillZero(String str, int diff) {
- StringBuffer sb = new StringBuffer(str);
- StringBuffer zeros = new StringBuffer();
- for (int i = 0; i < diff; i++) {
- zeros.insert(0, "0");
- }
- sb.insert(0, zeros);
- return sb.toString();
- }
- }
ok,这就是我对这道题的解法,在这里再给大家提供一种思路,即把数字分割成基本类型可以承载的长度,比如每 10 位一组,然后对应的每组数字相加,记下进位,加到高位的那一组中,最后拼接起来。抛砖引玉,不知大家是怎么解这道题的,希望有更好解法的小伙伴能说出来大家参考下。
来源: http://www.cnblogs.com/LZHua/p/5914435.html