在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同,则称这种编码为格雷码(Gray Code),另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。在数字系统中,常要求代码按一定顺序变化。例如，按自然数递增计数,若采用8421码，则数0111变到1000时四位均要变化,而在实际电路中，4位的变化不可能绝对同时发生,则计数中可能出现短暂的其它代码(1100、1111等) 。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误（格雷码一位改变特征减小了电路出错概率）。
格雷码有多种编码形式：
表中典型格雷码具有代表性。若不作特别说明，格雷码就是指典型格雷码，它可从自然二进制码转换而来。
下面我们讨论怎么求格雷码（即典型格雷码）：
一、格雷码的生成
方法一：
若要生成n位（即2^n个）格雷码序列，我们首先从0开始：
第一步：改变最右边的位元的值，得到1；
第二步：改变右边起第一个为1位元的左边的那个位元，得到11
第三步：重复一、二步，直到生成要求个数的格雷码
按照上述步骤生成的序列即为格雷码。
eg:000 >> 001 >> 011 >> 010 >> 110 >> 111 >> 101 >> 100 ......
代码实现：
vector<int> getGrayCode(int n){//生成n位格雷码序列
vector<int> ans;
ans.emplace_back(0);
int lenth = 1;//ans数组的长度
while (lenth < (1 << n)) {
if (lenth % 2)ans.emplace_back(ans[lenth - 1] ^ 1);//改变最右边的位元值
else ans.emplace_back(ans[lenth - 1] ^ ((ans[lenth - 1] & -ans[lenth - 1]) << 1));
//num & -num可以得到num中二进制最右边的1，然后再向左移一位
lenth++;
}
return ans;
}方法二：
通过观察可得出，如果我们可以得到n-1位格雷码序列，那么通过将n-1位格雷码序列逆转，再在逆转的格雷码序列的最左端都补上1，将得到的序列连接到原序列后即可得到n位格雷码序列。
eg：已有2位格雷码序列 00 01 11 10
将原序列逆转得 10 11 01 00
在左端补上1得110 111 101 100
接到原序列后面得到3位格雷码 000 001 011 010 110 111 101 100
证明：已有n-1位格雷码序列，则可知n-1位格雷码序列逆序也满足相邻代码只有一位不同，且首尾相连，对逆序的所有代码左端补1不改变上述性质，将两段代码相接后连接处的两个代码只有最高位不同，首尾代码也只有最高位不同，所以得到的是n位格雷码。
代码实现：
vector<int> getGrayCode(int n){//生成n位格雷码序列
vector<int> ans;
ans.emplace_back(0);
for (int i = 0; i < n; i++) {
for (int j = ans.size() - 1; j >= 0; j--) {
ans.emplace_back(ans[j] + (1 << i));
}
}
return ans;
}方法三：
通过自然二进制码得到格雷码
通过观察或者推理都可以得出，格雷码的最高位和自然二进制码的最高位是相同的
对n位二进制的码字，从右到左，以0到n-1编号，如果二进制码字的第i位和i+1位相同，则对应的格雷码的第i位为0，否则为1（当i+1=n时，二进制码字的第n位被认为是0，即第n-1位不变）
公式：
（G：格雷码，B：二进制码）
上图中0^b3 == b3，相当于保留b3
若当前二进制码为奇数 xp01111（x表示任意长度的前缀,p可能是0也可能是1）
则下一位二进制码为 xp10000 （它们的前缀相同）
根据上述公式，上面两个二进制码只有p^0和p^1会产生不同的结果，所以满足生成的相邻的格雷码只有一位二进制数不同，同理最后一位二进制码111...1生成的格雷码100...0与头部格雷码也只有一位不同，满足首尾相连。
代码实现：
vector<int> getGrayCode(int n){//生成n位格雷码序列
vector<int> ans;
for (int i = 0; i < (1 << n); i++) {
ans.emplace_back(i ^ (i >> 1));
cout << bitset<4>(ans[i]) << endl;
}
return ans;
}根据代码可得该公式也可写为：gi = i ^ (i / 2);其中i / 2向下取整。gi是序列中第i个格雷码。
二、格雷码的解码
即得到格雷码后如何将其转化为对应的二进制码。
从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。依次异或，直到最低位。依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。
公式：
（G：格雷码，B：二进制码）
下面是我对公式的一些推导：
格雷码相关例题：
题一文章来源：https://www.toymoban.com/news/detail-488908.html
题二文章来源地址https://www.toymoban.com/news/detail-488908.html
到了这里，关于格雷码的生成与解码的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
