这道题应该是考察 grey code 的概念。

格雷码是怎么来的？二进制数011，加1的时候变成100，在老式装置上，这意味着三个位元都要转动，增加了出错的几率。在这种情况下，人们发明了格雷码。

所以很显然，格雷码的特征是：每次加一，只改变一位。

直观的看，三位格雷码列表：

这个顺序与题意的顺序一致，可以看到最后一个格雷码100与第一个格雷码000也只相隔一位。这种也叫做循环格雷码。

我们是根据什么依据产生这种格雷码的呢？从这幅图应该可以看出端倪：

首先是上下对称复制，然后分别冠以0与1. 随着位数的增加，不断重复这个过程。

这样的格雷码与二进制之间有着这样一个公式：从最右边一位起，依次将每一位与左边一位异或(XOR)，作为对应格雷码该位的值，最左边一位不变(相当于左边是0)。

简单表达为：the nth Gray code is obtained by computing (n/2) ^ n.

我的解法也是利用了这个公式。但对于该公式的证明，我却没有想的很明白。