位元操作技巧：16 位元整數位元反轉演算法詳解

問題定義

將 16 位元無號整數的位元順序完全反轉：bit 0 ↔ bit 15、bit 1 ↔ bit 14、…、bit 7 ↔ bit 8。

例：0xB35E (1011 0011 0101 1110) → 0x7ACD (0111 1010 1100 1101)

演算法邏輯

只需處理前 8 位（i = 0..7），每輪交換 bit i 與 bit 15-i：

1. 取出 bit i：(data >> i) & 1
2. 移至目標位置 15-i：((data >> i) & 1) << (15 - i)
3. 同理取出 bit 15-i 移至 i
4. 兩者合併 | 累加至結果

C 語言實作

uint16_t reverse_bits16(uint16_t data)
{
    uint16_t dest = 0;
    for (int i = 0; i < 8; ++i) {
        uint16_t low_bit  = (data >> i) & 1;
        uint16_t high_bit = (data >> (15 - i)) & 1;
        dest |= (low_bit  << (15 - i)) | (high_bit << i);
    }
    return dest;
}

逐步追蹤範例（data = 0xB35E = 45918）

最終 dest = 0x7ACD，與預期相符。

效能優化方向

• 查表法：預計算 256 個 byte 反轉值，兩次查表 + 移位合併，O(1) 無迴圈。
• SWAR (SIMD Within A Register)：以位元運算平行交換（如 0x5555、0x3333、0x0F0F、0x00FF 遮罩），無分支、指令級平行。
• 編譯器內建：GCC/Clang __builtin_bswap16、MSVC _byteswap_ushort。

應用場景

• 網路位元序轉換（大小端轉換）
• CRC 校驗位元反轉
• 位元壓縮/解壓、霍夫曼編碼
• 嵌入式裝置暖存器鏡像