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; }