在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。


转换方法:

1.递归生成法:(构造法)

这种方法基于格雷码是反射码的事实，利用递归的如下规则来构造：

1位格雷码有两个码字 0 1

1.(n+1)位格雷码中的前2n个码字等于n位格雷码的码字，按顺序书写，加前缀0

2.(n+1)位格雷码中的后2n个码字等于n位格雷码的码字，按逆序书写，加前缀1 [4]

3.n+1位格雷码的集合 = n位格雷码集合(顺序)加前缀0 + n位格雷码集合(逆序)加前缀1

2,异或转换法

二进制转格雷码(编码): 

 (二进制下标从右到左编号为0~n)

通过公式我们可以知道一个数A,它对应的格雷码G = A^(A >> 1);


格雷码转二进制(解码):

根据异或的自反性，我们可以知道一个格雷码G,它所对应的二进制数A = G^(G >> 1).


例题一:

1238.循环排列码(力扣)


思路:

我们从格雷码的定义中知道，他符合题目中的所有定义（任意相邻两位二进制只差1并且首尾也符合）.

注意他要我们输出的什么，他要我们输出的是格雷码编码的值.(我们要搞清楚一个事实，对于任意的两个不同的数A,B,他们生产的格雷码的值也不会相同)

我们可以O(n)的求出格雷码，temp[i] = x.代表第i个数为值x。我们找到x == start的position，然后再循环输出就好.