`
gaofen100
  • 浏览: 1227691 次
文章分类
社区版块
存档分类
最新评论

格雷码的实现 (google 面试题)

 
阅读更多
问题:产生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位元格雷码产生的。

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

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

这是一道google 的面试题,以上代码均是网友peking2 和 SEwind520写成。原题还要求把二进制码转成十进制数。
参考:http://www.mitbbs.com/article_t/JobHunting/32003667.html

分享到:
评论

相关推荐

    格雷码图片生成与保存C++实现代码

    // 实现格雷码生成逻辑 } // 格雷码转RGB std::vector<uint8_t> gray_to_rgb(uint8_t gray) { // 将格雷码转换为RGB } // 保存图片 void save_image(const std::vector<uint8_t>& pixels, int width, int height...

    C语言写的产生格雷码的简单程序

    下面以C语言为例,演示如何实现这个简单的格雷码生成程序: ```c #include // 定义格雷码生成函数 void generate_gray(int n) { int grayCode = 0; for (int i = 0; i (1 ); i++) { // 循环遍历2^n个可能的二...

    生成格雷码图案matlab程序

    总的来说,这个MATLAB程序实现了格雷码的生成与可视化,而提供的.bmp文件可能是在特定分辨率下生成的格雷码图像,适用于结构光系统的应用。这种技术在机器人导航、工业检测、医学成像等领域都有广泛应用。通过理解和...

    基于PLC程序实现格雷码转换成二进制码.pdf

    基于PLC程序实现格雷码转换成二进制码的知识点如下: 1. 绝对位置编码器的应用 绝对位置编码器在自动化技术与应用中被广泛应用于角度、长度测量和定位控制,特别是在工业系统中。它能够提供每个位置的绝对唯一编码...

    格雷码问题 分治法产生n位的格雷码

    格雷码,又称格雷编码,是一种二进制数字系统,它的特点是任意两个相邻的代码之间仅有一位不同。这种编码在通信、计算机科学、电子工程等领域有着广泛应用,尤其是在错误检测和减少信号传输中的误码率方面。格雷码的...

    格雷码生成程序

    格雷码生成程序 在数字逻辑设计中,格雷码是一种特殊的编码方法,它使得每对连续的编码之间只有一个数位的...在本文中,我们介绍了格雷码的基本概念、生成方法和 C++ 实现,希望能够帮助您更好地理解和应用格雷码。

    分治法求格雷码的C语言代码

    本文介绍了一种利用分治法求解格雷码(Gray Code)的方法,并提供了相应的C语言代码实现。格雷码是一种二进制数字系统,在该系统中,两个连续的数值其二进制表示仅有一位不同。 #### 描述解析 这段描述简要介绍了...

    C语言实现格雷码生成代码

    本文通过对给定的C语言代码进行了详细解析,介绍了格雷码的基本概念及其在C语言中的实现方法。格雷码因其独特的性质,在许多实际应用中都有重要的作用。通过学习本文提供的知识,可以帮助读者更好地理解和掌握格雷码...

    8位二进制码转化为8位格雷码(源码)

    8位格雷码的生成可以通过一种简单的逐位翻转规则实现,即从低位到高位,每一位的格雷码等于它前一位二进制码的异或(XOR)结果。对于8位二进制码,转换过程如下: 1. 将最左边的位(最高位)复制到格雷码中。 2. ...

    二进制转格雷码MATLAB程序

    在MATLAB中实现二进制转格雷码的程序,主要是利用了格雷码与二进制码之间的转换规则。这个转换过程可以通过一系列数学操作完成,例如模2加法或者位翻转。MATLAB作为一种强大的数值计算和数据可视化工具,提供了丰富...

    格雷码--2021.09.06(E).pdf

    格雷码的实现可以分为编码和解码两个过程,编码过程是将二进制数转换为格雷码,解码过程是将格雷码转换回二进制数。 格雷码的优点 格雷码具有自适应、可逆和非重叠等优点,广泛应用于数字信号处理、数据存储和传输...

    结构光正弦条纹 格雷码图案matlab生成程序

    3. 应用格雷码编码,改变每个条纹的相位,通常会通过位操作或循环实现。 4. 将所有编码后的正弦条纹组合成一个序列,形成多帧图像。 5. 可能还包括对图像进行平滑处理、边缘增强或者噪声去除等预处理步骤,以提高...

    S7-1200 格雷码转成10进制数据.rar

    在SCL程序中实现格雷码到10进制的转换,首先需要理解格雷码的特性。一个n位格雷码可以转换为相应的n位10进制数,通过以下步骤: 1. **位翻转**:对于n位格雷码,从最低位开始,逐位与它的前一位进行异或操作。这样...

    VHDL实验二 基于 VHDL 格雷码编码器的设计

    -- 实现格雷码转换逻辑 gray_out(0) (0); gray_out(1) (0) xor binary_in(1); gray_out(2) (1) xor binary_in(2); gray_out(3) (2) xor binary_in(3); end process; end Behavioral; ``` 在这个结构体中,`...

    十进制转普通二进制和格雷码

    本文将深入探讨如何将十进制数转换为普通二进制和格雷码,并使用MATLAB来实现这一过程。同时,我们将讨论如何从日志文件中提取特定数据列,并将转换后的结果保存到Excel表格中。 首先,我们要理解十进制、普通二...

    altera官方格雷码计数器,verilog代码编写

    4. **格雷码转换**:设计一个格雷码到二进制或者二进制到格雷码的转换模块,这通常通过异或操作实现。在计数器内部,每次状态变化时,需要根据当前状态和下一状态计算出格雷码的变化。 5. **组合逻辑**:使用...

    二进制格雷码与自然二进制码的互换

    //以上代码实现了 unsigned int 型数据到格雷码的转换,最高可转换32 位自然二进制码,超出 32 位将溢出。 static int DecimaltoGray( int x) { return x^(x>>1); } //以上代码实现了 int 型数据到格雷码的转换,...

    格雷码的进制转换

    这两个文件很可能是实现格雷码转换的C++源代码文件。`graycodesolution.cpp` 包含了具体的功能实现,而`graycodesolution.h` 可能定义了相关的函数原型、类结构或者常量,以便于其他模块调用这些格雷码转换的函数。...

    格雷码生成算法

    通过以上分析,我们可以看出,该段代码实现了基于递归的格雷码生成算法,通过简单的数学运算和逻辑判断,有效地生成了指定长度的格雷码序列。这种方法不仅直观易懂,而且执行效率较高,是学习和应用格雷码生成算法的...

Global site tag (gtag.js) - Google Analytics