solution.md

# 格雷编码

<p>格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。</p>
<p>给定一个代表编码总位数的非负整数<em> n</em>，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。</p>
<p>格雷编码序列必须以 0 开头。</p>
<p>&nbsp;</p>
<p><strong>示例 1:</strong></p>
<pre><strong>输入:</strong>&nbsp;2<strong><br />输出:</strong>&nbsp;[0,1,3,2]<strong><br />解释:</strong>00 - 001 - 111 - 310 - 2对于给定的&nbsp;<em>n</em>，其格雷编码序列并不唯一。例如，[0,2,3,1]&nbsp;也是一个有效的格雷编码序列。00 - 010 - 211 - 301 - 1</pre>
<p><strong>示例&nbsp;2:</strong></p>
<pre><strong>输入:</strong>&nbsp;0<strong><br />输出:</strong>&nbsp;[0]<strong><br />解释:</strong> 我们定义格雷编码序列必须以 0 开头。给定编码总位数为 <em>n</em> 的格雷编码序列，其长度为 2<sup>n</sup>。当 <em>n</em> = 0 时，长度为 2<sup>0</sup> = 1。因此，当 <em>n</em> = 0 时，其格雷编码序列为 [0]。</pre>

以下程序实现了这一功能，请你填补空白处内容：

```cpp
#include <stdio.h>
#include <stdlib.h>
int *grayCode(int n, int *returnSize)
{
	if (n < 0)
	{
		return NULL;
	}
	int i, count = 1 << n;
	int *codes = malloc(count * sizeof(int));
	_________________
	return codes;
}
int main(int argc, char **argv)
{
	if (argc != 2)
	{
		fprintf(stderr, "Usage: ./test n\n");
		exit(-1);
	}
	int i, count;
	int *list = grayCode(atoi(argv[1]), &count);
	for (i = 0; i < count; i++)
	{
		printf("%d ", list[i]);
	}
	printf("\n");
	return 0;
}
```

## template

```cpp
#include <stdio.h>
#include <stdlib.h>
int *grayCode(int n, int *returnSize)
{
	if (n < 0)
	{
		return NULL;
	}
	int i, count = 1 << n;
	int *codes = malloc(count * sizeof(int));
	for (i = 0; i < count; i++)
	{
		codes[i] = (i >> 1) ^ i;
	}
	*returnSize = 1 << n;
	return codes;
}
int main(int argc, char **argv)
{
	if (argc != 2)
	{
		fprintf(stderr, "Usage: ./test n\n");
		exit(-1);
	}
	int i, count;
	int *list = grayCode(atoi(argv[1]), &count);
	for (i = 0; i < count; i++)
	{
		printf("%d ", list[i]);
	}
	printf("\n");
	return 0;
}
```

## 答案

```cpp
for (i = 0; i < count; i++)
{
	codes[i] = (i >> 1) ^ i;
}
*returnSize = 1 << n;
```

## 选项

### A

```cpp
for (i = 0; i < count; i++)
{
	codes[i] = (i >> 1) ^ i;
}
*returnSize = 1 << n - 1;
```

### B

```cpp
for (i = 0; i < count; i++)
{
	codes[i] = (i >> 2) ^ i;
}
*returnSize = 1 << n;
```

### C

```cpp
for (i = 0; i < count; i++)
{
	codes[i] = (i >> 1) ^ i;
}
*returnSize = 1 >> n;
```