上一篇文章簡單講解了移位操作是如何進行的，最後簡要分析了算法時間復雜度。這次介紹絕對值加法，這個算法是構建有符號數加法減法的重要模塊之一。絕對值計算的算法是高度優化的，本身的時間復雜度為 O(n)，但是如果被高級的算法調用，其復雜度很容易被提高到 O(n^2) 甚至 O(n^3)。絕對值加法只計算兩個大整數的絕對值之和：z = |x| + |y|，之所以要先解決絕對值的計算，是因為有符號的加法或減法都可以先通過計算絕對值的和或差，然後再修改符號位來實現。
★ 計算原理
大整數的絕對值加法和小學數學的筆算加法沒有什麼區別，只是進制不同而已。核心操作是：從低位到高位將相同的數位進行相加，進位傳遞到下一位。所有操作累加和進位操作完成後，將結果的高位清零，並且將符號位 sign 設置為 1 （絕對值相加，結果必為非負整數）。
★ 實現
下面給出絕對值加法的實現代碼。需要注意的是，這個算法裡面使用了好幾個宏定義，而且都是位於關鍵的操作之上，之所以這樣，是因為在某些環境下，基本的數據類型有單精度類型和雙精度類型，而在另一些環境下，只有單精度類型。例如 32 位系統下，有 32 位的單精度整形和 64 位的雙精度整形；而在 64 位系統下，只有 64 位的單精度整形，沒有 128 位的雙精度整形。在不同的環境下，其核心操作是略有不同的。使用宏定義，可以方便地在不同環境之間進行切換。後面會詳細講這些宏定義的工作原理。
int bn_add_abs(bignum *z, const bignum *x, const bignum *y)
{
int ret;
const bignum *tmp;
bn_digit *px, *py, *pz;
size_t i, max, min, olduse;
ADDC_INIT
if(x->used > y->used)
{
max = x->used;
min = y->used;
tmp = x;
}
else
{
max = y->used;
min = x->used;
tmp = y;
}
olduse = z->used;
z->used = max + 1;
BN_CHECK(bn_grow(z, z->used));
px = x->dp;
py = y->dp;
pz = z->dp;
for(i = 0; i < min; i++)
{
ADDC_CORE
px++;
py++;
pz++;
}
if(min != max)
{
for(; i < max; i++)
{
ADDC_FINAL
pz++;
}
}
ADDC_STOP
for(i = z->used; i < olduse; i++)
*pz++ = 0;
z->sign = 1;
bn_clamp(z);
clean:
return ret;
}
算法第一步是找出數位較大的正數，並且讓指針 tmp 指向它。第二步是增加目標整數的精度，設定三個別名指針分別指向輸入整數和輸出整數的 dp 來提高內存的訪問效率。第三步是通過一個循環將位數較小的整數累加到較大的整數上，並將結果存儲到目標整數的相應數位中，然後使用一個額外的循環和 ADDC_STOP 宏定義傳遞累加產生的進位，最後將高位清零，符號位設置成 1 和壓縮多余的數位完成計算。
相關的宏定義：
#ifdef _MSC_VER #define LL(v) (v##ui64) #else #define LL(v) (v##ULL) #endif #define BN_HAVE_LONG_LONG #define BN_MASK0 LL(0xFFFFFFFFFFFFFFFF) #else #define BN_MASK0 0xFFFFFFFFUL #endif
這部分定義了相關的掩碼來提取結果的某些比特位。
#ifdef BN_HAVE_LONG_LONG #define ADDC_INIT \ bn_udbl rr = 0; \ #define ADDC_CORE \ rr += (bn_udbl)(*px) + (*py); \ *pz = (bn_digit)(rr & BN_MASK0); \ rr >>= biL; \ #define ADDC_FINAL \ rr += (bn_udbl)(tmp->dp[i]); \ *pz = (bn_digit)(rr & BN_MASK0); \ rr >>= biL; \ #define ADDC_STOP \ z->dp[max] = (bn_digit)(rr & BN_MASK0); \ #else #define ADDC_INIT \ bn_digit rr, t, c = 0; \ #define ADDC_CORE \ t = *px; \ t = (t + c) & BN_MASK0; \ c = (t < c); \ rr = (t + *py) & BN_MASK0; \ c += (rr < t); \ *pz = rr; \ #define ADDC_FINAL \ t = tmp->dp[i]; \ t = (t + c) & BN_MASK0; \ c = (t < c); \ *pz = t; \ #define ADDC_STOP \ z->dp[max] = c; \ #endif
這部分宏定義是算法的關鍵之處。首先 ADDC_INIT 指明在不同環境下有那些變量被定義，緊接著 ADDC_CORE 定義了在不同環境下的累加操作應該如何執行，然後 ADDC_FINAL 確定了該如何執行累加完成後的進位傳遞操作，最後 ADDC_STOP 用於傳遞最後一個進位。下面講講在兩個不同的環境下這幾個宏是如何執行的。
A. 單精度和雙精度變量都存在的環境：
1. ADDC_INIT 定義雙精度類型的變量 rr 用於存放累加的結果。用雙精度的原因是單精度累加後結果可能要用雙精度類型才能完整存儲，簡單的數學證明如下：
設單精度類型是一個 n 位的整形，則能表示的最大無符號整數是：2^n - 1，兩個最大整數相加，結果是：2 * (2^n - 1) = 2^(n + 1) - 2，結果超出單精度類型所能表示的范圍，因此至少需要雙精度類型才能完整表示。
2. 在 ADDC_CORE 中，先計算 x 和 y 每一位的和，並和來自低位的進位相加，結果放在 rr 中；然後將 rr 和掩碼 BN_MASK0 相與提取出本位，存放在目標整數的對應數位上；最後將變量 rr 右移 biL 位計算出進位結果。記住 rr 是雙精度的，累加結果的低半部分是本位結果，高半部分是進位結果。
3. 在 ADDC_FINAL 中，數位多的整數的剩余數位與來自低位的進位相加，然後從結果中提取本位存儲到目標整數的對應數位上，最後 rr 右移 biL 位計算新的進位值。
4. ADDC_STOP 宏將剩余的最後一個進位傳遞到結果的最高數位上。注意，這個進位可能是 0，也有可能不是 0。
B. 只有單精度的環境：
1. ADDC_INIT 宏定義了三個變量：累加的本位結果 rr， 臨時變量 t， 進位值 c。
2. 這裡的 ADDC_CORE 計算稍微復雜點。第一步，將 x 的某一位存放到臨時變量 t 中。第二步，變量 t 和來自低位的進位 c 相加，得到結果的本位值，存放於變量 t 中。這裡要注意的是所有變量都是單精度類型，如果結果大於單精度數所能表示的范圍，則會產生溢出，相當於做了一次 mod 2^n 運算，所以得到的是結果的本位值。第三步，判斷前一步是否產生了進位。在加法中，如果結果產生進位，則本位的值小於兩個加數。所以，如果有進位，則 t < c，比較的結果為 1。第四步，計算 t 和第二個整數對應數位的和，結果的本位存放於變量 rr 中。第五步，判斷是否產生進位，原理和第三步一樣。最後一步，將最終的本位結果送到目標整數的對應數位上。
3. ADDC_FINAL 用於傳遞剩余的進位，和上面的 ADDC_FINAL 原理一樣，只不過是本位和進位是用兩個變量表示而已。
4. ADDC_STOP 宏將剩余的最後一個進位傳遞到結果的最高數位上。仍然要注意，這個進位可能是 0，也有可能不是 0。
上面的內容看起來有點凌亂，如果對 C 的數據類型不是很了解，不明白溢出是怎麼回事的話，可以先去看看相關的章節惡補一下。
★ 總結
上面的代碼為了效率和移植方便，所以把關鍵的地方拆分出來單獨寫，因此看起來不是很直觀，可讀性不是很好。不過加法的原理十分簡單，只要明白其中的計算原理，仍然可以很快弄懂。下一篇文章將介紹絕對值減法。
【回到本系列目錄】
版權聲明
原創博文，轉載必須包含本聲明，保持本文完整，並以超鏈接形式注明作者Starrybird和本文原始地址：http://www.cnblogs.com/starrybird/p/4359221.html
