爱华网格雷码(GrayCode)是一个数列集合，每个数使用二进位来表示，假设使用n位元来表示每个数字，任两个数之间只有一个位元值不同。例如以下为3位元的格雷码：000 001 011 010110 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位元格雷码产生的。
如果能够理解上面的部分，下面部分的代码实现就很容易理解了。[java]view plaincopy
- publicString[]GrayCode(intn){
- //produce2^ngradecodes
- String[]graycode=newString[(int)Math.pow(2,n)];
- if(n==1){
- graycode[0]="0";
- graycode[1]="1";
- returngraycode;
- }
- String[]last=GrayCode(n-1);
- for(inti=0;i<last.length;i++){
- graycode[i]="0"+last[i];
- graycode[graycode.length-1-i]="1"+last[i];
- }
- returngraycode;
- }
- publicvoidgetGrayCode(intbitNum){
- for(inti=0;i<(int)Math.pow(2,bitNum);i++){
- intgrayCode=(i>>1)^i;
- System.out.println(num2Binary(grayCode,bitNum));
- }
- }
- publicStringnum2Binary(intnum,intbitNum){
- Stringret="";
- for(inti=bitNum-1;i>=0;i--){
- ret+=(num>>i)&1;
- }
- returnret;
- }
转载请注明出处：blog.csdn.net/beiyeqingteng
![[转]格雷码 2421码转格雷码](http://img.413yy.cn/images/30101030/30084148t01e2c076dd1b8e17fc.jpg)
