1 格雷码：
1.1 格雷码引言：
在数字系统中，常要求代码按一定顺序变化。
在机器视觉里面，编码结构光也是按照一定的顺序进行变化，最常用的就是Binary,但是，二进制的纯粹的编码，由于二进制的进制关系(每个位是有权的），如果发生一个错码（在机器视觉里面，错码的发生可能是一个背景的干扰，也可能是测试物体的一个比较陡峭的轮廓变更），一个错码往往他的数字权重不是一位，比如二进制的最高为，错了一位，那么就是整个数值发生一半的变化。
去掉权重的好处就是，如果模拟量或者是采样的数据发生了一个微小的变化，在整个测量的范围内，这个微小的变化都只能变更一个格雷码数位，而不论这个测量的数值位于整个测量量程的哪个位置：
【案】在上面这个例子中，假设测量的量程为16，我们测量到7和8之间的模拟量，你看看二进制，红色表示要变更所有的数位来表示，而格雷码只要变更一位。
那么，在我们表示这个数据的时候，二进制码所有的位都必须不能出错，否则数据会大变化。而格雷码就不会出现这个问题。
后来，弗兰克·格雷（Frank Gray，-）专利“Pulse Code Communication” 发明了一种新的顺序编码的方式，这个方式也是每个数值是唯一的二进制标识，但是，每个相邻的位只有一个位值的变化，这样就极大的减少了测量可能发生误差。
1.2 格雷码的定义：
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。
格雷码是一种具有反射特性和循环特性的单步自补码，其循环和单步特性消除了随机取数时出现重大错误的可能，其反射和自补特性使得对其进行求反操作也非常方便，所以，格雷码属于一种可靠性编码，是一种错误最小化的编码方式，因此格雷码在通信和测量技术中得到广泛应用。
Gray Code(格雷码) C++多方法实现_越前浩波的博客-CSDN博客
3位格雷码的顺序编码_几种简单的编码（为什么使用ASCII码）_乔拉爵士的博客-CSDN博客
1.3 认识格雷码
下为3位元的Gray Code：Gray Code是一个数列集合，每个数使用二进位来表示，假设使用n位元来表示每个数好了，任两个数之间只有一个位元值不同
000 001 011 010 110 111 101 100
1.3.1 位元
位元就是数列的基础数是由几个二进位数来表示，就是几个位元。
上面的例子里面：000 是3个二进制数，那么就是3个位元，那么2^3 = 8,总共8个位值
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
上面，0000 等是4个 二进制数，那么就是4个位元，那么4^3 = 16,总共16个位值
1.3.2 （格雷）码值
001 就是一个码值
2 格雷码的生成：
2.1 方法1：按照定义排列生成格雷码
回到前面的3位元的格雷码：
000 001 011 010 110 111 101 100
如果推广到N个位元，那么码值的数量应该是2^N个
2.1.1 产生的基本规律原则和标准做法
其实就是3个步骤，
第一步，改变最右边的位元值；
第二步，改变右起第一个为1的位元的左边位元；
第三步，第四步重复第一步和第二步，直到所有的格雷码产生完毕（换句话说，已经走了(2^n) – 1 步）。
举例3位元的产生步骤：
2.1.2 实现算法如下：
#include
#include
#define MAXBIT 20 #define TRUE 1 #define CHANGE_BIT(x) x = ((x) == '0' ? '1' : '0') #define NEXT(x) x = (1 - (x)) int main(void) { char digit[MAXBIT]; int i, bits, odd; printf("输入位元数："); scanf("%d", &bits); for(i = 0; i < bits; i++) { digit[i] = '0'; printf("0"); } printf("\n"); odd = TRUE; while(1) { if(odd) CHANGE_BIT(digit[0]); else { // 计算第一个1的位置 for(i = 0; i < bits && digit[i] == '0'; i++) ; if(i == bits - 1) // 最后一个Gray Code break; CHANGE_BIT(digit[i+1]); } for(i = bits - 1; i >= 0; i--) printf("%c", digit[i]); printf("\n"); NEXT(odd); } return 0; }
方法2：
///产生n位格雷码(直接排列方法构建) void generateGraycode2(int n) { int i; char code[20]; for (i = 0; i < n; i++) code[i] = '0'; code[n] = '\0'; printf("%s\n", code); while (1) { if (code[n - 1] == '0') code[n - 1] = '1'; else code[n - 1] = '0'; printf("%s\n", code); i = n - 1; while (code[i] == '0') i--; if (i == 0) break; if (code[i - 1] == '0') code[i - 1] = '1'; else code[i - 1] = '0'; printf("%s\n", code); } } 方法3：
vector
grayCode(int n) { int count = 1 << n; vector
res(count,0); for(int i = 1 ; i < count; i ++) { int cur = res[i - 1]; if(i % 2 == 1) cur = cur ^ 1; else { int k = 0; while(((cur >> k) & 1) == 0) k ++; cur = cur ^ (1 << (k + 1)); } res[i] = cur; } return res; }
C++经典算法题-格雷码（Gray Code）_逍遥云恋-CSDN博客_c++格雷码
2.2 方法2：通过二进制和格雷码的转码规律生成：
格雷码（从零基础讲解，C++版）_不负AC不负卿的博客-CSDN博客
Gray Code(格雷码) C++多方法实现_越前浩波的博客-CSDN博客
观察上表，我们可以得出格雷码和二进制码之间的基本换算逻辑如下：
2.2.1 二进制转码为格雷码（编码）
原理：如果二进制码字的第 i 位和 i+1 位（从右边开始数）相同，则对应的格雷码的第i位为0，否则为1（当i+1=n时，二进制码字的第n位被认为是0，即第n-1位不变）
/*编码模板 */ #include
using namespace std; int gray_encode(int num) { return num ^ (num >> 1); // >>是位移运算符，^是异或运算符 }
方法2：
class Solution { public: vector
grayCode(int n) { int num = 1 << n; vector
ret; ret.reserve(num); for(int i = 0; i < num; i++) { ret.push_back(i ^ (i >> 1)); } return ret; } };
2.2.1 格雷码转成二进制（解码）
原理：从左边第二位起，将每位与左边一位解码后的值进行异或，作为该位解码后的值（最左边一位依然不变），直到最低位。
这里因为转成二进制的权重的位，所以要取对数log，并以2为底，用数值去除log2
/*解码模板 */ #include
// log对数函数需要用到的头文件 #include
using namespace std; int gray_decode(int num) { int head; if(!num) return 0; head = 1 << int(log(num) / log(2)); //C++没有直接以2为底的对数，我们创造一个以2为底的对数 return head + gray_decode((num^head) ^ (head>>1));
2.3 镜像排列生成格雷码（对称法）
格雷码编解码学习(一)：格雷码编码原理与C++代码实现_Color Space的博客-CSDN博客
上面这个列表，分别给出位元为1,2,3的三组格雷码，其中灰色的部分是镜像分割线，黑色的格雷码码字和蓝色的格雷码码字是针对镜像分割线对称的。
算法原理：
2.3.1 实现算法1，C++,二维数组
template
void recursive::grayCodeGeneration(T (*list)[N],std::size_t size)const{ if(size==1){//最后需要翻转输出 list[0][size-1]=0; list[1][size-1]=1; } else{ grayCodeGeneration(list,size-1); //下面做的是对称翻转 for(int i= std::pow(2,size-1),j=std::pow(2,size)-1;i < std::pow(2,size);++i) for(int k = 0;k
pow 就是求某数的指数的函数
2.3.2 实现算法2，C++,
C++ 生成代码如下：
#include
#include
#include
using namespace std; ///产生n位格雷码(镜像排列方法构建) vector
generateGraycode(int n) { vector
nGraycode; if (n == 1) { nGraycode.push_back("0"); nGraycode.push_back("1"); } else { vector
mid_ans = generateGraycode(n - 1); for (vector
::iterator iter = mid_ans.begin(); iter != mid_ans.end(); ++iter) { string temp = *iter; temp.insert(0, "0"); nGraycode.push_back(temp); } for (int i = mid_ans.size() - 1; i >= 0; --i) { string temp = mid_ans[i]; temp.insert(0, "1"); nGraycode.push_back(temp); } } return nGraycode; } int main() { vector
nGraycode; nGraycode = generateGraycode(3); for(int i = 0; i < nGraycode.size(); i++) cout << nGraycode.at(i) << endl; return 0; }
C++ 另一种表述为：
#include
#include
using namespace std; vector
getGray(int n) { // write code here vector
result; if(n == 1){ result.push_back("0"); result.push_back("1"); return result; }else{ result = getGray(n-1); int currentsize = (int)result.size(); for(int i = 0; i < currentsize; i++){ result.push_back(result.at(i)); } for(int i = 0; i < currentsize; i++){ result.at(i) = "0" + result.at(i); } for(int i = currentsize; i < (int)result.size(); i++){ result.at(i) = "1" + result.at(i); } return result; } } int main(){ vector
v; v = getGray(2); for(int i = 0; i < v.size(); i++){ cout << v.at(i) << " "; } cout << endl; return 0; }
实现算法另一种表述、
[C++]LeetCode: 86 Gray Code （格雷码）_cindy_niu的专栏-CSDN博客
class Solution { public: vector
grayCode(int n) { vector
ret{0}; for(int i = 0; i < n; i++) { int curCnt = ret.size(); //把当前数字按照逆序顺序添加到ret中 while(curCnt) { curCnt--; int curNum = ret[curCnt]; curNum += (1 << i); ret.push_back(curNum); } } return ret; } };
2.3.3 实现算法3，C，二维数组
c 语言表述：
算法实验-格雷码_中位数问题 分治法-CSDN博客_格雷码分治
//用分治策略设计一个算法对任意的n构造相应的Gray码。 #include
#include
using namespace std; //构造n位格雷码，格雷码数m个 //利用格雷码除第一位外对称的原理 char countgary(int n) { int m = 1; for (int a = 0; a < n; a++) m = m * 2; char garycode = new char *[m]; for (int a = 0; a < m; a++) garycode[a] = new char[n]; if (n == 1) { garycode[0][0] ='0'; garycode[1][0] ='1'; return garycode; }//1的格雷码为0和1 char temp = countgary(n - 1); for (int a = 0; a < m / 2; a++) { garycode[a][0] = '0'; garycode[a + m / 2][0] = '1'; //m个格雷码前一半的第一位为0，后一半第一位为1 for (int b = 1; b < n; b++) { garycode[a][b] = temp[a][b - 1]; garycode[m-a-1][b] = temp[a][b - 1]; //将n-1的格雷码呈上下对称放在n格雷码的前半段和后半段 } } return garycode; } int main() { ifstream f1("C:\\Data\\3.txt"); ofstream f2("C:\\Data\\4.txt"); int n; int m = 1; f1 >> n; for (int a = 0; a < n; a++) m = m * 2; char garycode = countgary(n); for (int a = 0; a < m; a++) { for (int b = 0; b < n; b++) { f2 << garycode[a][b] << "\t"; cout << garycode[a][b] << "\t"; } cout << "\n"; f2 << "\n"; } f1.close(); f2.close(); return 0; }
格雷码的算法实现_(っ°Д°)っ ＃-CSDN博客_格雷码算法
2.4 正序逆序生成格雷码（对称法）
在正序的基础上将1左移n-1位，再加在逆序上，即得green code 格雷码。
算法返回的是10进制的值
class Solution { public: vector
grayCode(int n) { vector
res; int c=1; res.push_back(0); for(int i=0;i
=0;j--) res.push_back(res[j]+c); c<<=1; } return res; } };
C++经典算法题-格雷码（Gray Code）_逍遥云恋-CSDN博客_c++格雷码
(1条消息) [C++]LeetCode: 86 Gray Code （格雷码）_cindy_niu的专栏-CSDN博客
本文重要参考：
C++经典算法题-格雷码（Gray Code）_逍遥云恋-CSDN博客_c++格雷码
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/220248.html原文链接：https://javaforall.net
