简介
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。在数字系统中，常要求代码按一定顺序变化。例如，按自然数递增计数，若采用8421码，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同时发生，则计数中可能出现短暂的其它代码（1100、1111等）。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。格雷码有多种编码形式。
格雷码（Gray Code）曾用过Grey Code、葛莱码、格莱码、戈莱码、循环码、反射二进制码、最小差错码等名字，它们有的不对，有的易与其它名称混淆，建议不要再使用这些曾用名。
格雷码是一种具有反射特性和循环特性的单步自补码，其循环和单步特性消除了随机取数时出现重大错误的可能，其反射和自补特性使得对其进行求反操作也非常方便，所以，格雷码属于一种可靠性编码，是一种错误最小化的编码方式，因此格雷码在通信和测量技术中得到广泛应用。
生成格雷码
000
001
011
010
110
111
101
100
算法实现
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、结果：
————————————————————递归实现———————————————— 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 ——————————————————非递归实现———————————————— 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
致谢：感谢您的耐心阅读！