如何實(shí)現(xiàn)大整數(shù)相加
摘自漫畫算法：
題目：給出兩個(gè)很大的整數(shù)，要求實(shí)現(xiàn)程序求出兩個(gè)整數(shù)之和玄糟。
注意：很多人第一想法就是直接用long存儲(chǔ)勿她，在程序里相加不就行了；但是如果這兩個(gè)整數(shù)大得連long類型都裝不下呢阵翎？比如兩個(gè)100位的整數(shù)逢并？
解題思路
在講解大整數(shù)相加之前，先來(lái)回顧一下小學(xué)數(shù)學(xué)課郭卫，在上小學(xué)時(shí)砍聊，我們通過(guò)列豎式計(jì)算兩個(gè)較大數(shù)目的加、減贰军、乘玻蝌、除；那么词疼，為什么需要列出豎式來(lái)運(yùn)算呢俯树？這是因?yàn)閷?duì)于這么大的整數(shù)，我們無(wú)法一步到位直接算出結(jié)果贰盗，所以不得不把計(jì)算過(guò)程拆解成一個(gè)一個(gè)子步驟许饿。其實(shí)不僅僅是人腦，對(duì)于計(jì)算機(jī)來(lái)說(shuō)也同樣如此舵盈。程序不可能通過(guò)一條指令計(jì)算出兩個(gè)大整數(shù)之和陋率，但我們卻可以把大運(yùn)算拆解成若干個(gè)小運(yùn)算球化，像小學(xué)生列豎式一樣按位計(jì)算。
如果大整數(shù)超出了long類型的范圍瓦糟，該如何來(lái)存儲(chǔ)這樣的整數(shù)呢支示？
對(duì)于這個(gè)問(wèn)題很好解決宾肺，用數(shù)組存儲(chǔ)即可。數(shù)組的每一個(gè)元素，對(duì)應(yīng)著大整數(shù)的每一個(gè)數(shù)位尖坤。
在程序中列出的”豎式“究竟是什么樣子呢持际？我們以426 709 752 318 + 95 481 253 129為例杰扫，來(lái)看看大整數(shù)相加的詳細(xì)步驟戴涝。
1、創(chuàng)建兩個(gè)整型數(shù)組斋竞，數(shù)組長(zhǎng)度是較大整數(shù)的位數(shù)+1.把每一個(gè)數(shù)組倒序存儲(chǔ)到數(shù)組中倔约，整數(shù)的個(gè)位存于數(shù)組下標(biāo)為0的位置，最高位存于數(shù)組的尾部坝初。之所以倒序存儲(chǔ)浸剩，是因?yàn)檫@樣更符合從左到右訪問(wèn)數(shù)組的習(xí)慣。
2鳄袍、創(chuàng)建結(jié)果數(shù)組绢要，結(jié)果數(shù)組的長(zhǎng)度同樣是較大整數(shù)的位數(shù)+1，+1的目的很明顯拗小，是給最高位進(jìn)位預(yù)留的重罪。
3、遍歷兩個(gè)數(shù)組哀九，從左到右按照對(duì)應(yīng)下標(biāo)把元素兩兩相加剿配，就像小學(xué)生計(jì)算豎式一樣。在本例中阅束，最先相加的是數(shù)組A的第1個(gè)元素8和數(shù)組B的第1個(gè)元素9呼胚，結(jié)果是7，進(jìn)位1息裸。把7填充到result數(shù)組的對(duì)應(yīng)下標(biāo)位置蝇更，進(jìn)位的1填充到下一個(gè)位置。
第2組相加的是數(shù)組A的第2個(gè)元素1和數(shù)組B的第2個(gè)元素2呼盆，結(jié)果3年扩，再加上剛才的進(jìn)位1，把4填充到result數(shù)組的對(duì)應(yīng)下標(biāo)位置宿亡。
第3組相加的是數(shù)組A的第3個(gè)元素3和數(shù)組B的第3個(gè)元素1常遂，結(jié)果是4，把4填充到result數(shù)組的對(duì)應(yīng)下標(biāo)位置挽荠。
第4組相加的是數(shù)組A的第4個(gè)元素2和數(shù)組B的第4個(gè)元素3克胳，結(jié)果是5，把5填充到result數(shù)組的對(duì)應(yīng)下標(biāo)位置圈匆。
以此類推漠另，一直把數(shù)組的所有元素都相加完畢。
4跃赚、把result數(shù)組的全部元素再次逆序笆搓，去掉首位0，就是最終結(jié)果纬傲。
需要說(shuō)明的是满败，為兩個(gè)大整數(shù)建立臨時(shí)數(shù)組，是一種直觀的解決方案叹括。若想節(jié)省內(nèi)存空間算墨，也可以不創(chuàng)建這兩個(gè)臨時(shí)數(shù)組。
代碼實(shí)現(xiàn)
/**
* 描述：實(shí)現(xiàn)大整數(shù)相加汁雷。
* <p>
* Create By ZhangBiao
* 2020/6/9
*/
public class BigNumberSum {
/**
* 大整數(shù)求和
*
* @param bigNumberA 大整數(shù)A
* @param bigNumberB 大整數(shù)B
* @return
*/
public static String bigNumberSum(String bigNumberA, String bigNumberB) {
// 1净嘀、把兩個(gè)大整數(shù)用數(shù)組逆序存儲(chǔ)，數(shù)組長(zhǎng)度等于較大整數(shù)位數(shù)+1
int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() :
bigNumberB.length();
int[] arrayA = new int[maxLength + 1];
for (int i = 0; i < bigNumberA.length(); i++) {
arrayA[i] = bigNumberA.charAt(bigNumberA.length() - 1 - i) - '0';
}
int[] arrayB = new int[maxLength + 1];
for (int i = 0; i < bigNumberB.length(); i++) {
arrayB[i] = bigNumberB.charAt(bigNumberB.length() - 1 - i) - '0';
}
// 2侠讯、構(gòu)建result數(shù)組挖藏，數(shù)組長(zhǎng)度等于較大整數(shù)位+1
int[] result = new int[maxLength + 1];
// 3、遍歷數(shù)組厢漩，按位相加
for (int i = 0; i < result.length; i++) {
int temp = result[i];
temp += arrayA[i];
temp += arrayB[i];
// 判斷是否進(jìn)位
if (temp >= 10) {
temp = temp - 10;
result[i + 1] = 1;
}
result[i] = temp;
}
// 4膜眠、把result數(shù)組再次逆序并轉(zhuǎn)成String
StringBuilder sb = new StringBuilder();
// 是否找到大整數(shù)的最高有效位
boolean findFirst = false;
for (int i = result.length - 1; i >= 0; i--) {
if (!findFirst) {
if (result[i] == 0) {
continue;
}
findFirst = true;
}
sb.append(result[i]);
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(bigNumberSum("426709752318", "95481253129"));
}
}
上述代碼中，如果給出的大整數(shù)的最長(zhǎng)位數(shù)是n溜嗜，那么創(chuàng)建數(shù)組柴底。按位運(yùn)算、結(jié)果逆序的時(shí)間復(fù)雜度各自都是O(n)粱胜，整體的時(shí)間復(fù)雜度也是O(n)柄驻。不過(guò)當(dāng)前的思路其實(shí)還存在一個(gè)可優(yōu)化的地方。
優(yōu)化方案
我們之前是把大整數(shù)按照數(shù)位來(lái)拆分的焙压，即如果較大整數(shù)有50位鸿脓，那么我們就需要?jiǎng)?chuàng)建一個(gè)長(zhǎng)度為51的數(shù)組，數(shù)組中的每個(gè)元素存儲(chǔ)其中一位數(shù)字涯曲。
那么我們真的有必要把原整數(shù)拆分得這么細(xì)嗎野哭？顯然不需要，只需要拆分到可以被直接計(jì)算的程序就夠了幻件。
int類型的取值范圍是 -2 147 483 648 ~ 2 147 483 647拨黔，最多可以有10位整數(shù)。為了防止溢出绰沥，我們可以把大整數(shù)的每9位作為數(shù)組的一個(gè)元素篱蝇，進(jìn)行加法運(yùn)算贺待。（這里也可以使用long類型來(lái)拆分，按照int類型拆分僅僅是提供一個(gè)思路）零截。
如此一來(lái)麸塞，內(nèi)存占用空間和運(yùn)算次數(shù)，都?jí)嚎s到了原來(lái)的1/9涧衙。
