格雷码：相邻只差一位的计数法

题目

普通二进制里，从 3（011）到 4（100）要同时翻转 3 个比特。若用在机械转盘或模数转换上，瞬间多比特跳变极易出错。能不能设计一种编码，让相邻两个整数只差 1 个比特？

答案与解析

能，这就是格雷码（Gray Code），用“反射构造”：

• 1 位：0, 1
• 2 位：00, 01, 11, 10（相邻只变 1 位）
• 3 位：000,001,011,010,110,111,101,100

构造规律：第 $n$ 位格雷码 = 前 $2^{n-1}$ 个前面补 0，再把前 $2^{n-1}$ 个倒序前面补 1。

解法公式（整数 $x$ 的格雷码 $g$）： $g = x \oplus (x \gg 1)$ 其中 $\oplus$ 是异或、$\gg$ 是右移。反过来也能还原 $x$。

背后的数学

格雷码由弗兰克·格雷 1947 年申请专利（用于防止 PCM 通信误码）。它本质是超立方体上的哈密顿路径——每个 $n$ 位串是顶点，翻转一位是边，格雷码就是走遍所有顶点只动一比特的路线。至今广泛用于编码器、FPGA、错误最小化计数，是“相邻只差一点”的工程智慧。