C 語言實作 32 位整數二進位逆序並輸出結果

問題描述

給定一個 32 位有號整數，將其二進位位元序列完全反轉（MSB↔LSB），輸出反轉後對應的整數值。例如：

2  = 0000...0010 (32 bits)
逆序 = 0100...0000 = 1073741824

核心邏輯：位元操作三步曲

1. 取最低位：b & 1 保留 LSB，其餘歸零。
2. 源右移：b >>= 1 將下一位移至 LSB 位置，循環 32 次遍歷所有位。
3. 目標左移+寫入：a <<= 1 為新位騰出 LSB 位置；a |= (bit) 寫入當前位。循環 32 次後，首個讀取的位已移至 MSB。

完整可執行代碼

#include 
#include 

uint32_t reverse_bits(uint32_t x) {
    uint32_t result = 0;
    for (int i = 0; i < 32; ++i) {
        result = (result << 1) | (x & 1u);
        x >>= 1;
    }
    return result;
}

int main() {
    uint32_t test_cases[] = {2, 1, 0, 0xFFFFFFFF, 0x80000000, 0x12345678};
    for (size_t i = 0; i < sizeof(test_cases)/sizeof(test_cases[0]); ++i) {
        uint32_t n = test_cases[i];
        printf("0x%08X -> 0x%08X (%u)\n", n, reverse_bits(n), reverse_bits(n));
    }
    return 0;
}

關鍵細節與避坑指南

1. 使用無號型別

右移有號整數為實作定義行為（算術右移補符號位），會導致負數反轉錯誤。務必使用 uint32_t 或 unsigned int。

2. 位元寬度常數化

避免硬編碼 32，改用 sizeof(uint32_t) * CHAR_BIT（需 ），提升可移植性。

3. 編譯器內建函數優化

GCC/Clang/MSVC 提供 __builtin_bitreverse32 或 _byteswap_ulong，單指令完成，效能遠超迴圈：

#if defined(__GNUC__) || defined(__clang__)
    return __builtin_bitreverse32(x);
#elif defined(_MSC_VER)
    return _byteswap_ulong(x);
#else
    // 迴圈實作
#endif

4. 查表法

預計算 0~255 逆序表，每次查 4 次表並移位組合，平衡速度與程式碼體積：

static const uint8_t rev8[256] = { /* 預計算 */ };
uint32_t reverse_bits_lut(uint32_t x) {
    return (rev8[x & 0xFF] << 24) |
           (rev8[(x >> 8) & 0xFF] << 16) |
           (rev8[(x >> 16) & 0xFF] << 8) |
           (rev8[x >> 24]);
}

測試輸出範例

0x00000002 -> 0x40000000 (1073741824)
0x00000001 -> 0x80000000 (2147483648)
0x00000000 -> 0x00000000 (0)
0xFFFFFFFF -> 0xFFFFFFFF (4294967295)
0x80000000 -> 0x00000001 (1)
0x12345678 -> 0x1E6A2C48 (510311752)

擴展思考

• 64 位整數：同理擴展至 64 迴圈或查表 8 次。
• 任意位寬：參數化位寬 n，迴圈 n 次。
• 網路位序轉換：htonl/ntohl 為大小端轉換，非位元反轉，勿混淆。
• 應用場景：位元板表示、哈希函數擾動、快速傅立葉變換位元反序、加密演算法。

總結

32 位整數二進位逆序的本質是「從 LSB 讀取、向 MSB 寫入」。掌握 &1 取位、>>=1 右移、<<=1 | bit 左移寫入三大基本操作，即可靈活應對各種位元操作面試題與工程需求。生產環境優先使用編譯器內建函數或查表法獲取最佳效能。