算法学习 - 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 <iostream> #include <vector> #include <math.h> #include <string.h> using namespace std; class Solution{ public: vector<int> grayCode(int n){ vector<int> 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<int> test; Solution sl; test = sl.grayCode(3); vector<int>::iterator iter; for (iter = test.begin(); iter != test.end(); iter++) { printf("%d\n",*iter); } return 0; }
- 2楼chenfs19928小时前
- 代码忘了写注释,函数InitToBit是把十进制转换为二进制,BitToGray是把二进制转换为格雷码,GrayToInt是把格雷码当做二进制代码表示成十进制。所以GrayToInt不是解码。假如要解码的话,请自行修改GrayToInt。这个代码是我放到leetcode的代码。
- 1楼chenfs19928小时前
- 代码忘了写注释,函数InitToBit是把十进制转换为二进制,BitToGray是把二进制转换为格雷码,GrayToInt是把格雷码当做二进制代码表示成十进制。所以GrayToInt不是解码。假如要解码的话,请自行修改GrayToInt。这个代码是我放到leetcode的代码。