大整數算法系列（四）：位操作核心實現——Get/Set Bit、MSB/LSB 計算與位元統計

位元級操作：大整數庫的微觀基石

大整數採用 2^32（或 2^64）進制陣列儲存，位操作是實現移位、模運算、素數測試、RSA 金鑰生成等核心功能的底層原語。本文深入剖析五大關鍵位操作的數學原理與高效實現。

資料表示回顧

32 位系統下，biL = 32。大整數 x = 1134924633606254832 (0xFC00FF0F0F0F0F0) 儲存為：

• dp[0] (低位) = 4042322160 = 0xF0F0F0F0
• dp[1] (高位) = 264245232 = 0x0FC00FF0

位元索引 pos 從 0 起算（LSB=0），對應關係：

• 數位索引：offset = pos / biL（或 pos >> 5）
• 數位內偏移：mod = pos % biL（或 pos & 31）

1. 讀取指定位 bn_get_bit

boolean bn_get_bit(const bignum *x, size_t pos) {
    if (x->alloc * biL <= pos) return 0; // 超出範圍視為 0
    return (x->dp[pos / biL] >> (pos & (biL - 1))) & 1;
}

技巧：pos & (biL-1) 等價 pos % biL，位運算更快。

2. 設定指定位 bn_set_bit

分三步：擴容 → 清零目標位 → 寫入新值

int bn_set_bit(bignum *x, size_t pos, boolean value) {
    size_t offset = pos / biL;
    size_t mod = pos & (biL - 1);
    if (pos >= x->alloc * biL) {
        if (value == FALSE) return 0; // 高位預設為 0，無需擴容
        BN_CHECK(bn_grow(x, offset + 1));
    }
    x->dp[offset] &= ~((bn_digit)1 << mod); // 清零
    x->dp[offset] |= ((bn_digit)value << mod); // 寫入
    x->used = x->alloc;
    bn_clamp(x); // 修正 used，去除高位前導零
    return 0;
}

3. 最高有效位位置 bn_msb (Most Significant Bit)

回傳 floor(log2(x)) + 1，即二進制表示的總位數。

size_t bn_msb(const bignum *x) {
    size_t i = x->used - 1;
    for (size_t j = biL; j > 0; j--) {
        if (((x->dp[i] >> (j - 1)) & 1) != 0) break;
    }
    return biL * i + j;
}

用途：快速估算大小、決定乘法演算法切換閾值、模運算位數對齊。

4. 最低有效位前導零計數 bn_lsb (Least Significant Bit)

回傳最低位 1 之前的 0 的個數，即 v2(x)（2 的指數）。

size_t bn_lsb(const bignum *x) {
    for (size_t i = 0; i < x->used; i++) {
        if (x->dp[i] != 0) {
            for (size_t j = 0; j < biL; j++) {
                if (((x->dp[i] >> j) & 1) != 0) return i * biL + j;
            }
        }
    }
    return 0; // x == 0
}

應用：二進制 GCD (Stein 算法) 核心步驟、x = q * 2^r 分解、Montgomery 約減預處理。

5. 位元組大小 bn_size

size_t bn_size(const bignum *x) {
    return (bn_msb(x) + 7) >> 3; // 等價 ceil(msb/8)
}

用於序列化、網路傳輸、檔案儲存的緩衝區大小計算。

效能優化建議

• 使用編譯器內建：__builtin_clz/__builtin_ctz (GCC/Clang) 或 _BitScanForward (MSVC) 替代迴圈
• 查表法：預計算 16-bit 查表陣列，以空間換時間
• SIMD：VPMOVMSKB 等指令並行處理多數位

常見錯誤

1. 忘記 bn_clamp 導致 used 殘留舊值，後續運算讀取垃圾資料
2. pos 越界未檢查，造成緩衝區溢出
3. 符號位與數值位混淆：bignum 採用絕對值+符號位表示，非補碼，位操作只處理 dp 陣列

位操作是大整數庫的「組裝指令」，掌握其邊界條件與優化手段，能為上層演算法奠定堅實效能基礎。下一篇將介紹移位操作：邏輯/算術左移右移、任意位數移位的完整實現。