★ 引子
最近兩個星期一直在折騰，主機從 Windows 換到了 Linux，工作環境從實體機轉移到虛擬機中。當然目的只有一個，那就是充分發揮 Linux 和虛擬機的優勢來提高自己的工作效率。俗話說得好：磨刀不誤砍柴工，花費一些時間來折騰升級還是有必要的，有空的話可以聊聊相關經驗，如果你想急於知道的話，推薦編程隨想的博客（博客在牆外，請自行搜索梯子）。
★ 計算原理
好了，廢話不多說。上一篇文章講了絕對值加法的實現，這次來講講絕對值減法該如何做。絕對值減法的做法仍然是筆算算法，從低位開始減，不夠的向高位借位，直到所有的數位都處理完畢。為了方便日後的有符號數加減的實現，這裡規定，算法計算 z = x - y，並且 x 的絕對值大於或等於 y，否則算法返回負數錯誤。
★ 實現
因為原理比較簡單，所以我就先把代碼貼出來，然後在介紹他的工作方式。
int bn_sub_abs(bignum *z, const bignum *x, const bignum *y)
{
int ret;
bn_digit *px, *py, *pz;
size_t i, min, max, olduse, t1, t2, c;
max = x->used;
min = y->used;
if(bn_cmp_abs(x, y) < 0)
return BN_NEGATIVE_VALUE_ERROR;
olduse = z->used;
z->used = max;
BN_CHECK(bn_grow(z, z->used));
c = 0;
px = x->dp;
py = y->dp;
pz = z->dp;
for(i = 0; i < min; i++)
{
t1 = *px++;
t2 = *py++;
*pz++ = t1 - t2 - c;
if(t1 != t2) c = (t1 < t2);
}
for(; i < max; i++)
{
t1 = *px++;
*pz++ = t1 - c;
if(c != 0 && t1 != 0) c = 0;
}
for(i = max; i < olduse; i++)
*pz++ = 0;
z->sign = 1;
bn_clamp(z);
clean:
return ret;
}
絕對值減法中，對輸入進行排序並不重要，因為前面已經規定 |x| >= |y|，所以直接把 x->used 給 max， y->used 給 min；t1 和 t2 是臨時變量，c 是借位。
在進行計算之前，先檢查 x 和 y 的絕對值大小，如果不滿足上面約定的條件，返回負數錯誤。
如果 x 和 y 的絕對值大小檢查沒問題，那麼計算就可以正常進行，首先把借位的值設為 0，然後設定指針別名來提高內存訪問效率。
第一個循環：對位相減。分別把 x 和 y 的每一個數位賦值給臨時變量 t1 和 t2，計算 t1 - t2 - c 的值，然後存放到 z 的對應數位當中，如果 c = 0，表示低位沒有向高位借位。相減完畢後，判斷本次相減是否需要向高位借位，如果原來 x 中的某一數位的值小於 y 中對應數位的值，則比較的結果為 1，c = 1。注意所有的計算都是 mod 2^n。
第二個循環：退位和賦值。如果 max > min，表明 x 的數位要比 y 多，所以還需進行退位計算。如果 c = 0，則不會有退位了，直接把 x 的剩余數位賦值給 z 的對應數位即可。如果 c = 1，則還有來自低位的借位，在完成一次退位計算後，判斷下一位是否需要退位，由於 c 的值只可能是 0 或 1，如果本次退位計算前，該數位的值大於 0，則以後的數位都不需要進行退位，故將 c 的值置為 0，否則保持退位值 1。完成退位計算後，將 x 剩余的數位給 z ，完成減法計算。
第三個循環：高位清零。如果減法計算完畢後，高位還有不為 0 的數位，必須清空，否則結果會出錯。
所有循環結束後，把符號為設為 1，因為絕對值減法的最終結果仍然是個非負整數；最後壓縮多余位完成計算。
★ 總結
減法操作相對於加法來講要簡單些，主要是不需要考慮單雙精度的問題，只要你知道筆算算法以及理解計算機下二進制的補碼運算，就不難實現。下一篇文章將根據前面建立的比較算法，絕對值加減算法構造有符號數的加減計算算法。
【回到本系列目錄】
版權聲明
原創博文，轉載必須包含本聲明，保持本文完整，並以超鏈接形式注明作者Starrybird和本文原始地址：http://www.cnblogs.com/starrybird/p/4399652.html
