C 語言位運算技巧：32 位整數二進制序列反轉

C 語言位運算技巧：32 位整數二進制序列反轉

將 32 位整數的位序列完全反轉（MSB↔LSB），常用於網路位序轉換、位圖鏡像、哈希函數等場景。

實作程式碼

#include <stdio.h>
#include <stdint.h>

uint32_t reverse_bits(uint32_t x) {
    uint32_t rev = 0;
    for (int i = 0; i < 32; i++) {
        rev = (rev << 1) | (x & 1); // 取 x 最低位，加到 rev 最低位
        x >>= 1;                    // x 右移，準備下一位
    }
    return rev;
}

int main() {
    printf("%u\n", reverse_bits(1));       // 2147483648 (0x80000000)
    printf("%u\n", reverse_bits(0));       // 0
    printf("%u\n", reverse_bits(0xFFFFFFFF)); // 4294967295 (全 1 反轉不變)
    return 0;
}

演算法圖解

x = 0000 ... 0001 (1)
迴圈 32 次：
  rev = 0 → 1 → 10 → 100 → ... → 1000 ... 0000 (2^31)

優化版本：查表法 (4 位一組)

static const uint8_t rev_nibble[16] = {
    0x0, 0x8, 0x4, 0xC, 0x2, 0xA, 0x6, 0xE,
    0x1, 0x9, 0x5, 0xD, 0x3, 0xB, 0x7, 0xF
};

uint32_t reverse_bits_fast(uint32_t x) {
    uint32_t rev = 0;
    for (int i = 0; i < 8; i++) {
        rev = (rev << 4) | rev_nibble[x & 0xF];
        x >>= 4;
    }
    return rev;
}

硬體指令加速

• ARM: RBIT 指令單周期反轉。
• x86 (BMI2): _mm_cvtsi64_si32(_mm_shuffle_epi8(...)) 或組合指令。
• GCC/Clang 內建：__builtin_bitreverse32(x) (編譯器自動選最優指令)。

應用場景