★ 引子
前面幾篇文章介紹了比較操作，絕對值加法和絕對值減法，現在就可以利用這幾個算法構建有符號數的加減算法。
★ 有符號數加法
int bn_add_bn(bignum *z, const bignum *x, const bignum *y)
{
int ret;
int sign;
sign = x->sign;
if(x->sign == y->sign)
{
BN_CHECK(bn_add_abs(z, x, y));
z->sign = sign;
}
else
{
if(bn_cmp_abs(x, y) >= 0)
{
BN_CHECK(bn_sub_abs(z, x, y));
z->sign = sign;
}
else
{
BN_CHECK(bn_sub_abs(z, y, x));
z->sign = -sign;
}
}
if(BN_IS_ZERO(z))
z->sign = 1;
clean:
return ret;
}
要注意的是，如果兩個數異號，但絕對值相等，則可能出現 -0 的現象（例如 x = -a， y = a），這與之前的規定不符，所以在最後加一句判斷，如果 z = 0，強制把符號位設為 1。BN_IS_ZERO 是一個宏定義：
#define BN_IS_ZERO(x) ((x->used == 0) ? 1 : 0)
★ 有符號數減法
和有符號數的加法類似，有符號數減法也分成兩種情況：
1. 兩個數異號：執行絕對值加法。結果 z 的符號由 x 決定，如果 x 為非負數，則 z 為正數；如果 x 為負數，則 z 為負數。
2. 兩個數同號：執行絕對值減法，用絕對值較大的數去減絕對值較小的數。結果 z 的符號由 x 和 y 的絕對值大小決定，如果 x 的絕對值大於或等於 y 的絕對值，則 z 和 x 同號（可能出現 -0），否則 z 與 x 異號。
int bn_sub_bn(bignum *z, const bignum *x, const bignum *y)
{
int ret;
int sign;
sign = x->sign;
if(x->sign != y->sign)
{
BN_CHECK(bn_add_abs(z, x, y));
z->sign = sign;
}
else
{
if(bn_cmp_abs(x, y) >= 0)
{
BN_CHECK(bn_sub_abs(z, x, y));
z->sign = sign;
}
else
{
BN_CHECK(bn_sub_abs(z, y, x));
z->sign = -sign;
}
}
if(BN_IS_ZERO(z))
z->sign = 1;
clean:
return ret;
}
同樣，為了避免出現 -0 的情況，在末尾添加一個對 z 是否等於 0 的判斷。
★ 單數位加法和減法
單數位算法，主要是計算一個大整數和一個單精度數的計算。這兩個算法在處理小規模數據的加減會很有用。對於單數位加法和減法，默認輸入是一個大整數和一個有符號的單精度數，結果為一個大整數。在處理上，並不是重新編寫兩個算法，而是先將單精度數賦值給一個臨時的 bignum 變量，然後利用上面的兩個有符號數算法進行計算。
1. 單數位加法：
int bn_add_int(bignum *z, const bignum *x, const bn_sint y)
{
int ret;
bignum t[1];
bn_digit p[1];
p[0] = (y >= 0) ? y : -y;
t->used = (y != 0) ? 1 : 0;
t->sign = (y >= 0) ? 1 : -1;
t->dp = p;
t->alloc = 1;
BN_CHECK(bn_add_bn(z, x, t));
clean:
return ret;
}
2. 單數位減法：
int bn_sub_int(bignum *z, const bignum *x, const bn_sint y)
{
int ret;
bignum t[1];
bn_digit p[1];
p[0] = (y >= 0) ? y : -y;
t->used = (y != 0) ? 1 : 0;
t->sign = (y >= 0) ? 1 : -1;
t->dp = p;
t->alloc = 1;
BN_CHECK(bn_sub_bn(z, x, t));
clean:
return ret;
}
★ 總結
到此位置，大整數的加減算法就講完了，實現加減法的關鍵還是分類的思想，這樣就可以把復雜的問題簡單化，然後各個擊破。後面幾篇將會著重介紹乘法的計算，乘法要比加減法復雜，而且在計算中，乘法是比較耗時間的，所以要做很多優化工作，否則後面的冪乘將會十分耗時。
【回到本系列目錄】
版權聲明
原創博文，轉載必須包含本聲明，保持本文完整，並以超鏈接形式注明作者Starrybird和本文原始地址：http://www.cnblogs.com/starrybird/p/4401863.html
