格雷码(Gray Code)是指在一组数的编码中,任意两个相邻的代码只有一位二进制数不同,则称这种代码为格雷码。另外由于最大数和最小数之间也仅有一位数不同,即“首尾相连”,因此又称为循环码或反射码。这篇博文主要介绍怎样用递归的方式构造格雷码以及格雷码与 8421 码之间的转换。
简介
在数字系统中,通常要求代码按一定顺序变化。例如,按自然数递增计数,若采用8421码,则数 0111 变到 1000 时四位均需要变化,而在实际电路中,四位的变化不可能绝对同时发生,则计数中可能出现短暂的其他编码(1100,1111等),在特定情况下可能导致电路状态或输出错误。而使用格雷码可以避免这种错误。这也是格雷码叫循环码的原因。而叫它反射码的原因在于常见的编码生成方式是反射或镜像。
题目
题目的来源有两个,一个是最近腾讯笔试的编程题:给定一个编码位数n,用递归的方式输出这串n位格雷码,而另一题目是 LeetCode上的第 87 题,就是给出一个编码位数n,以十进制的方式输出这串 n 位格雷码。
思路
- 反射或镜像 之所以称格雷码叫反射码,是因为通过反射可以构造格雷码。下面这附图通过n的增大来体现何为反射码.
图中的虚线就是反射的反射面,也是镜像的镜面。而由 n 变化到 n+1,只需将 n 的格雷码镜像翻转后,上面的镜像前面添 0,下面的镜像前面添 1。除此之外,还可以发现以下的规律:
> 假定正常顺序是先出现 0 再出现1,那么:
> 如果第i位前面出现偶数个 1,那么第i位就是正常顺序;
> 如果第i位前面出现奇数个 1,那么第i位就是不正常顺序。
- 格雷码和 8421码的转换 其实格雷码和我们经常使用的 8421码之间是可以直接转换的,也就是说给定一个数值为 k 的 8421码可以直接得出第 k 个格雷码。当然给定一个格雷码也可以直接获得这个格雷码对应的8421码。那么这就需要知道格雷码和8421码之间的对应关系。下图将给个详细的解释。
图中第一个矩形表示的是格雷码和8421码的对应关系。
> **Tips:**
> 对于格雷码的序列有多种,这里采用的是最常见的一种方式。
图中第二个矩形表示的是格雷码和8421码之间的转换关系。由图中可以看出由格雷码转换到8421码时,有如下的对应关系: $$ 8421[0]=Gray[0]; i=0 $$$$ 8421[i]=Gray[i] \wedge Gray[i-1]; i>0 $$ 同理我们可以得到8421码到格雷码的转换,转换关系如下: $$ Gray[0]=8421[0]; i=0 $$$$ Gray[i]=\backsim (8421[i] \wedge 8421[i-1]); i>0 $$
算法说明
通过递归的方式构造格雷码
1// bin[] 存放二进制编码 2// ind 确定第ind的编码 3// sum 前ind位有多少个1 4// num 编码的位数 5void GrayCode(int bin[], int ind, int sum, int num){ 6 int i; 7 if(ind==num){ 8 // 输出显示 9 for(i=0; i<num; i++) 10 printf("%d ",bin[i]); 11 printf("\n"); 12 return; 13 }else { 14 if(sum%2==0){ 15 // 前ind位有偶数个1,正常顺序 16 bin[ind]=0; 17 GrayCode(bin,ind+1,sum,num); 18 bin[ind]=1; 19 GrayCode(bin,ind+1,sum+1,num); 20 }else{ 21 // 前ind位有奇数个1,不正常顺序 22 bin[ind]=1; 23 GrayCode(bin,ind+1,sum+1,num); 24 bin[ind]=0; 25 GrayCode(bin,ind+1,sum,num); 26 } 27 } 28}
8421码转换到格雷码
1// n 编码位数 2// returnSize 存放返回8421码数组的长度 3// return 8421码数组 4int* GrayCode(int n, int* returnSize) { 5 int i; 6 // 数组长度 7 *returnSize = 1<<n; 8 int* gray=malloc((*returnSize)*sizeof(int)); 9 for(i=0; i<*returnSize; i++){ 10 // 格雷码转换为8421码,一步到位 11 gray[i]=i^(i>>1); 12 } 13 14 return gray; 15}
举一反三
格雷码转换到8421码也可以用位运算一步解决: $$ 8421=~(Gray \wedge (Gray»1)); $$