格雷码:任意两个相邻的二进制数之间只有一位不同
想必通信专业的学生应该都接触过格雷码,它出现在数电、通信原理等课程里。
如下图所示一个四位格雷码是什么样子的:
格雷码的特点:
其最大的特点是任意上下相邻的两个码值间,只有一位码不同,这样在码值上下变化过程中,每次只改变一位码,从而传输、读数的错码率最小。
格雷码的实现:
从上图中可以看到一些规律,灰色部分的格雷码是紫色部分格雷码翻转后再在高位补1得到的,所以我们可以根据前 n-1 位得到的格雷码推出 n 位格雷码。
89. 格雷编码 - 力扣(LeetCode)
class Solution {
public:vector<int> grayCode(int n) {vector<int> res;res.push_back(0);for(int i=0;i<n;i++)//运行到第几位{int len = res.size();for(int j=len-1;j>=0;j--)//倒着遍历即为翻转的逻辑{res.push_back(res[j]|(1<<i));//将高位置1}}return res;}
};
上面的生成方式的条件是第一个数字是0,如果需要从任意一个数字开始,并生成n位的格雷码该怎么实现呢?
思想就是利用上面生成格雷码的方式,将生成好的码表与开始的数字进行异或,这样就可以生成以任意数字开始的格雷码。
1238. 循环码排列 - 力扣(LeetCode)
class Solution {
public:vector<int> circularPermutation(int n, int start) {vector<int> res;res.push_back(start);for(int i=0;i<n;i++){int len = res.size();for(int j=len-1;j>=0;j--){//(res[j]^start|(1<<i))即生成以0开始的格雷码//然后再与start进行异或即为结果res.push_back((res[j]^start|(1<<i))^start);}}return res;}
};