轉(zhuǎn)載自??漫畫：如何實(shí)現(xiàn)大整數(shù)相加

?

?

?

?

在程序中列出的 “豎式” 究竟是什么樣子呢？我們以 426709752318 +?95481253129 為例，來(lái)看看大整數(shù)相加的詳細(xì)步驟：

第一步，把整數(shù)倒序存儲(chǔ)，整數(shù)的個(gè)位存于數(shù)組0下標(biāo)位置，最高位存于數(shù)組長(zhǎng)度-1下標(biāo)位置。之所以倒序存儲(chǔ)，更加符合我們從左到右訪問(wèn)數(shù)組的習(xí)慣。

?

第二步，創(chuàng)建結(jié)果數(shù)組，結(jié)果數(shù)組的最大長(zhǎng)度是較大整數(shù)的位數(shù)+1，原因很明顯。

?

第三步，遍歷兩個(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è)位置：

?

第二組相加的是數(shù)組A的第2個(gè)元素1和數(shù)組B的第2個(gè)元素2，結(jié)果是3，再加上剛才的進(jìn)位1，把4填充到Result數(shù)組的對(duì)應(yīng)下標(biāo)：

?

第三組相加的是數(shù)組A的第3個(gè)元素3和數(shù)組B的第3個(gè)元素1，結(jié)果是4，把4填充到Result數(shù)組的對(duì)應(yīng)下標(biāo)：

?

第四組相加的是數(shù)組A的第4個(gè)元素2和數(shù)組B的第4個(gè)元素3，結(jié)果是5，把5填充到Result數(shù)組的對(duì)應(yīng)下標(biāo)：

?

以此類推......一直把數(shù)組的所有元素都相加完畢：

?

第四步，把Result數(shù)組的全部元素再次逆序，去掉首位的，就是最終結(jié)果：

?

/** * 大整數(shù)求和 * @param bigNumberA ?大整數(shù)A * @param bigNumberB ?大整數(shù)B */ public static String bigNumberSum(String bigNumberA, String bigNumberB) {//1.把兩個(gè)大整數(shù)用數(shù)組逆序存儲(chǔ)，數(shù)組長(zhǎng)度等于較大整數(shù)位數(shù)+1int 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ù)位數(shù)+1int[] 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)成StringStringBuilder 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")); }

?

?

?

如何優(yōu)化呢？

?

我們之前是把大整數(shù)按照每一個(gè)十進(jìn)制數(shù)位來(lái)拆分，比如較大整數(shù)的長(zhǎng)度有50位，那么我們需要?jiǎng)?chuàng)建一個(gè)51位的數(shù)組，數(shù)組的每個(gè)元素存儲(chǔ)其中一位。

?

我們真的有必要把原整數(shù)拆分得那么細(xì)嗎？顯然不需要，只需要拆分到可以被直接計(jì)算的程度就夠了。

int類型的取值范圍是?-2147483648——2147483647，最多有10位整數(shù)。為了防止溢出，我們可以把大整數(shù)的每9位作為數(shù)組的一個(gè)元素，進(jìn)行加法運(yùn)算。（這里也可以使用long類型來(lái)拆分，按照int范圍拆分僅僅是提供一個(gè)思路）

?

如此一來(lái)，占用空間和運(yùn)算次數(shù)，都被壓縮了9倍。

?

?

?

總結(jié)

以上是生活随笔為你收集整理的漫画：如何实现大整数相加的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。