算法学习(6)

#算法学习(6)| 来源: 网络整理| 查看: 265

　　在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。在数字系统中，常要求代码按一定顺序变化。例如，按自然数递增计数，若采用8421码，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同时发生，则计数中可能出现短暂的其它代码（1100、1111等）。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。格雷码有多种编码形式。

格雷码有多种编码形式十进制数4位自然二进制码4位典型格雷码十进制余三格雷码十进制空六格雷码十进制跳六格雷码步进码 0 0000 0000 0010 0000 0000 00000 1 0001 0001 0110 0001 0001 00001 2 0010 0011 0111 0011 0011 00011 3 0011 0010 0101 0010 0010 00111 4 0100 0110 0100 0110 0110 01111 5 0101 0111 1100 1110 0111 11111 6 0110 0101 1101 1010 0101 11110 7 0111 0100 1111 1011 0100 11100 8 1000 1100 1110 1001 1100 11000 9 1001 1101 1010 1000 1000 10000 10 1010 1111 ---- ---- ---- ---- 11 1011 1110 ---- ---- ---- ---- 12 1100 1010 ---- ---- ---- ---- 13 1101 1011 ---- ---- ---- ---- 14 1110 1001 ---- ---- ---- ---- 15 1111 1000 ---- ---- ---- ---- 　　表中典型格雷码具有代表性。若不作特别说明，格雷码就是指典型格雷码，它可从自然二进制码转换而来。转换方法递归生成码表这种方法基于格雷码是反射码的事实，利用递归的如下规则来构造： 1位格雷码有两个码字 (n+1)位格雷码中的前2n个码字等于n位格雷码的码字，按顺序书写，加前缀0 (n+1)位格雷码中的后2n个码字等于n位格雷码的码字，按逆序书写，加前缀1 n+1位格雷码的集合 = n位格雷码集合(顺序)加前缀0 + n位格雷码集合(逆序)加前缀1 2位格雷码3位格雷码4位格雷码4位自然二进制码 00 01 11 10 000 001 011 010 110 111 101 100 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

异或转换二进制码→格雷码（编码）：此方法从对应的n位二进制码字中直接得到n位格雷码码字，步骤如下：对n位二进制的码字，从右到左，以0到n-1编号如果二进制码字的第i位和i+1位相同，则对应的格雷码的第i位为0，否则为1（当i+1=n时，二进制码字的第n位被认为是0，即第n-1位不变）公式表示：

（G：格雷码，B：二进制码）

例如：二进制码0101，为4位数，所以其所转为之格雷码也必为4位数，因此可取转成之二进位码第五位为0，即0 b3 b2 b1 b0。 0 xor 0=0，所以g3=0 0 xor 1=1，所以g2=1 1 xor 0=1，所以g1=1 0 xor 1=1，所以g0=1 因此所转换为之格雷码为0111

其实，从上述格雷码异或转换的方法可以得到一个简单易行的算法，例如，对于一个2进制比特不超过32位的整数x，它的格雷码即可表示为 (x>>1)^x。

算法演示：

#include #include void print_bin(unsigned int value,char *tail); //打印一个数字的bit位 int main(int argc,char* argv[]) { unsigned int temp; for(unsigned int i=0;i>1)^i; //转换代码仅仅一行，很简单 print_bin(temp,"\n"); } return 0; } void print_bin(unsigned int value,char* tail) { for(int i=31;i>=0;i--) { printf("%d",(value>>i)&1); } if(tail) { printf("%s",tail); } }

编译运行结果：

root@javis:~/Documents/Code$ gcc test.c -std=c99 -o test.out root@javis:~/Documents/Code$ ./test.out 0 :00000000000000000000000000000000 1 :00000000000000000000000000000001 2 :00000000000000000000000000000011 3 :00000000000000000000000000000010 4 :00000000000000000000000000000110 5 :00000000000000000000000000000111 6 :00000000000000000000000000000101 7 :00000000000000000000000000000100 8 :00000000000000000000000000001100 9 :00000000000000000000000000001101 10 :00000000000000000000000000001111 11 :00000000000000000000000000001110 12 :00000000000000000000000000001010 13 :00000000000000000000000000001011 14 :00000000000000000000000000001001 15 :00000000000000000000000000001000

【本文地址】

算法学习(6)

算法学习(6)

今日新闻

推荐新闻