原文出处： WhyWin
简介
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。在数字系统中，常要求代码按一定顺序变化。例如，按自然数递增计数，若采用8421码，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同时发生，则计数中可能出现短暂的其它代码（1100、1111等）。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。格雷码有多种编码形式。
格雷码（Gray Code）曾用过Grey Code、葛莱码、格莱码、戈莱码、循环码、反射二进制码、最小差错码等名字，它们有的不对，有的易与其它名称混淆，建议不要再使用这些曾用名。
格雷码是一种具有反射特性和循环特性的单步自补码，其循环和单步特性消除了随机取数时出现重大错误的可能，其反射和自补特性使得对其进行求反操作也非常方便，所以，格雷码属于一种可靠性编码，是一种错误最小化的编码方式，因此格雷码在通信和测量技术中得到广泛应用。
生成格雷码
格雷码(Gray Code)是一个数列集合，每个数使用二进位来表示，假设使用n位元来表示每个数字，任两个数之间只有一个位元值不同。
例如以下为3位元的格雷码： 000 001 011 010 110 111 101 100 。
如果要产生n位元的格雷码，那么格雷码的个数为2^n.
假设原始的值从0开始，格雷码产生的规律是：
第一步，改变最右边的位元值；
第二步，改变右起第一个为1的位元的左边位元；
第三步，第四步重复第一步和第二步，直到所有的格雷码产生完毕（换句话说，已经走了(2^n) – 1 步）。
用一个例子来说明：
假设产生3位元的格雷码，原始值位 000
第一步：改变最右边的位元值： 001
第二步：改变右起第一个为1的位元的左边位元： 011
第三步：改变最右边的位元值： 010
第四步：改变右起第一个为1的位元的左边位元： 110
第五步：改变最右边的位元值： 111
第六步：改变右起第一个为1的位元的左边位元： 101
第七步：改变最右边的位元值： 100
如果按照这个规则来生成格雷码，是没有问题的，但是这样做太复杂了。如果仔细观察格雷码的结构，我们会有以下发现：
1、除了最高位（左边第一位），格雷码的位元完全上下对称（看下面列表）。比如第一个格雷码与最后一个格雷码对称（除了第一位），第二个格雷码与倒数第二个对称，以此类推。
2、最小的重复单元是 0 , 1。
000
001
011
010
110
111
101
100
所以，在实现的时候，我们完全可以利用递归，在每一层前面加上0或者1，然后就可以列出所有的格雷码。
比如：
第一步：产生 0, 1 两个字符串。
第二步：在第一步的基础上，每一个字符串都加上0和1，但是每次只能加一个，所以得做两次。这样就变成了 00,01,11,10 （注意对称）。
第三步：在第二步的基础上，再给每个字符串都加上0和1，同样，每次只能加一个，这样就变成了 000,001,011,010,110,111,101,100。
好了，这样就把3位元格雷码生成好了。
如果要生成4位元格雷码，我们只需要在3位元格雷码上再加一层0,1就可以了： 0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1110,1010,0111,1001,1000.
也就是说，n位元格雷码是基于n-1位元格雷码产生的。
算法实现
1、递归实现
/**
* 递归生成二进制格雷码
* 思路:1、获得n-1位生成格雷码的数组
* 2、由于n位生成的格雷码位数是n-1的两倍，故只要在n为格雷码的前半部分加0，后半部分加1即可。
* @param n 格雷码的位数
* @return 生成的格雷码数组
*/
public static String[] GrayCode(int n) {
//数组的大小是2的n次方，因为n位的格雷码有2的n次方种排列
String[] grayCodeArr = new String[(int)Math.pow(2, n)];
if(n < 1)
{
System.out.println("你输入的格雷码位数有误！");
}
if(1 == n)
{
grayCodeArr[0] = "0";
grayCodeArr[1] = "1";
return grayCodeArr;
}
//n-1 位格雷码的生成方式
String[] before = GrayCode(n-1);
for(int i = 0 ; i < before.length ; i++){
grayCodeArr[i] = "0" + before[i];
grayCodeArr[grayCodeArr.length -1 - i] = "1" + before[i];
}
return grayCodeArr;
}
2、非递归实现
/**
* 非递归生成二进制格雷码
* 思路:1、获得n-1位生成格雷码的数组
* 2、由于n位生成的格雷码位数是n-1的两倍，故只要在n为格雷码的前半部分加0，后半部分加1即可。
* @param n 格雷码的位数
* @return 生成的格雷码数组
*/
public static String[] GrayCode2(int n)
{
int num = (int)Math.pow(2, n);//根据输入的整数，计算出此Gray序列大小
String[] s1 = {"0","1"};//第一个Gray序列
if(n < 1)
{
System.out.println("你输入的格雷码位数有误！");
}
for(int i=2;i<=n;i++){//循环根据第一个Gray序列，来一个一个的求
int p = (int)Math.pow(2, i);//到了第几个的时候，来计算出此Gray序列大小
String[] si = new String[p];
for(int j=0;j<p;j++){//循环根据某个Gray序列，来一个一个的求此序列
if(j<(p/2)){
si[j] = "0" + s1[j];//原始序列前面加上"0"
}else{
si[j] = "1" + s1[p-j-1];//原始序列反序，前面加上"1"
}
}
s1 = si;//把求得的si，附给s1,以便求下一个Gray序列
}
return s1;
}
3、测试
public static void main(String[] args) {
System.out.println("————————————————————递归实现————————————————");
String[] strArr = GrayCode(4);
for(int i = 0 ; i < strArr.length ; i++)
{
System.out.println(strArr[i]);
}
System.out.println("——————————————————非递归实现————————————————");
String[] strArr2 = GrayCode2(4);
for(int i = 0 ; i < strArr2.length ; i++)
{
System.out.println(strArr2[i]);
}
}
4、结果：
————————————————————递归实现———————————————— 0001 0010 0111 0100 1101 1110 1011 1000 ——————————————————非递归实现———————————————— 0001 0010 0111 0100 1101 1110 1011 1000
致谢：感谢您的耐心阅读！
