23、位操作与算法：用位运算实现格雷码生成

格雷码这东西，我第一次接触是在做编码器信号处理的时候。当时电机一转，数据线哗哗地跳，普通二进制码在边界处同时翻转多位，导致毛刺不断。后来老工程师丢给我一句话：「去查查格雷码，相邻两个数只变一位。」嗯，从那以后，我就再也没用普通二进制做过位置编码了。

说白了，格雷码就是相邻两个数值之间，只有1个比特位不同的编码方式。它在硬件设计中特别有用——减少信号跳变时的竞争冒险，降低功耗，还能避免数据采集时的毛刺误判。

格雷码的数学定义

先看一个4位格雷码的例子：

看到规律了吗？从3(0011)到4(0100)，二进制变了3位，格雷码只变了1位。这就是格雷码的核心价值。

二进制转格雷码：一行代码搞定

二进制转格雷码的公式非常简单：

gray = binary ^ (binary >> 1)

就这么一行。我当年第一次看到这个公式时愣了半天——这么优雅？是的，位运算的魅力就在于此。

展开解释一下：

• binary >> 1 把二进制右移一位
• ^ 异或操作，把原数和右移后的数逐位比较
• 结果就是格雷码

举个例子，二进制 5 (0101)：

  0101
^ 0010  (0101 >> 1)
-------
  0111  → 格雷码 7

验证一下表格，5的格雷码确实是0111，没错。

格雷码转二进制：逆向也不难

反过来，从格雷码恢复二进制，稍微绕一点：

uint32_t gray_to_binary(uint32_t gray) {
    uint32_t binary = gray;
    while (gray >>= 1) {
        binary ^= gray;
    }
    return binary;
}

原理是什么？格雷码的最高位和二进制最高位相同，然后逐位异或下去。你可以理解为：从高位往低位，每一位都是当前格雷位和上一位二进制位的异或结果。

我个人习惯用循环实现，因为可读性好。但在性能敏感的场景，我会用查表法——比如4位一组查表，8位一组查表，速度更快。

binary = gray;
binary ^= gray >> 1;
binary ^= gray >> 2;
binary ^= gray >> 4;

生成格雷码序列：用位运算遍历

有时候我们需要生成一个完整的格雷码序列。比如做状态机编码，或者生成测试向量。用位运算可以高效实现：

void generate_gray_sequence(int n) {
    int total = 1 << n;  // 2^n 个码
    for (int i = 0; i < total; i++) {
        uint32_t gray = i ^ (i >> 1);
        printf("i=%d, gray=%u\n", i, gray);
    }
}

这个循环从0到2^n-1，每次调用二进制转格雷码公式，就能得到完整的格雷码序列。注意，这个序列是循环码——最后一个和第一个也只差1位。

格雷码的递推生成：另一种思路

除了用公式，还可以用递推方式生成格雷码。我记得有一次做FPGA开发，需要硬件实时生成格雷码序列，用递推法更省资源：

// 递推生成n位格雷码
// 思路：n位格雷码 = 0 + (n-1位格雷码) 拼接 1 + (n-1位格雷码逆序)
void generate_gray_recursive(int n) {
    if (n == 0) return;
    int size = 1 << n;
    uint32_t *gray = malloc(size * sizeof(uint32_t));
    gray[0] = 0;
    gray[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        int half = 1 << (i - 1);
        // 前半部分不变
        // 后半部分：最高位置1，然后逆序复制前半部分
        for (int j = 0; j < half; j++) {
            gray[half + j] = (1 << (i - 1)) | gray[half - 1 - j];
        }
    }
    
    // 打印结果
    for (int i = 0; i < size; i++) {
        printf("gray[%d] = %u\n", i, gray[i]);
    }
    free(gray);
}

这个方法的本质是：n位格雷码的前一半是0加上(n-1)位格雷码，后一半是1加上(n-1)位格雷码的逆序。你想想看，这正好保证了相邻两个码之间只变一位——前半部分内部相邻只变一位，后半部分内部也是，而中间交界处（half-1和half）因为最高位从0变1，其他位对称，也只变一位。

格雷码在嵌入式中的实际应用

我曾经在一个电机控制项目里用过格雷码。当时用绝对值编码器，输出是并行二进制数据。电机高速旋转时，数据在边界处同时翻转多位，导致MCU读到错误的位置值。换成格雷码后，问题立刻消失。

具体做法是：

• 编码器输出格雷码
• MCU用gray_to_binary()转成二进制
• 然后做位置计算

还有一个场景是状态机编码。如果你用普通二进制编码状态机，相邻状态之间可能有多位变化，容易产生毛刺。用格雷码编码状态，每次状态切换只变一位，稳定性好很多。

格雷码生成的核心逻辑图

下面这张图展示了二进制与格雷码之间的转换关系，以及格雷码序列的生成流程：

性能对比：位运算 vs 查表法

在实际项目中，我做过一个性能测试。在STM32F4上，生成1024个格雷码：

可以看到，位运算公式法在代码量和执行时间上取得了很好的平衡。我个人推荐在大多数场景下使用公式法，只有在极端性能要求下才用查表法。

格雷码生成这件事，说白了就是一行异或操作的事。但它的应用场景非常广泛——从编码器数据采集到状态机设计，从信号同步到低功耗通信。掌握了这个位运算技巧，你在处理边界跳变问题时就能多一个有力的工具。

公众号:蓝海资料掘金营，微信deep3321