格雷码

字数统计: 730阅读时长: 2 min

 2019/11/26 

定义

格雷码（循环二进制单位距离码）是任意两个相邻数的代码只有一位二进制数不同的编码，它与奇偶校验码同属可靠性编码。

格雷码（Gray code）是由贝尔实验室的Frank Gray在1940年提出，用于在PCM（脉冲编码调变）方法传送讯号时防止出错。

例如2位的格雷码，排列为00，01，11，10。这个排列中的四个数字，每相邻两个二进制序列都仅有一位不同。可以扩展到n位格雷码，而且格雷码的排列不仅有一种。例如上面2位的格雷码，还可以是00，10，11，01。

实现

实现格雷码有两种方法，递归和数学方法。

递归的方法是：

1位格雷码只有0，1;

n位格雷码的序列为k1,k2…kn;

n+1位格雷码的序列为0k1,0k2…0kn,1kn…1k2,1k1。就是先把前n位的格雷码高位补零，然后把前n位格雷码倒序，再高位补1衔接。

代码如下：

vector<int> grayCode(int n) {
        if(n==0)
        {
            vector<int> res;
            res.push_back(0);
            return res;
        }
        vector<int> tmp = grayCode(n-1);
        vector<int> res;
        for(int i = 0; i < tmp.size(); ++i)
        {
            int m = tmp[i]*2;
            res.push_back(m);
        }
        for(int i = tmp.size()-1; i>=0; --i)
        {
            int m = tmp[i]*2+1;
            res.push_back(m);
        }
        return res;
    }

数学方法：

一个二进制数n对应的格雷码G(n),是n与n-1异或的值

int g(int n)
{ 
    return n ^ (n >> 1); 
}

int rev_g(int g) {
  int n = 0;
  for (; g; g >>= 1) n ^= g;
  return n;
}

用途

格雷码由于相邻两个数字只差一位，可以用来降低转态转换出错的概率。

如果一次状态变换改变3个比特，那么3个比特变化不是原子的，在他们变换的中间态，例如只有2个比特变了的时，此时读取数据会读到错误的状态。但是使用格雷码，每次只变更1个比特。是最小差异。能够避免读错。这是格雷码最初的应用。

除了容错外，格雷码还能用来实现汉诺塔移动策略。

具体的方法是：

假设汉诺塔n个盘子，从小到大编号为1~n。

三个柱子A、B、C，盘子从A移动到C。

如果汉诺塔有n个盘子，则n位格雷码，自左至右编号为第n位，第n-1位…第2位，第1位。

每次格雷码变更的位序号数k，则是第k的盘子移动。除了第一个盘子，其他编号的盘子移动的位置是固定的。

如果盘子数是偶数，则最小的盘子先移动到B，如果盘子数是奇数，则最小的盘子移动到C。后面按照格雷码变更的位置移动。

原文作者：owenzhang

原文链接：https://yunpengzhang.github.io/2019-%E6%A0%BC%E9%9B%B7%E7%A0%81/

发表日期：November 26th 2019, 10:00:03 am

更新日期：November 26th 2019, 10:00:03 am

Next Post

多阶Hash算法
Previous Post

简单高效的排行榜算法——树状数组

CATALOG

1. 定义
2. 实现
3. 用途