格雷码(gray code)

（格雷码，Gray Code）格雷码是对十进制数的一种二进制编码。编码顺序与相应的十进制数的大小不一致。其特点是：对于两个相邻的十进制数，对应的两个格雷码只有一个二进制位不同。另外，最大数与最小数之间也仅有一个二进制位不同，以 4 位二进制数为例，格雷编码如下：

十进制数	格雷码	十进制数	格雷码
0	0000	8	1100
1	0001	9	1101
2	0011	10	1111
3	0010	11	1110
4	0110	12	1010
5	0111	13	1011
6	0101	14	1001
7	0100	15	1000

如果把每个二进制的位看作一个开关，则将一个数变为相邻的另一个数，只须改动一个开关。因此，格雷码广泛用于信号处理、数-模转换等领域。

下面程序的任务是：由键盘输入二进制数的位数n(n<16)，再输入一个十进制数 m(0≤m<2n)，然后输出对应于 m 的格雷码（共 n 位，用数组 gr[] 存放）。

为了将程序补充完整，你必须认真分析上表的规律，特别是对格雷码固定的某一位，从哪个十进制数起，由0 变为 1，或由 1 变为 0。

/**************************************************************** 
 * Description: C++ implementation of gray code
 * Author: Alex Li
 * Date: 2023-04-25 21:12:31
 * LastEditTime: 2023-06-10 17:09:49
****************************************************************/

#include <stdio.h>
int main(){
	
	int bound = 1, m, n, b, p, gr[15];
	//由键盘输入二进制数的位数n(n<16)，再输入一个十进制数 m(0≤m<2n)，
	printf( "input n,m\n" );
	scanf( "%d%d", &n, &m );
	for (int i = 1; i <= n; i++ )
		bound = bound*2;
	if ( m < 0 || m >= bound ){
		printf( "Data error!\n" );
		return 0;
	}
	b = 1;
	for ( int i = 1; i <= n; i++ ){
		p = 0; 
        b = b * 2;
		for ( int j=0; j <= m; j++ )
			if ( (j%b-(b/2))==0 )
				p = 1 - p;
		gr[i] = p;
	}
	for ( int i = n; i>=1;i--)
		printf( "%1d", gr[i] );  
	printf( "\n" );
}

Previous Quiz

Back to Lesson

Next Quiz

计算机基础

格雷码(gray code)