# Gray Code

## Gray Code

[原题链接](https://leetcode.com/problems/gray-code/)

### 描述

> The gray code is a binary numeral system where two successive values differ in only one bit.
>
> Given a non-negative integer *n* representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

### 例子

> Input: 2 
>
> Output: \[0,1,3,2] 
>
> Explanation: 
>
> 00 - 0 
>
> 01 - 1 
>
> 11 - 3 
>
> 10 - 2
>
> For a given n, a gray code sequence may not be uniquely defined. For example, \[0,2,3,1] is also a valid gray code sequence.
>
> 00 - 0 
>
> 10 - 2 
>
> 11 - 3 
>
> 01 - 1

### 解法

```cpp
class Solution {
public:
     vector<int> grayCode(int n) {
        vector<int>res(1,0);
        for(int i=0;i<n;i++){
            int size=res.size();
            for(int j=size-1;j>=0;j--){
                res.push_back(res[j]|1<<i);
            }
        }
        return res;
    }
};
```

[出处](https://leetcode.com/problems/gray-code/discuss/29891/Share-my-solution)

The middle two numbers only differ at their highest bit, while the rest numbers of part two are exactly symmetric of part one：\
Say the example input is 3.

0 000\
1 001\
3 011\
2 010

6 110\
7 111\
5 101\
4 100

For the pair of (2, 6), (3, 7), (1, 5) and (0, 4), the last 2 bits are the same. The only difference is 6,7,5 and 4 set the first bit on.