位元反轉：從低位到高位重建整數
將 32 位整數的二進制位序列完全反轉（bit-reversal），即最高位變最低位、次高位變次低位...，這在 FFT、網路位序轉換、密碼學中常用。
標準迴圈實作
#include <stdio.h>
#include <stdint.h>
// 反轉 32 位無號整數的位序列
uint32_t reverseBits(uint32_t n) {
uint32_t rev = 0;
for (int i = 0; i < 32; i++) {
rev = (rev << 1) | (n & 1); // 取 n 最低位，加到 rev 最低位
n >>= 1; // n 右移，準備下一位
}
return rev;
}
int main() {
printf("reverse(1) = %u (0x%08X)\n", reverseBits(1), reverseBits(1)); // 0x80000000
printf("reverse(0) = %u (0x%08X)\n", reverseBits(0), reverseBits(0)); // 0x00000000
printf("reverse(-1) = %u (0x%08X)\n", reverseBits(-1), reverseBits(-1)); // 0xFFFFFFFF
printf("reverse(0x12345678) = %u (0x%08X)\n", reverseBits(0x12345678), reverseBits(0x12345678));
return 0;
}
執行結果解析
| 輸入 | 二進制 | 輸出 | 反轉後二進制 |
|---|
| 1 | 000...001 | 2147483648 | 100...000 (0x80000000) |
| 0 | 000...000 | 0 | 000...000 |
| -1 (0xFFFFFFFF) | 111...111 | 4294967295 | 111...111 (不變) |
| 0x12345678 | 0001 0010 0011 0100 0101 0110 0111 1000 | 0x1E6A2C48 | 0001 1110 0110 1010 0010 1100 0100 1000 |
優化版本：分治法 (O(log n) 步驟)
uint32_t reverseBitsFast(uint32_t n) {
// 交換相鄰 16 位塊
n = (n >> 16) | (n << 16);
// 交換相鄰 8 位塊
n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
// 交換相鄰 4 位塊
n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
// 交換相鄰 2 位塊
n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
// 交換相鄰 1 位
n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
return n;
}
查表法 (最快，需 256-byte 表)
// 編譯期生成查表
static const uint8_t reverseByte[256] = {
0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, // ...
// 完整 256 個值...
};
uint32_t reverseBitsLookup(uint32_t n) {
return (reverseByte[n & 0xFF] << 24) |
(reverseByte[(n >> 8) & 0xFF] << 16) |
(reverseByte[(n >> 16) & 0xFF] << 8) |
(reverseByte[(n >> 24) & 0xFF]);
}
效能比較 (單次呼叫)
| 方法 | 指令數 | 記憶體存取 | 適用場景 |
|---|
| 迴圈法 | ~50 | 無 | 教學、無快取壓力 |
| 分治法 | ~20 | 無 | 通用高效能 |
| 查表法 | ~10 | 4 次 L1 快取 | 極高頻呼叫 |
| CPU 指令 | 1 (rbit/bswap) | 無 | ARMv8/現代 x86 |
硬體指令支援
- ARMv8 (AArch64)：
RBIT 指令單週期完成
- x86 (BMI2)：無直接 bit-reverse，但可用
BSWAP + 位操作組合
- RISC-V：
bitmanip 擴展含 rev8、revw
- 編譯器內建：GCC
__builtin_bitreverse32 (較新版本)
應用場景
- FFT/IFFT：位元反序重排
- 網路程式：大小端轉換 (配合位元組反轉)
- 密碼學：某些置換盒 (S-box) 運算
- 資料結構：Van Emde Boas 樹索引計算
