原文出处： 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | /** * 递归生成二进制格雷码 * 思路: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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | /** * 非递归生成二进制格雷码 * 思路: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、测试
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | 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、结果：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | ————————————————————递归实现————————————————00010010011101001101111010111000——————————————————非递归实现————————————————00010010011101001101111010111000 |
致谢：感谢您的耐心阅读！
