1238. 循环码排列

难度

• Easy
• Medium
• Hard

思路

在看这题之前，先看 89. 格雷编码 。与本题的不同之处在于，No.89 要求第一位是恒定的 0 。

格雷编码的定义基本就是题干描述。而如何生成这样一个编码，大致有两种方法——归纳和公式。

归纳法的证明比较麻烦，就略过了。

使用公式生成格雷编码： $g_i = i \oplus \lfoor \frac{i}{2} \rfloor$

下面证明其正确性。

1. 当 $i$ 为偶数，显然 $i +1$ 是奇数，其二进制形式仅区别于最低的一位。而 $\lfoor \frac{i}{2} \rfloor$ 和 $\lfoor \frac{i +1}{2} \rfloor$ 是相等的（比如 4 和 5）。因此得出的 $g_i$ 也仅相差一位。
2. 当 $i$ 为奇数，我们将其与 $i + 1$的二进制形式作对比，可以从高位到低位分为三个部分。第一个部分中，两者完全相同；第二个部分中， $i$ 均为 0 ， $i +1$ 均为 1 ；第三个部分中， $i$ 均为 1 ， $i + 1$ 均为0。两者右移一位，在高位补 0 。此时第一部分对应的数位，不管是原数还是位移后的数，都是一样的，因此第一部分的异或结果也一定一样。位移后，原有第一部分的最后一位被用于跟第二部分的第一位做异或。前者在两个数中均相同，而后者在两个数中分别为 0 和 1 ，故异或结果一定不同。对于第三部分，除去第一位，剩余位置对于两个数而言都是相同的数做异或，因此异或结果一定都是 1 加上若干 0，两个数均相同。综上所述，三个部分的异或结果中，仅有一位不同。证明完毕。

对于本题要求第一个数是 start ，只需要将每次生成的数与 start 异或即可。

代码