位操作与算法：用位运算实现位反转

位反转，听起来挺唬人的一个词。说白了，就是把一个二进制数的比特顺序完全颠倒过来。比如 10110010 反转后变成 01001101。你可能会问：这玩意儿有什么用？

我在做嵌入式通信协议的时候遇到过。当时要处理一个 SPI 接口的数据，芯片手册上明确写着「数据以 MSB 优先发送」，但我的传感器偏偏输出 LSB 优先。嗯，这时候位反转就派上用场了。不用它，你就得手动移位拼接，代码又臭又长。

什么是位反转？

先看个直观的例子。假设我们有一个 8 位的数：

原始数据:  1 0 1 1 0 0 1 0  (二进制)
反转后:    0 1 0 0 1 1 0 1  (二进制)

注意看，第 0 位（最低位）变成了第 7 位（最高位），第 1 位变成了第 6 位，依此类推。这就是位反转的核心思想——对称交换。

我个人习惯把位反转分成两类：

• 按位反转：逐位交换，适合任意位宽
• 查表反转：预计算所有可能结果，适合固定位宽且性能敏感的场景

方法一：逐位交换法

这是最直观的方法。你想想看，既然要反转，那就把最低位取出来放到最高位，次低位放到次高位……循环处理即可。

uint8_t reverse_bits_naive(uint8_t x) {
    uint8_t result = 0;
    for (int i = 0; i < 8; i++) {
        result = (result << 1) | (x & 1);
        x >>= 1;
    }
    return result;
}

这段代码的逻辑很清晰：每次取 x 的最低位，拼接到 result 的末尾，然后 x 右移一位。循环 8 次后，result 就是反转后的结果。

方法二：分治交换法

有没有更快的办法？有。用分治思想，一次交换一半。这就像洗牌时把牌分成两叠，然后交叉合并。

uint8_t reverse_bits_divide(uint8_t x) {
    x = (x & 0xF0) >> 4 | (x & 0x0F) << 4;
    x = (x & 0xCC) >> 2 | (x & 0x33) << 2;
    x = (x & 0xAA) >> 1 | (x & 0x55) << 1;
    return x;
}

我来拆解一下这个过程：

1. 第一步：交换高 4 位和低 4 位
2. 第二步：在每个 4 位组内，交换高 2 位和低 2 位
3. 第三步：在每个 2 位组内，交换相邻的 1 位

为什么这样更快？因为没有循环，全是位运算，编译器可以优化成几条指令。我在 ARM Cortex-M 上测试过，这个函数只需要 6 个时钟周期左右。

方法三：查表法

如果位宽固定，而且你追求极致性能，查表法是最快的。预先把所有可能的反转结果算好，存成一个数组。运行时直接查表，一次搞定。

// 预计算 8 位反转表
static const uint8_t bit_reverse_table[256] = {
    0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0,
    0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
    // ... 省略中间数据，实际应有 256 项
    0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF,
    0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

uint8_t reverse_bits_lookup(uint8_t x) {
    return bit_reverse_table[x];
}

查表法的优点很明显：时间复杂度 O(1)，而且代码极简。但代价是占用了 256 字节的 ROM。在 8 位 MCU 上，256 字节可能不算什么，但在某些超低成本的芯片上，这可能是奢侈的。

方法四：64 位扩展反转

如果你处理的是 32 位或 64 位数据，分治法同样适用，只是掩码要相应调整。下面是一个 32 位反转的例子：

uint32_t reverse_bits_32(uint32_t x) {
    x = (x & 0xFFFF0000) >> 16 | (x & 0x0000FFFF) << 16;
    x = (x & 0xFF00FF00) >> 8  | (x & 0x00FF00FF) << 8;
    x = (x & 0xF0F0F0F0) >> 4  | (x & 0x0F0F0F0F) << 4;
    x = (x & 0xCCCCCCCC) >> 2  | (x & 0x33333333) << 2;
    x = (x & 0xAAAAAAAA) >> 1  | (x & 0x55555555) << 1;
    return x;
}

这个模式很清晰：先交换 16 位，再交换 8 位，然后 4 位、2 位、1 位。一共 5 步，没有循环，效率极高。

四种方法对比

方法	时间复杂度	空间开销	适用场景
逐位交换法	O(n)	极小	教学演示、位宽不固定
分治交换法	O(log n)	极小	通用场景，性能与资源平衡
查表法	O(1)	256 字节（8位）	性能敏感、ROM 充足
64 位扩展法	O(log n)	极小	32/64 位数据反转

位反转的应用场景

除了前面提到的 SPI 数据顺序调整，位反转在以下场景也很常见：

• FFT 算法：快速傅里叶变换中，输入数据需要按位反转顺序重排
• CRC 校验：某些 CRC 算法要求数据按位反转后再计算
• 图像处理：某些像素格式的字节序需要反转
• 加密算法：DES、AES 等算法中涉及位置换操作

知识体系图

下面这张图总结了位反转的四种实现方法及其关系：

总结

位反转这个操作，说难不难，说简单也不简单。关键在于根据你的实际场景选择合适的方法：

• 如果你只是写个测试程序，逐位交换法最直观
• 如果你在做嵌入式底层驱动，分治交换法是最稳妥的选择
• 如果你的 ROM 够大且性能要求苛刻，查表法值得考虑
• 如果你在处理 32 位以上的数据，扩展分治法是最佳实践

我个人最常用的是分治交换法。它没有查表法的 ROM 开销，也没有逐位法的循环延迟，在大多数场景下都是最优解。嗯，说白了，这就是「用空间换时间」和「用时间换空间」之间的权衡，而分治法恰好站在了中间。

---