格雷码的实现

http://blog.csdn.net/beiyeqingteng/article/details/7044471

问题:产生n位元的所有格雷码。

格雷码(Gray Code)是一个数列集合,每个数使用二进位来表示,假设使用n位元来表示每个数字,任两个数之间只有一个位元值不同。

例如以下为3位元的格雷码: 000 001 011 010 110 111 101 100 。

如果要产生n位元的格雷码,那么格雷码的个数为2^n.

假设原始的值从0开始,格雷码产生的规律是:第一步,改变最右边的位元值;第二步,改变右起第一个为1的位元的左边位元;第三步,第四步重复第一步和第二步,直到所有的格雷码产生完毕(换句话说,已经走了(2^n) - 1 步)。

用一个例子来说明:

假设产生3位元的格雷码,原始值位 000

第一步:改变最右边的位元值: 001

第二步:改变右起第一个为1的位元的左边位元: 011

第三步:改变最右边的位元值: 010

第四步:改变右起第一个为1的位元的左边位元: 110

第五步:改变最右边的位元值: 111

第六步:改变右起第一个为1的位元的左边位元: 101

第七步:改变最右边的位元值: 100

如果按照这个规则来生成格雷码,是没有问题的,但是这样做太复杂了。如果仔细观察格雷码的结构,我们会有以下发现:

1、除了最高位(左边第一位),格雷码的位元完全上下对称(看下面列表)。比如第一个格雷码与最后一个格雷码对称(除了第一位),第二个格雷码与倒数第二个对称,以此类推。

2、最小的重复单元是 0 , 1

000 001 011 010 110 111 101 100

所以,在实现的时候,我们完全可以利用递归,在每一层前面加上0或者1,然后就可以列出所有的格雷码。

比如:

第一步:产生 0, 1 两个字符串。

第二步:在第一步的基础上,每一个字符串都加上0和1,但是每次只能加一个,所以得做两次。这样就变成了 00,01,11,10 (注意对称)。

第三步:在第二步的基础上,再给每个字符串都加上0和1,同样,每次只能加一个,这样就变成了 000,001,011,010,110,111,101,100。

好了,这样就把3位元格雷码生成好了。

如果要生成4位元格雷码,我们只需要在3位元格雷码上再加一层0,1就可以了: 0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1110,1010,0111,1001,1000.

也就是说,n位元格雷码是基于n-1位元格雷码产生的。

如果能够理解上面的部分,下面部分的代码实现就很容易理解了。

[java] view plaincopy

  1. public String[] GrayCode(int n) {  
  2. // produce 2^n grade codes
  3.     String[] graycode = new String[(int) Math.pow(2, n)];  
  4. if (n == 1) {  
  5.         graycode[0] = "0";  
  6.         graycode[1] = "1";  
  7. return graycode;  
  8.     }  
  9.     String[] last = GrayCode(n - 1);  
  10. for (int i = 0; i < last.length; i++) {  
  11.         graycode[i] = "0" + last[i];  
  12.         graycode[graycode.length - 1 - i] = "1" + last[i];  
  13.     }  
  14. return graycode;  
  15. }  

格雷码还有一种实现方式是根据这个公式来的 G(n) =  B(n) XOR B(n+1), 这也是格雷码和二进制码的转换公式。代码如下:

[java] view plaincopy

  1. public void getGrayCode(int bitNum){  
  2. for(int i = 0; i < (int)Math.pow(2, bitNum); i++){  
  3. int grayCode = (i >> 1) ^ i;  
  4.         System.out.println(num2Binary(grayCode, bitNum));  
  5.     }  
  6. }  
  7. public String num2Binary(int num, int bitNum){  
  8.     String ret = "";  
  9. for(int i = bitNum-1; i >= 0; i--){  
  10.         ret += (num >> i) & 1;  
  11.     }  
  12. return ret;  
  13. }  

这是一道google 的面试题,以上代码均是网友peking2 和 SEwind520写成。原题还要求把二进制码转成十进制数。

参考:http://www.mitbbs.com/article_t/JobHunting/32003667.html

转载请注明出处:blog.csdn.net/beiyeqingteng

版权声明:本文为博主原创文章,未经博主允许不得转载。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏聊聊技术

原 HDOJ 1002 A + B Pro

30211
来自专栏机器学习算法与Python学习

Python:numpy总结(4)

31、chr函数,获取指定的字符 例子: #获取指定的字符for i in range(65,70): print str(chr(i))...

3919
来自专栏Petrichor的专栏

python: center、ljust、rjust 函数

1691
来自专栏窗户

awk的递归

  想来惭愧,之前写的一篇文章《用awk写递归》里多少是传递了错误的信息。虽然那篇文章目的上是为了给出一种思路,但实际上awk是可以支持函数局部变量的。

952
来自专栏Python小屋

针对递归函数的优化与Python修饰器实现

我们围绕一个数学问题来说明本文的思想,组合数C(n,i),也就是从n个元素中任选i个,共有多少种选法。当然,这个问题有很多种求解方法,例如【最快的组合数算法之P...

4139
来自专栏夏时

PHP 常用函数大全

4842
来自专栏Redis源码学习系列

Redis源码学习之字典

在字典结构体中,包含了一组字典函数(dictType),通过封装的方法处理对应的操作,通常在字典初始化的时候对其进行配置。

2771
来自专栏Laoqi's Linux运维专列

python3–内置模块Ⅱ

4828
来自专栏Golang语言社区

使用 Go 语言学会 Tensorflow

Tensorflow 并不是一个专门用于机器学习的库,相反的,它是一个通用的用于图计算的库。它的核心部分是用 C++ 实现的,同时还有其它语言的接口库。Go 语...

4542
来自专栏用户2442861的专栏

限制QLineEdit的数值输入范围

QLineEdit *lineEdit = new QLineEdit(this);

9791

扫码关注云+社区

领取腾讯云代金券