大整數算法系列（五）：移位操作完整實現——從整數位移到任意位元移位的算術邏輯

算術移位：大整數乘除 2 的高效原語

移位是大整數庫中最高頻的底層操作：左移 = 乘 2ⁿ，右移 = 除 2ⁿ。本文詳細解析算術移位（保留符號、精度自動擴展）與邏輯移位的差異，並給出四種移位原語的完整 C 實現與複雜度分析。

邏輯移位 vs 算術移位

大整數採用絕對值 + 符號位表示 (非補碼)，因此：

• 左移：精度可能增加 (最高位進位產生新數位)，低位補 0
• 右移：精度減少 (低位捨棄)，高位補 0，**符號位獨立維護不變**

1. 整數位移：bn_lshd (左移) / bn_rshd (右移)

以 b = 32 位為單位移動陣列元素，等價乘除 2^32b。

// 左移 b 個數位
int bn_lshd(bignum *x, size_t b) {
    x->used += b;
    BN_CHECK(bn_grow(x, x->used));
    bn_digit *top = x->dp + x->used - 1;
    bn_digit *bottom = x->dp + x->used - b - 1;
    for (size_t i = x->used; i > b; i--) *top-- = *bottom--; // 高位向上搬移
    for (size_t i = 0; i < b; i++) *x->dp++ = 0; // 低位清零
    return 0;
}

// 右移 b 個數位
int bn_rshd(bignum *x, size_t b) {
    if (x->used <= b) return bn_set_word(x, 0); // 全部移出 = 0
    bn_digit *bottom = x->dp;
    bn_digit *top = x->dp + b;
    for (size_t i = 0; i < x->used - b; i++) *bottom++ = *top++; // 低位向下搬移
    for (size_t i = x->used - b; i < x->used; i++) *bottom++ = 0; // 高位清零
    x->used -= b;
    return 0;
}

2. 單位元移位：bn_lshift_1 / bn_rshift_1

核心技巧：跨數位進位/借位傳遞。以左移為例，每個數位左移 1 位，其最高位 (bit 31) 成為下一數位的最低位進位。

// 左移 1 位：y = x << 1
int bn_lshift_1(bignum *y, const bignum *x) {
    BN_CHECK(bn_grow(y, x->used + 1)); // 預留可能進位
    size_t shift = biL - 1; // 31 (32位系統)
    bn_digit r = 0, rr;
    for (size_t i = 0; i < x->used; i++) {
        rr = x->dp[i] >> shift; // 取出最高位
        y->dp[i] = (x->dp[i] << 1) | r; // 左移並合併前一進位
        r = rr; // 當前最高位成為下一輪進位
    }
    if (r) y->dp[y->used++] = 1; // 最終進位產生新數位
    y->sign = x->sign;
    bn_clamp(y);
    return 0;
}

// 右移 1 位：y = x >> 1
int bn_rshift_1(bignum *y, const bignum *x) {
    BN_CHECK(bn_grow(y, x->used));
    size_t shift = biL - 1;
    bn_digit r = 0, rr;
    for (int i = x->used - 1; i >= 0; i--) {
        rr = x->dp[i] & 1; // 取出最低位
        y->dp[i] = (x->dp[i] >> 1) | (r << shift); // 右移並合併前一借位
        r = rr;
    }
    y->sign = x->sign;
    bn_clamp(y); // 修正 used，去除高位前導零
    return 0;
}

3. 任意位元移位：bn_lshift / bn_rshift (通用版)

分解為：整數位移 + 餘數位元移位。

// 左移 count 位
int bn_lshift(bignum *y, const bignum *x, size_t count) {
    if (y != x) BN_CHECK(bn_copy(y, x));
    BN_CHECK(bn_grow(y, y->used + count/biL + 1));
    if (count >= biL) BN_CHECK(bn_lshd(y, count/biL));
    size_t d = count & (biL - 1); // 餘數位元
    if (d) {
        size_t shift = biL - d;
        bn_digit r = 0, rr;
        for (size_t i = 0; i < y->used; i++) {
            rr = y->dp[i] >> shift;
            y->dp[i] = (y->dp[i] << d) | r;
            r = rr;
        }
        if (r) y->dp[y->used++] = r;
    }
    return 0;
}

// 右移 count 位
int bn_rshift(bignum *y, const bignum *x, size_t count) {
    if (y != x) BN_CHECK(bn_copy(y, x));
    if (count >= biL) BN_CHECK(bn_rshd(y, count/biL));
    size_t d = count & (biL - 1);
    if (d) {
        size_t shift = biL - d;
        bn_digit r = 0, rr;
        for (int i = y->used - 1; i >= 0; i--) {
            rr = y->dp[i] & ((1 << d) - 1); // 取出低 d 位
            y->dp[i] = (y->dp[i] >> d) | (r << shift);
            r = rr;
        }
    }
    bn_clamp(y);
    return 0;
}

複雜度分析與優化

• 時間複雜度：O(n)，n 為數位數，單層迴圈
• 空間複雜度：O(1) 額外空間 (就地操作)
• 優化方向：
  • 編譯器內建：__builtin_clz/ctz 快速定位邊界
  • SIMD：VPALIGNR (位元組對齊移位) + VPSLLD/VPSRLD 並行處理 4×64-bit
  • 就地操作避免 bn_copy 開銷

應用場景

1. 快速乘除 2 的冪次：RSA 模指數運算中的平方步驟
2. Montgomery 約減：右移實現除以 R=2^k
3. 位掃描：bn_msb/bn_lsb 配合移位快速試除
4. 編碼/解碼：DER/PEM 格式轉換、Base64 編碼

移位操作是大整數庫的「加速器」，正確處理跨數位進位、精度動態調整、符號位保持，能為上層乘法、模運算、素數測試奠定穩固效能基礎。下一篇將介紹絕對值加法：多精度加法的核心迴圈、雙精度暫存器技巧、進位傳遞優化。