首页 > 代码库 > Gray Code(格雷码)
Gray Code(格雷码)
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]
. Its gray code sequence is:
00 - 001 - 111 - 310 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1]
is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
格雷码的定义:百度百科
二进制 格雷码
0 000 000
1 001 001
2 010 011
3 011 010
4 100 110
5 101 100
6 110 101
7 111 100
方法即:把二进制码从右往左的,把第一位和下一位做异或运算,最左边一位保持不动。
那么把110右移为011,再和自身异或
110^011=101 这种错位的异或,刚好实现了需求
格雷码解码的时候反过来即可,从左边第二位开始与下一位异或。
代码:
class Solution {public: vector<int> grayCode(int n) { vector<int> res; res.push_back(0); for(int i=1;i<(1<<n);++i){ res.push_back((i>>1)^i); } return res; }};
Gray Code(格雷码)