位倒置是将整数低指定位宽的二进制位顺序完全翻转，必须手动实现，常见于FFT预处理、哈希索引等场景；需明确位宽（如8/16/32），不可直接对int整体操作；小位宽推荐查表法加速，大或非整倍位宽则用循环动态截断处理。
什么是位倒置，它在什么场景下必须手动实现
位倒置（Bit-Reversal）不是标准库函数，std::reverse 对字节有效但对单个整数的二进制位无效。它常用于 FFT（快速傅里叶变换）预处理、某些哈希或索引映射中——要求把一个 n 位整数的比特顺序完全翻转，比如 8 位的 0b00000101（5）变成 0b10100000（160）。
注意：倒置位宽必须明确。你不能对 int 整体倒置（符号位、填充位会干扰），而应指定有效位数，如 8/16/32 位。否则结果不可控。
用查表法加速 8 位和 16 位倒置
小位宽（≤16）查表最快，避免循环或位运算开销。核心是预先生成 uint8_t reverse_table[256]，然后按字节拆分处理：
// 静态初始化查表（C++17 可 constexpr）
constexpr uint8_t reverse_table[256] = {
#define R2(n) n, n+2*64, n+1*64, n+3*64
#define R4(n) R2(n), R2(n+2*16), R2(n+1*16), R2(n+3*16)
#define R8(n) R4(n), R4(n+2*4), R4(n+1*4), R4(n+3*4)
R8(0), R8(2), R8(1), R8(3)
};
使用时：
立即学习“C++免费学习笔记（深入）”；
- 8 位倒置：
reverse_table[x & 0xFF] - 16 位倒置：
(reverse_table[x & 0xFF] > 8) & 0xFF] - 务必先 & 掩码，防止高位污染查表索引
通用模板：对齐到 N 位的位倒置函数
当 N 不是 8 的倍数（如 10 位 FFT 索引），需动态截断。以下函数接受值 x 和位宽 bits（≤32），只倒置低 bits 位，高位清零：
uint32_t bit_reverse(uint32_t x, uint8_t bits) {
uint32_t r = 0;
for (uint8_t i = 0; i < bits; ++i) {
r |= ((x >> i) & 1U) << (bits - 1 - i);
}
return r & ((1U << bits) - 1U); // 严格截断到 bits 位
}
关键点：
- 循环次数由
bits决定，不是固定 32；否则对 10 位输入会错误倒置全部 32 位 - 末尾的
&截断必不可少——否则高位残留导致越界索引 - 若性能敏感且
bits固定，可将该函数特化为 constexpr 模板，编译期展开
用 __builtin_bitreverse* 编译器内置函数要注意平台限制
GCC/Clang 提供 __builtin_bitreverse32 等，但它们总是反转整个类型宽度（32 或 64 位），不支持任意位宽。直接用会出错：
比如想倒置 10 位的 0x00000123（二进制低 10 位是 000100100011），用 __builtin_bitreverse32(0x00000123) 得到的是全部 32 位翻转结果，而非仅低 10 位。
正确做法是：
- 先用掩码提取低
bits位：x & ((1U - 再调用 builtin 函数
- 最后右移补零或再次掩码（因为 builtin 返回的是完整 32 位，高位是原低位翻转后“溢出”的部分）
这反而比手写循环更易错，除非你确定位宽恒为 8/16/32 且无截断需求。
