Skip to content

Latest commit

 

History

History
 
 

088. Gray Code

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

这道题应该是考察 grey code 的概念。


格雷码是怎么来的?二进制数011,加1的时候变成100,在老式装置上,这意味着三个位元都要转动,增加了出错的几率。在这种情况下,人们发明了格雷码。

所以很显然,格雷码的特征是:每次加一,只改变一位

直观的看,三位格雷码列表:

十进制 格雷码 二进制
0 000 000
1 001 001
2 011 010
3 010 011
4 110 100
5 111 101
6 101 110
7 100 111

这个顺序与题意的顺序一致,可以看到最后一个格雷码100与第一个格雷码000也只相隔一位。这种也叫做循环格雷码。

我们是根据什么依据产生这种格雷码的呢?从这幅图应该可以看出端倪: generate grey code

首先是上下对称复制,然后分别冠以0与1. 随着位数的增加,不断重复这个过程。

这样的格雷码与二进制之间有着这样一个公式:从最右边一位起,依次将每一位与左边一位异或(XOR),作为对应格雷码该位的值,最左边一位不变(相当于左边是0)。

简单表达为:the nth Gray code is obtained by computing (n/2) ^ n.

我的解法也是利用了这个公式。但对于该公式的证明,我却没有想的很明白。