文章目录

Gray Code (格雷码)特点产生变换方法第一种描述第二种描述 二进制->格雷码格雷码->二进制 格雷码所有位清0的步骤打印变化步骤

Gray Code (格雷码)

一种编码规则, 将1,2,3…这样的十进制数用另一种方式表示 (常用的是二进制表示). 要知道每个格雷码表示的数值是多少, 需要解码成二进制表示.

特点

相邻数字的格雷码之间只有一个二进制位不同

产生

传统的二进制表示法, 当在相邻的数字之间进行切换时, 会改变许多位. 比如3->4, 011->100, 需要改变三位, 63->64, 111111->1000000, 需要改变七位. 如果在转换过程中发生异常, 就会造成编码错误.可能的话应该尽量缩短转换过程, 因此诞生了格雷码, 相邻数字之间只需要改变一位. 贝尔实验室的Frank Gray于1940年提出.

变换方法

第一种描述

改变最右边的二进制位改变从右边数第一个二进制位为1的右边一个二进制位重复上述两步

000(1) ->001(1) ->011(2) ->010(3) ->110(4) ->111(5) ->101(6) ->100(7)

第二种描述

最右边一位可以任何时候改变如果想要改变第n位(从右边开始数), 需要第(n-1)位为1, 从第(n-2)位开始全为0 如果改变第2位, 只需要第1位(最右边一位)为1

二进制->格雷码

算法 从最右位开始, 与右边一位取异或值为该位的格雷码值

G(i) = B(i) XOR B(i+1) (0 <= i < n-1) G(i) = B(i) (i = n-1) 最右位为0

gray_code = n ^ (n >> 1);

格雷码->二进制

算法 从次左位开始, 每位与左边一位解码后的二进制值进行异或为该位解码后的二进制值. 最左位解码的二进制值就是该位的格雷码值

B(i) = G(i) (i = n-1) B(i) = G(i) XOR B(i+1) (0 <= i < n-1) (B(i) = G(i) XOR G(i+1) XOR G(i+2) XOR … XOR G(n-1), 每一位的解码值 = 该位与左边所有位的异或值) a5 a4 a3 a2 a1      a5 a4 a3 a2           a5 a4 a3                a5 a4                     a5 每次右移一位, 然后与原来的进行异或刚好可以实现, 与左边所有位进行异或的结果

int ans = 0; while(n) { ans ^= n; n = n >> 1; }

格雷码所有位清0的步骤

将格雷码转换成二进制, 对应的结果就是所有位清0需要的步骤次数, 因为格雷码相邻数字之间只需要改变一位

打印变化步骤

清零顺序 : 从左到右(递归)改变(置0或置1)第n位, 需要把第(n-1)位变为1, 第(n-2)位开始往后所有位变为0改变(置0或置1)第n位后, 需要把为清零它改变的其余位复原 void one_to_zero(string& s, int n); void zero_to_one(string& s, int n); // 字符串是从左往右0-n-1, graycode解码也需要从左到右 void one_to_zero(string& s, int n) { // 从左往右找到第一个需要翻转的1 while(n <= s.size()-1 && s[n] == '0') ++n; if(n <= s.size()-1) { // 现在n是左边第一个1, 想要归零它, 需要下一位是1, 之后全为0 // 同时不满足下面两个条件的只有n==0 // 如果下一位是0, 将它置为1, 注意下标 if(n+1 <= s.size()-1 && s[n+1] == '0') zero_to_one(s, n+1); // 如果下一位已经是1, 需要把从下下位开始的所有置为0, 注意下标 if(n+2 <= s.size()-1) one_to_zero(s, n+2); s[n] = '0'; cout<<s<<endl; // 还原 if(n <= s.size()-3) zero_to_one(s, n+2); if(n <= s.size()-2) one_to_zero(s, n+1); } } void zero_to_one(string& s, int n) { if(n <= s.size()-2 && s[n+1] == '0') zero_to_one(s, n+1); if(n <= s.size()-3) one_to_zero(s, n+2); if(s[n] == '0') { s[n] = '1'; cout<<s<<endl; } // 还原 if(n <= s.size()-3) zero_to_one(s, n+2); if(n <= s.size()-2) one_to_zero(s, n+1); } int main() { string s = "1010"; cout<<s<<endl; one_to_zero(s, 0); return 0; } 1010 1110 1111 1101 1100 0100 0101 0111 0110 0010 0011 0001 0000 Program ended with exit code: 0