#include <stdio.h>
#include <stdlib.h>

#define MAXBIT 20
#define TRUE 1
#define CHANGE_BIT(x) x = ((x) == '0' ? '1' : '0')
#define NEXT(x) x = (1 - (x))

/*输出格雷码*/

/* Gray Code是一个数列集合，每个数使用二进位来表示，假设使用n位元来表示每个数好了，任两个数之间只有一个位元值不同，例如以下为3位元的Gray Code：
000 001 011 010 110 111 101 100*/

int main ( void )
{
	char digit[MAXBIT];
	int i, bits, odd;

	printf ( "输入位元数：" );
	scanf ( "%d", &bits );

	for ( i = 0; i < bits; i++ )
	{
		digit[i] = '0';
		printf ( "0" );
	}

	printf ( "\n" );

	odd = TRUE;

	while ( 1 )
	{
		if ( odd )
			CHANGE_BIT ( digit[0] );
		else
		{
			// 计算第一个1的位置
			for ( i = 0; i < bits && digit[i] == '0'; i++ ) ;
			if ( i == bits - 1 ) // 最后一个Gray Code
				break;
			CHANGE_BIT ( digit[i+1] );
		}
		for ( i = bits - 1; i >= 0; i-- )
			printf ( "%c", digit[i] );

		printf ( "\n" );
		NEXT ( odd );
	}
	return 0;
}