Gray Code(格雷碼) C++多方法實作

簡介

在一組數的編碼中，若任意兩個相鄰的代碼隻有一位二進制數不同，則稱這種編碼為格雷碼（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、異或生成

題解:根據二進制數與格雷碼的轉化關系。

vector<int> grayCode(int n) {
        int count = 1 << n;
        vector<int> res(count,0);
        for(int i = 1 ; i < count; i ++)
        {
            int bin = i,cur = bin >> (n - 1);
            for(int k = n - 1;k > 0;k --)
                cur = (cur << 1) + (((bin >> k) & 1) ^ ((bin >>(k - 1)) & 1));
            res[i] = cur;
        }
        return res;
    }

           

2、遞歸實作

//gray code遞歸

#include <iostream>
#include <vector>
#include <math.h>
#include <string.h>
using namespace std;


vector<string> gray_code(int n)
{
    if(n==1)
    {
        vector<string> v;
        v.push_back("0");
        v.push_back("1");
        return v;
    }
    else
    {
        vector<string> v;
        vector<string> v1;
        v1=gray_code(n-1);

        for(int i=0;i<v1.size();i++)
        {
            v.push_back("0"+v1[i]);
        }
        for(int i=(v1.size()-1);i>-1;i--)
        {
            v.push_back("1"+v1[i]);
        }

        return v;
    }
}

int main(int argc,char *argv[])
{
    int n;
    cout<<"input n:";
    cin>>n;

    vector<string> v;
    v=gray_code(n);
    for(int i=0;i<v.size();i++)
    {
        cout<<v[i]<<endl;
    }
}
           

疊代構造方式

題解三：格雷碼另一種生成方式：從000開始，重複進行如下兩步直至全部生成

• 改變最右邊的位的值
• 改變從右邊開始第一個1左邊元素的值。

vector<int> grayCode(int n) {
        int count = 1 << n;
        vector<int> res(count,0);
        for(int i = 1 ; i < count; i ++)
        {
            int cur = res[i - 1];
            if(i % 2 == 1)
                cur  = cur ^ 1;
            else
            {
                int k = 0;
                while(((cur >> k) & 1) == 0) 
                    k ++;
                cur = cur ^ (1 << (k + 1));
            }
            res[i] = cur;
        }
        return res;
    }