算法學習 - Gray Code(格雷碼)的解釋和c++實現

算法學習 - Gray Code(格雷碼)的解釋和c++實現

Gray Code(格雷碼)

典型的二進制格雷碼（Binary Gray Code）簡稱格雷碼。當初是為了通信，現在則常用於模擬－數字轉換和位置－數字轉換中。

特點是：一組數的編碼中，若任意兩個相鄰的代碼只有一位二進制數不同，則稱這種編碼為格雷碼。

格雷碼屬於可靠性編碼，是一種錯誤最小化的編碼方式。格雷碼是一種絕對編碼方式。由於格雷碼是一種變權碼。格雷碼的十進制數奇偶性與其碼字中1的個數的奇偶性相同。

十進制轉換為格雷碼

好的上面我們已經介紹那麼多了，那麼我來說下如何把一個十進制的數字轉換成格雷碼呢？

首先把十進制的數字轉換成二進制的形式。對n位二進制的碼字，從右到左，以0到n-1編號。如果二進制碼字的第i位和i+1位相同，則對應的格雷碼的第i位為0，否則為1（當i+1=n時，二進制碼字的第n位被認為是0，即第n-1位不變）。

舉例來說：
首先12 -> 二進制：1100
然後二進制碼是：1100 編號為0-3
然後在1100前補一個0,則變為01100，這樣開始操作。

0異或1為1.
1異或1為0.
1異或0為1.
0異或0為0.
所以格雷碼為1010。

格雷碼轉換為十進制

現在我們假設獲取到一個格雷碼為1010.如何解碼為十進制呢。從左邊第二位起，將每位與左邊一位解碼後的值異或，作為該位解碼後的值（最左邊一位依然不變）。依次異或，直到最低位。依次異或轉換後的值（二進制數）就是格雷碼轉換後二進制碼的值。
所以操作結果是：

0 與第一位 1 進行異或結果為 1
上面結果1與第二位0異或結果為 1
上面結果1與第三位1異或結果為 0
上面結果0與第四位0異或結果為 0
所以二進制的值為：1100->十進制為：12.

代碼實現

下面放上代碼實現，這個代碼裡只放了編碼部分，沒放解碼。假如對解碼有問題，可以評論告訴我。

//
//  main.cpp
//  GrayCode_leetcode
//
//  Created by Alps on 14/12/7.
//  Copyright (c) 2014年 chen. All rights reserved.
//

#include 
#include 
#include 
#include 
using namespace std;

class Solution{
public:
    vector grayCode(int n){
        vector gray;
        if (n < 1) {
            gray.push_back(0);
            return gray;
        }
        int num = pow(2,n);
        int graycode[n];
        for (int i = 0; i < num; i++) {
            IntToBit(graycode, i, n);
            BitToGray(graycode,n);
            gray.push_back(GrayBitToInt(graycode, n));
        }
        return gray;
    }
    
    void IntToBit(int *code, int n, int bit){
        int i = bit-1;
        while (i >= 0) {
            code[i--] = n%2;
            n/=2;
        }
    }
    
    void BitToGray(int *code, int bit){
        int temp[bit];
        temp[0] = 0^code[0];
        for (int i = 0; i < bit-1; i++) {
            temp[i+1] = code[i]^code[i+1];
        }
        for (int i = 0; i < bit; i++) {
            code[i] = temp[i];
        }
    }
    
    int GrayBitToInt(int *code, int bit){
        int number = 0;
        for (int i = 0; i < bit; i++) {
            if (code[i] == 1) {
                number += pow(2, bit-i-1);
            }
        }
        return number;
    }
    
};

int main(int argc, const char * argv[]) {
    vector test;
    Solution sl;
    test = sl.grayCode(3);
    vector::iterator iter;
    for (iter = test.begin(); iter != test.end(); iter++) {
        printf("%d\n",*iter);
    }
    
    return 0;
}