格雷编码

回溯当然行,但又要记访问过哪些、又要翻哪一位、还可能走死胡同回退。有没有「直接算出来」的办法?

i >> 1 是把 i 右移一位(去掉最低位),再和 i 本身异或。下面我们就逐个 i 套这条公式,把 8 个数一个个算出来填进序列。

起步 · 序列还空着：这排 8 个格子就是要填的序列(先全看成 0)。指针停在第 0 格,我们让 i 从 0 走到 7,每步算一个格雷码填进对应格子。

i = 0：i=0:右移还是 0,0 ^ 0 = 0。第 0 个格雷码是 000,填进第 0 格。序列从 0 开头,符合要求。

i = 1：i=1:1 右移变 0,1 ^ 0 = 1,二进制 001。和上一个 000 比,只有最低位从 0 变 1——差一位,达标。

i = 2：i=2 是 010,右移成 001,010 ^ 001 = 011 = 3。和上一个 001 比,只翻了第二位。填 3 进第 2 格。

i = 3：i=3 是 011,右移 001,011 ^ 001 = 010 = 2。和上一个 011 比,只翻最低位。填 2 进第 3 格。前四个:0,1,3,2。

i = 4：i=4 是 100,右移成 010,100 ^ 010 = 110 = 6。和上一个 010 比,只翻最高位。填 6 进第 4 格。

i = 5：i=5 是 101,右移 010,101 ^ 010 = 111 = 7。和上一个 110 比,只翻最低位。填 7 进第 5 格。

i = 6：i=6 是 110,右移成 011,110 ^ 011 = 101 = 5。和上一个 111 比,只翻中间位。填 5 进第 6 格。

i = 7 · 最后一个：i=7 是 111,右移 011,111 ^ 011 = 100 = 4。和上一个 101 比,只翻最低位。填 4 进最后一格,8 个全填完!

序列完成 ✓：8 个数全部算出:0,1,3,2,6,7,5,4。一条公式 i^(i>>1) 顺序套一遍就出结果,不用判重、不用回退。

逐对验证 · 第 0↔1 对：现在逐对验证「相邻只差一位」。第 0 和第 1 个:000 与 001,异或得 001,只有一位是 1,达标。

逐对验证 · 第 1↔2 对：第 1 和第 2 个:001 与 011,异或得 010,只翻一位,达标。高亮对往右滑一格。

逐对验证 · 第 2↔3 对：第 2 和第 3 个:011 与 010,异或得 001,只翻最低位,达标。

逐对验证 · 第 3↔4 对：第 3 和第 4 个:010 与 110,异或得 100,只翻最高位,达标。跨过中点也照样成立。

逐对验证 · 第 4↔5 对：第 4 和第 5 个:110 与 111,异或得 001,只翻最低位,达标。

逐对验证 · 第 5↔6 对：第 5 和第 6 个:111 与 101,异或得 010,只翻中间位,达标。

逐对验证 · 第 6↔7 对：第 6 和第 7 个:101 与 100,异或得 001,只翻最低位,达标。中间 7 对全部过关。

首尾也只差一位：最后看首尾:第 7 个 100 和第 0 个 000 比,也只差最高位一位——题目要的「首尾相连」也天然满足。8 对全部通过!

下面我们不套公式,改用「照镜子」的办法,从 n=1 一层层长到 n=3,看序列怎么翻倍生长,每步只动一个新加入的数。

构造 · n=1 的种子：n=1 最简单:就是 0, 1(前两格)。把它当「种子」,后面靠照镜子长大。

n=2 · 上半段补 0：造 n=2:上半段直接抄 n=1 的 0,1,在最高位补 0,值不变还是 0,1。下半段(灰色)马上由镜像填出来。

n=2 · 下半段逆序补 1：下半段把 n=1 序列倒过来(1,0),各自最高位补 1:11=3, 10=2。拼起来 n=2 = 0,1,3,2,和公式法一模一样!

n=3 · 上半段补 0：造 n=3:上半段照抄 n=2 的 0,1,3,2,最高位补 0 值不变。下半段(灰色)再镜像一次。

n=3 · 下半段逆序补 1 · 完成：下半段把 n=2 序列倒过来(2,3,1,0),最高位补 1(即 +4):6,7,5,4。拼成 n=3 = 0,1,3,2,6,7,5,4——和公式法分毫不差。两条路殊途同归。

直观理解:相邻整数 i 与 i+1 在二进制上变化集中在低位进位;公式 i^(i>>1) 把这种规律「折叠」成恰好一位的改变。记住公式会用就足够应对面试。

雷区实演 · n=2：换 n=2 验证:循环 2² = 4 次,套公式得 0,1,3,2,即 00→01→11→10,相邻仍只差一位。若把循环写成 range(2) 只跑 2 次,就只剩 0,1——这就是雷区①。

边界三连：想清最小情形:n=0 只一个 0、n=1 是 0/1、n=2 是 0,1,3,2,代码就稳了。

面试追问：把「公式为何对」「O(2ⁿ) 是输出下界」讲清,是这题面试的得分点。