大整數算法系列（三）：比較操作實現與有符號數大小判斷邏輯

多精度整數比較：從絕對值到有符號的完整實現

大整數（Bignum）比較是高精度運算庫的基石，廣泛用於排序、搜尋、密碼學演算法（如 RSA 模指數運算中的模比較）。本文詳細解析三種比較模式的演算法邏輯與 C 實現。

設計約定

• 回傳值：1 (x > y)、0 (x == y)、-1 (x < y)
• 資料結構：bignum 採用 2^32 進制（32 位系統），dp 陣列低位在前（LSB first），used 記錄有效數位數，sign 為 1 (非負) 或 -1 (負數)

1. 絕對值比較 bn_cmp_abs

核心邏輯：先比位數，位數多者較大；位數相同則從最高位向低位逐位比較。

int bn_cmp_abs(const bignum *x, const bignum *y) {
    size_t i;
    if (x->used > y->used) return 1;
    if (x->used < y->used) return -1;
    // 位數相同，從最高位遞減比較
    for (i = x->used; i > 0; i--) {
        if (x->dp[i-1] > y->dp[i-1]) return 1;
        if (x->dp[i-1] < y->dp[i-1]) return -1;
    }
    return 0;
}

時間複雜度：O(n)，n 為數位數。

2. 有符號比較 bn_cmp_bn

利用數學性質化簡：

• 異號：非負 > 負數
• 同號且非負：直接比較絕對值
• 同號且負數：反向比較絕對值（因為 -5 > -10，但 |-5| < |-10|）

int bn_cmp_bn(const bignum *x, const bignum *y) {
    if (x->sign == 1 && y->sign == -1) return 1;
    if (y->sign == 1 && x->sign == -1) return -1;
    if (x->sign == 1) return bn_cmp_abs(x, y); // 同為非負
    return bn_cmp_abs(y, x); // 同為負數，反向比較
}

3. 多精度與單精度比較 bn_cmp_int

將單精度整數 bn_sint y 臨時封裝為 bignum，複用 bn_cmp_bn。雖有微小效能損失，但大幅減少代碼重複。

int bn_cmp_int(const bignum *x, const bn_sint y) {
    bignum t[1];
    bn_digit p[1];
    p[0] = (y >= 0) ? y : -y; // 絕對值
    t->sign = (y >= 0) ? 1 : -1;
    t->used = (y == 0) ? 0 : 1; // 0 特殊處理：used=0
    t->alloc = 1;
    t->dp = p;
    return bn_cmp_bn(x, t);
}

關鍵細節與避坑指南

1. used = 0 代表數值 0，比較時需優先處理
2. 負數比較時交換參數順序而非取反回傳值，避免邏輯錯誤
3. 單精度轉換時注意 bn_sint 可能為最小負數（如 INT_MIN），取絕對值會溢位，建議用無符號型別中繼
4. 所有比較函數應標記 const 參數，確保不修改輸入

效能優化方向

• 針對常見情況（如比較小整數）加入快速路徑
• 使用編譯器內建函數（__builtin_clz 等）加速最高有效位定位
• SIMD 指令並行比較多個數位（需對齊記憶體）

比較操作看似簡單，實則是後續加減乘除、模運算、Montgomery 乘法等高階演算法的前置依賴。下一篇將介紹位操作：get_bit、set_bit、msb/lsb 計算等位元級運算。