C語言實現32位整數二進制位逆序算法詳解

將一個 32 位整數的二進制位完全反轉（MSB↔LSB），是經典位運算面試題，也用於網絡字節序轉換、哈希擴散、位圖操作等場景。本文提供逐位搬移法、查表法、指令集優化三種實現，並分析時間空間權衡。

問題形式化

輸入: uint32_t x = 0x00000002  // 0000...0010
輸出: uint32_t y = 0x40000000  // 0100...0000
即: y = reverse_bits(x)

方法一：逐位搬移（通用、易懂）

uint32_t reverse_bits_loop(uint32_t x) {
    uint32_t y = 0;
    for (int i = 0; i < 32; ++i) {
        y = (y << 1) | (x & 1);  // y左移騰位，x最低位入隊
        x >>= 1;                 // x右移準備下一位
    }
    return y;
}

• 邏輯：y 作為結果累加器，每輪左移 1 位，最低位置入 x 當前 LSB
• 32 輪循環，無分支，適合編譯器自動展開/向量化
• 編譯優化 -O2 通常生成高效指令序列

方法二：分治並行反轉（無循環、O(log n) 指令）

利用掩碼並行交換相鄰位組：

uint32_t reverse_bits_parallel(uint32_t x) {
    x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1);  // 交換奇偶位
    x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2);  // 交換2位組
    x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4);  // 交換4位組 (nibble)
    x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8);  // 交換字節
    x = (x >> 16) | (x << 16);                               // 交換半字
    return x;
}

• 5 步完成，無循環分支，指令級並行度高
• 掩碼常數編譯期確定，適合寄存器分配
• 現代編譯器 -O3 可進一步合並指令

方法三：查表法（空間換時間）

// 編譯期生成 256 條目表
static const uint8_t reverse_byte[256] = {
    0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, ...
    // 可用腳本生成或 constexpr 初始化
};

uint32_t reverse_bits_lut(uint32_t x) {
    return (reverse_byte[x & 0xFF] << 24) |
           (reverse_byte[(x >> 8) & 0xFF] << 16) |
           (reverse_byte[(x >> 16) & 0xFF] << 8) |
           (reverse_byte[x >> 24]);
}

• 4 次表查找 + 移位/或運算，極快
• 256 字節表可放入 L1 緩存，適合高頻調用
• 嵌入式系統需權衡 Flash 佔用

方法四：硬件指令（最高性能）

• ARM: RBIT (ARMv7-A/ARMv8) 單指令完成
• x86: BMI2 指令集無直接反轉，但可用 PSHUFB (SSE) 或 GF2P8AFFINEQB (AVX512) 並行處理
• GCC/Clang 內建: __builtin_bitreverse32(x) 自動選擇最佳實現

性能對比 (x86-64, -O3, 10^8 次調用)

工程建議

1. 首選 __builtin_bitreverse32() 或 _byteswap_ulong() (MSVC) — 可移植、編譯器優化最佳
2. 無內建環境：並行法平衡速度/體積，無查表依賴
3. 極致性能熱點：查表法或內聯汇編調用硬件指令
4. 類型安全：使用 uint32_t 明確 32 位，避免符號擴展陷阱

擴展：64 位與任意寬度

uint64_t reverse_bits64(uint64_t x) {
    x = ((x >> 1) & 0x5555555555555555ULL) | ((x & 0x5555555555555555ULL) << 1);
    x = ((x >> 2) & 0x3333333333333333ULL) | ((x & 0x3333333333333333ULL) << 2);
    x = ((x >> 4) & 0x0F0F0F0F0F0F0F0FULL) | ((x & 0x0F0F0F0F0F0F0F0FULL) << 4);
    x = ((x >> 8) & 0x00FF00FF00FF00FFULL) | ((x & 0x00FF00FF00FF00FFULL) << 8);
    x = ((x >> 16) & 0x0000FFFF0000FFFFULL) | ((x & 0x0000FFFF0000FFFFULL) << 16);
    x = (x >> 32) | (x << 32);
    return x;
}

總結

位逆序操作展示了「算法優化 → 指令級並行 → 硬件加速」的經典演進路徑。理解並行掩碼邏輯不僅能寫出高性能位運算代碼，更能訓練位級思維，為壓縮、加密、圖形、網絡協議等底層開發打下堅實基礎。