愛(ài)華網(wǎng)格雷碼(GrayCode)是一個(gè)數(shù)列集合，每個(gè)數(shù)使用二進(jìn)位來(lái)表示，假設(shè)使用n位元來(lái)表示每個(gè)數(shù)字，任兩個(gè)數(shù)之間只有一個(gè)位元值不同。例如以下為3位元的格雷碼：000 001 011 010110 111 101 100 。如果要產(chǎn)生n位元的格雷碼，那么格雷碼的個(gè)數(shù)為2^n.
假設(shè)原始的值從0開(kāi)始，格雷碼產(chǎn)生的規(guī)律是：第一步，改變最右邊的位元值；第二步，改變右起第一個(gè)為1的位元的左邊位元；第三步，第四步重復(fù)第一步和第二步，直到所有的格雷碼產(chǎn)生完畢（換句話說(shuō)，已經(jīng)走了(2^n)- 1 步）。
用一個(gè)例子來(lái)說(shuō)明：假設(shè)產(chǎn)生3位元的格雷碼，原始值位 000第一步：改變最右邊的位元值：001第二步：改變右起第一個(gè)為1的位元的左邊位元：011第三步：改變最右邊的位元值： 010第四步：改變右起第一個(gè)為1的位元的左邊位元： 110第五步：改變最右邊的位元值： 111第六步：改變右起第一個(gè)為1的位元的左邊位元： 101第七步：改變最右邊的位元值： 100
如果按照這個(gè)規(guī)則來(lái)生成格雷碼，是沒(méi)有問(wèn)題的，但是這樣做太復(fù)雜了。如果仔細(xì)觀察格雷碼的結(jié)構(gòu)，我們會(huì)有以下發(fā)現(xiàn)：1、除了最高位（左邊第一位），格雷碼的位元完全上下對(duì)稱（看下面列表）。比如第一個(gè)格雷碼與最后一個(gè)格雷碼對(duì)稱（除了第一位），第二個(gè)格雷碼與倒數(shù)第二個(gè)對(duì)稱，以此類推。2、最小的重復(fù)單元是 0 ,1。
000
001
011
010
110
111
101
100
所以，在實(shí)現(xiàn)的時(shí)候，我們完全可以利用遞歸，在每一層前面加上0或者1，然后就可以列出所有的格雷碼。比如：第一步：產(chǎn)生 0, 1 兩個(gè)字符串。第二步：在第一步的基礎(chǔ)上，每一個(gè)字符串都加上0和1，但是每次只能加一個(gè)，所以得做兩次。這樣就變成了00,01,11,10 （注意對(duì)稱）。第三步：在第二步的基礎(chǔ)上，再給每個(gè)字符串都加上0和1，同樣，每次只能加一個(gè)，這樣就變成了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.
也就是說(shuō)，n位元格雷碼是基于n-1位元格雷碼產(chǎn)生的。
如果能夠理解上面的部分，下面部分的代碼實(shí)現(xiàn)就很容易理解了。[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;
- }
轉(zhuǎn)載請(qǐng)注明出處：blog.csdn.net/beiyeqingteng
![[轉(zhuǎn)]格雷碼 2421碼轉(zhuǎn)格雷碼](http://img.413yy.cn/images/30101030/30084148t01e2c076dd1b8e17fc.jpg)
格雷碼轉(zhuǎn)換快速方法
（假設(shè)以二進(jìn)制為0的值做為格雷碼的0） G：格雷碼B：二進(jìn)位碼 G(N)= B(n+1) XOR B(n)格雷碼轉(zhuǎn)二進(jìn)位數(shù)
二進(jìn)位碼第n位= 二進(jìn)位碼第（n+1）位時(shí)異或格雷碼第n位。因?yàn)槎M(jìn)位碼和格雷碼皆有相同位數(shù)，所以二進(jìn)位碼可從最高位的左邊位元取0，以進(jìn)行計(jì)算?！ ±纾焊窭状a0111，為4位數(shù)，所以其所轉(zhuǎn)為之二進(jìn)位碼也必為4位數(shù)，因此可取轉(zhuǎn)成之二進(jìn)位碼第五位為0，即0b3 b2 b1 b0?！ ?xor 0=0，所以b3=0 0xor 1=1，所以b2=1 1xor 1=0，所以b1=0 0xor 1=1，所以b0=1 因此所轉(zhuǎn)換為之二進(jìn)位碼為0101愛(ài)華網(wǎng)本文地址 » http://www.klfzs.com/a/25101010/27362.html
