C++ 数学与算法系列之认识格雷码

1. 前言

程序中所涉及到的任何数据，计算机底层均需转换成二进制数值后方可存储，这个过程也称为编码。反之，把底层二进制数据转换成应用数据称为解码，

不同的数据类型需要不同的编（解）码方案，如音频数据编码、视频数据编码、图形数据编码……

即使是同类型的数据，根据不同的应用场景，也有多种编码方案可选。如字符编译就有ASCII、UTF-8、哈夫曼编码以及本文将要讲解的格雷码。

讲解格雷码之前，首先了解一下格雷码的定义：

• 对数据编码后，若任意两个相邻的码值间只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。
• 由于最大数与最小数之间也仅只有一位数不同，即首尾相连，又称循环码或反射码。

格雷码的优点：

一种编码的出现，一定是为了弥补已有编码的不足，这里以ASCII编码中的A~Z字符的码值开始研究：

G的编码是01000111，H的编码是01001000。

从宏观的计数角度而言，计数增长仅为1，但是有 4 个数据位发生了变化。从底层的存储硬件而言，每一位都需由电路控制 ，宏观世界里4 位数字的变化会引起微观世界里多个电路门变化，且不可能同时发生。

意味着中间会短暂出现其它代码，则在电流不稳或特定因素的影响下可能会导致电路状态变化错误的概率会增加很多。

而格雷码相邻编码只有一个数据位的变化，相对于计数编码，显然易见，其安全性和容错性要高很多。

格雷码可以有多种编码形式。如下图所示：

表中典型格雷码具有代表性，一般说格雷码就是指典型格雷码，它可从自然二进制码转换而来。

Tips： 格雷码是一种变权码，每一位码没有固定的大小，很难直接进行比较大小和算术运算。

2. 编码方案

2.1 递归实现

这种方法基于格雷码是反射码的事实，可以对直接使用递归算法构造。

流程如下：

• 1位格雷码有两个编码。

• (n+1)位格雷码中的前2^n个编码等于n位正序格雷码的前面 加0。

• (n+1)位格雷码中的后2^n个编码等于n位逆序格雷码的前面加1。

编码实现：

#include 
#include 
using namespace std;
/*
*实现格雷编码
*/
vector grayCode(int num) {
    //存储格雷码
	vector vec;
	if(num==1) {
        //出口：1位格雷码是已知的
		vec.push_back("0");
		vec.push_back("1");
		return vec;
	}
    //得到低位格雷码
	vector vec_= grayCode(num-1);
	//对低位格雷码正向遍历，添加前缀 0
	vector::iterator begin=vec_.begin();
	vector::iterator end=vec_.end();
	for(; begin!=end; begin++) {
		vec.push_back("0"+*begin);
	}
	//对低位格雷码反向遍历,添加前缀 1 
	vector::reverse_iterator rbegin=vec_.rbegin();
	vector::reverse_iterator rend=vec_.rend();
	for(; rbegin!=rend; rbegin++) {
		vec.push_back("1"+*rbegin);
	}
	return vec;
}
//测试
int main(int argc, char** argv) {
	vector vec=grayCode(4);
    cout<<"4 位格雷码："<

4 位格雷码：
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include 
#include 
using namespace std;
/*
*异或转换格雷编码
*/
void  yhGrayCode(int num) {
    //二进制
	vector vec;
    //格雷码
	vector  gc;
	//存储进位值
	int jinWei=0;
    //初始二进制的每一位为 0
	for(int i=0; i=0; i--) {
			vec[i]	= vec[i]+jinWei;
			jinWei= vec[i] / 2;
			vec[i]=vec[i] % 2;
		}
	}
}
//仅测试 4 位格雷码
int main(int argc, char** argv) {
	cout<<"\ 4 位格雷码："<