Gray码

Gray码：

格雷码是一个数列集合，相邻两数间只有一个位元改变，为无权数码，且格雷码的顺序不是唯一 的

二进制转化为Gray码：

简便的算法： 二进制数右移一位，最高为补零，之后与原二进制值按位异或得到格雷码

//二进制--->Gray码 int binary2gray(int b){ return b ^ (b >> 1); }

Gray码转为二进制：

//Gray码 ---> 二进制 int gray2bin(int g){ int len = 0; int tmp = g; while(tmp > 1){ tmp = tmp>>1; ++len; } //printf("len = %d\n", len); int b = 1<<len; for(int i = len-1; i >= 0; --i){ int m = (g&(1<<i)) ^ ((b>>1)&(1<<i)); if(m) b |= 1 << i; } return b; }

生成n位Gray码：

将Gray码分成上下两部分，除了最高位（左边第一位），格雷码的位元完全上下对称 比如第一个格雷码与最后一个格雷码对称（除了第一位），第二个格雷码与倒数第二个对称，以此类推。

//生成n位的gray码 void gray(int n){ if(n == 1){ G[1] = 0; G[2] = 1; return;} gray(n - 1); for(int k = 1<<(n-1), i = k; i > 0; --i) G[2*k - i + 1] = G[i] + k;//除最高位外, 上下对称, 下面的只需要在最高位补1,对于整数来说就是 + 1<<(n-1) }

输出的时候，在前面补0即可：

void display(int n){ char str[32]; int m = 1<<n; for(int i = 1; i <= m; ++i){ _itoa(G[i], str, 2);//将G[i]的二进制转为字符串存在str for(int i = 0; i < n-strlen(str); ++i) printf("0"); printf("%s\n", str); } }

完整代码：

#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int INF = 0x3f3f3f3f; typedef long long LL; const int maxn = 1<<10; int G[maxn]; //生成n位的gray码 void gray(int n){ if(n == 1){ G[1] = 0; G[2] = 1; return;} gray(n - 1); for(int k = 1<<(n-1), i = k; i > 0; --i) G[2*k - i + 1] = G[i] + k;//除最高位外, 上下对称, 下面的只需要在最高位补1,对于整数来说就是 + 1<<(n-1) } void display(int n){ char str[32]; int m = 1<<n; for(int i = 1; i <= m; ++i){ _itoa(G[i], str, 2); for(int i = 0; i < n-strlen(str); ++i) printf("0"); printf("%s\n", str); } } //二进制--->Gray码 int bin2gray(int b){ return b ^ (b >> 1); } //Gray码 ---> 二进制 int gray2bin(int g){ int len = 0; int tmp = g; while(tmp > 1){ tmp = tmp>>1; ++len; } //printf("len = %d\n", len); int b = 1<<len; for(int i = len-1; i >= 0; --i){ int m = (g&(1<<i)) ^ ((b>>1)&(1<<i)); if(m) b |= 1 << i; } return b; } void test(){ char str[32]; int n; printf("input a binary code: "); scanf("%d", &n); _itoa(n, str, 2); printf("input binary code : %s\n", str); int g = bin2gray(n); _itoa(g, str, 2); printf("generate gray code : %s\n", str); int b = gray2bin(g); _itoa(b, str, 2); printf("gray to binary code : %s\n", str); } int main() { test(); // int n; // while(scanf("%d",&n) == 1&&n){ // gray(n); // display(n); // } fclose(stdin); return 0; }

图片摘自： https://blog.csdn.net/qq_22980439/article/details/51072294 https://blog.csdn.net/gordon_77/article/details/79489548