C語言32位整數二進制逆序：原理、實現與優化

本文詳細講解如何將一個 32 位無符號整數的二進制位順序完全反轉（最高位↔最低位），提供從基礎循環到無分支並行算法、查表法、編譯器內建函數的完整演進路徑，並給出性能基準與工程選型指南。

問題定義

reverse_bits(0x00000002) = 0x40000000
// 0000...0010 → 0100...0000

基礎位運算速查

算法 1：逐位搬移循環（教學首選）

uint32_t reverse_loop(uint32_t x) {
    uint32_t y = 0;
    for (int i = 0; i < 32; ++i) {
        y = (y << 1) | (x & 1);  // y 左移騰位，吸收 x 當前 LSB
        x >>= 1;                 // x 右移，下一位移至 LSB
    }
    return y;
}

• 邏輯清晰：y 作為結果累加器，每輪左移 1 位，最低位置入 x 的 LSB
• 32 次迭代，編譯器 -O2 通常自動展開
• 無數據相關分支，適合流水線

算法 2：分治並行反轉（無循環，O(log w)）

uint32_t reverse_parallel(uint32_t x) {
    x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1);  // 交換相鄰 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 步完成 32 位全反轉，指令級並行度高。

算法 3：查表法（空間換時間）

static const uint8_t rev_byte[256] = {
    0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0,
    0x08,0x88,0x48,0xC8,0x28,0xA8,0x68,0xE8,0x18,0x98,0x58,0xD8,0x38,0xB8,0x78,0xF8,
    0x04,0x84,0x44,0xC4,0x24,0xA4,0x64,0xE4,0x14,0x94,0x54,0xD4,0x34,0xB4,0x74,0xF4,
    0x0C,0x8C,0x4C,0xCC,0x2C,0xAC,0x6C,0xEC,0x1C,0x9C,0x5C,0xDC,0x3C,0xBC,0x7C,0xFC,
    0x02,0x82,0x42,0xC2,0x22,0xA2,0x62,0xE2,0x12,0x92,0x52,0xD2,0x32,0xB2,0x72,0xF2,
    0x0A,0x8A,0x4A,0xCA,0x2A,0xAA,0x6A,0xEA,0x1A,0x9A,0x5A,0xDA,0x3A,0xBA,0x7A,0xFA,
    0x06,0x86,0x46,0xC6,0x26,0xA6,0x66,0xE6,0x16,0x96,0x56,0xD6,0x36,0xB6,0x76,0xF6,
    0x0E,0x8E,0x4E,0xCE,0x2E,0xAE,0x6E,0xEE,0x1E,0x9E,0x5E,0xDE,0x3E,0xBE,0x7E,0xFE,
    0x01,0x81,0x41,0xC1,0x21,0xA1,0x61,0xE1,0x11,0x91,0x51,0xD1,0x31,0xB1,0x71,0xF1,
    0x09,0x89,0x49,0xC9,0x29,0xA9,0x69,0xE9,0x19,0x99,0x59,0xD9,0x39,0xB9,0x79,0xF9,
    0x05,0x85,0x45,0xC5,0x25,0xA5,0x65,0xE5,0x15,0x95,0x55,0xD5,0x35,0xB5,0x75,0xF5,
    0x0D,0x8D,0x4D,0xCD,0x2D,0xAD,0x6D,0xED,0x1D,0x9D,0x5D,0xDD,0x3D,0xBD,0x7D,0xFD,
    0x03,0x83,0x43,0xC3,0x23,0xA3,0x63,0xE3,0x13,0x93,0x53,0xD3,0x33,0xB3,0x73,0xF3,
    0x0B,0x8B,0x4B,0xCB,0x2B,0xAB,0x6B,0xEB,0x1B,0x9B,0x5B,0xDB,0x3B,0xBB,0x7B,0xFB,
    0x07,0x87,0x47,0xC7,0x27,0xA7,0x67,0xE7,0x17,0x97,0x57,0xD7,0x37,0xB7,0x77,0xF7,
    0x0F,0x8F,0x4F,0xCF,0x2F,0xAF,0x6F,0xEF,0x1F,0x9F,0x5F,0xDF,0x3F,0xBF,0x7F,0xFF
};

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

• 4 次表查找 + 移位/或，常數時間
• 256 字節只讀表，極易命中 L1 緩存
• 嵌入式需評估 Flash 佔用

算法 4：編譯器內建 / 硬件指令（生產首選）

// GCC / Clang
uint32_t reverse_builtin(uint32_t x) {
    return __builtin_bitreverse32(x);
}

// MSVC
uint32_t reverse_msvc(uint32_t x) {
    return _byteswap_ulong(x);  // 注意：_byteswap 交換字節序，非位反轉！
    // MSVC 無直接位反轉內建，需用並行法或內聯汇編
}

• __builtin_bitreverse32 自動選擇目標架構最優實現 (ARM RBIT, x86 並行指令序列)
• 可移植、零維護、性能最優

性能基準 (x86-64, -O3, 10^8 次)

工程選型建議

1. 現代項目：直接使用 __builtin_bitreverse32() (GCC/Clang) 或並行法作為 fallback
2. 無內建工具鏈：並行法最佳平衡，無查表依賴，無循環開銷
3. 極致熱點：查表法或內聯汇編調用 RBIT (ARM) / PSHUFB (x86 SSE)
4. 類型安全：統一使用 uint32_t，避免符號右移擴展符號位導致邏輯錯誤

擴展：64 位版本

uint64_t reverse64(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;
}

總結

位反轉是理解「分治、查表、硬件加速」經典優化路徑的最佳切入點。掌握並行掩碼邏輯不僅能寫出高性能位運算，更能訓練位級思維，為網絡字節序轉換、哈希擴散、位圖索引、壓縮編碼等底層系統開發奠定堅實基礎。