题解

格雷码公式

编号为 $k$ 的二进制反射格雷码可以直接计算：

其中 $\oplus$ 表示按位异或，$\gg1$ 表示右移一位。

计算出 $g$ 后，从第 $n-1$ 位到第 $0$ 位依次输出，即可保留前导零并得到恰好 $n$ 位的答案。

本题 $n$ 最大为 $64$，应使用 unsigned long long。不要计算 1ULL << 64，因为移位位数等于类型宽度是未定义行为；本解法不需要计算 $2^n$。

为什么公式成立

普通二进制编号 $k$ 的相邻两位发生进位时，会有一段连续位改变。把 $k$ 与右移一位的 $k$ 异或后，每个格雷码位表示相邻两个二进制位是否不同。这样构造出的顺序与题目给出的“前半加 0、后半反向加 1”的递归生成完全一致。

复杂度

• 计算公式为 $O(1)$；
• 输出 $n$ 位需要 $O(n)$ 时间；
• 空间复杂度：$O(1)$。