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 - 0 01 - 1 11 - 3 10 - 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.
题解:查了资料才发现,原来可以从二进制码转成gray码。比如说二进制码1101,要转成gray码,过程如下:
(1)左边第一位保留:1
(2)第二位与第一位异或得到第二位:1^1 = 0
(3)第三位与第二位异或得到第三位:0^1 = 1
(4)第四位与第三位异或得到第四位:1^0 = 1
所以最后得到的gray码是1011
有一个简单的公式,二进制码x对应的gray码为(x>>1)^x,上情况就是(1101>>1)^1101=1011,原理就是上述描述的过程,把x右移一位,然后错位相异或。至于第一位,如果原来是1,那么右移后得到的0和这个1相异或得到的还是1;如果原来是0,那么右移后得到的0与这个0相异或得到的还是0.
代码如下:
1 class Solution { 2 public: 3 vector<int> grayCode(int n) { 4 int total_number = 1 << n; 5 vector<int> answer; 6 7 for(int i = 0;i < total_number;i++){ 8 answer.push_back((i>>1)^i); 9 } 10 return answer; 11 } 12 };
【leetcode】Gray Code,布布扣,bubuko.com
原文:http://www.cnblogs.com/sunshineatnoon/p/3779603.html