C 語言循環左移：位運算實現與可移植性詳解

函數功能

實現無符號整數的循環左移（Rotate Left）：高位移出的位補到低位。例如 rotate_l(0x80000000, 4) 將最高位 1 移至第 4 位。

代碼逐行解析

int rotate_l(unsigned int number, unsigned int bit) {
    unsigned int i;
    unsigned int high = 8 * sizeof(unsigned int);  // 1. 計算總位數（可移植關鍵）
    // 例如 32 位系統：8*4=32；16 位系統：8*2=16

    for (i = 0; i < bit; i++) {                    // 2. 循環 bit 次，每次左移 1 位
        if (number & (1u << (high - 1))) {         // 3. 檢查最高位是否為 1
            // 最高位為 1：左移 1 位，最低位補 0，再與 1 或運算 → 最低位變 1
            number = (number << 1) | 1;
        } else {
            // 最高位為 0：直接左移 1 位，最低位自動補 0
            number = number << 1;
        }
    }
    return number;
}

關鍵技術點

1. sizeof(unsigned int) 保證可移植性：不同平台 int 位寬不同（16/32/64 位），動態計算避免硬編碼 32。
2. 1u << (high - 1) 構造最高位掩碼：1u 確保無符號運算，避免符號擴展陷阱。
3. 位運算組合實現循環：
   • number << 1：邏輯左移，高位丟棄，低位補 0。
   • | 1：將最低位強制置 1，完成「高位移到低位」。

優化建議

// 提取掩碼計算出循環外，避免重複計算
unsigned int mask = 1u << (high - 1);
for (i = 0; i < bit; i++) {
    if (number & mask) number = (number << 1) | 1;
    else number = number << 1;
}

進階：無循環版本（O(1)）

unsigned int rotate_l_fast(unsigned int x, unsigned int n) {
    unsigned int bits = 8 * sizeof(unsigned int);
    n %= bits;                              // 處理 n > bits 情況
    return (x << n) | (x >> (bits - n));   // 高位移出部分由右移補回
}

利用「左移丟棄的高位 = 右移得到的低位」原理，單指令完成，效率極高（編譯器常優化為單條 ROL 指令）。

常見陷阱

• 移位量超過位寬：C 標準規定移位量 >= 位寬屬未定義行為，必須取模。
• 符號擴展：對有符號數右移可能產生算術右移（符號位複製），循環移位必須用無符號類型。
• bit == 0：循環不執行，直接返回原值，符合預期。

掌握位運算精髓，寫出高效、可移植的系統級代碼。