The solution with most votes is excellent, but I am afraid seldom people can think it out in an interview if he has never met this problem.

I try to give a solution which is easy to think out.

Lets see when n = 1:

0 1

then n = 2:

00 01 11 10 => 0 + each of {0,1} and 1 + each of {1, 0}

then n = 3:

000 001 011 010 110 111 101 100 => 0 + each of {00,01,11,10} and 1 + each of {10,11,01, 00}

....

So we can see that what we need to do is when doing next round, we just need to output all the previous one, and reverse them, and add an 1 on top of them.

adding an 1 means + 2^n, we can use a number to record it, every round we times 2. So we do not need to do bit operations in fact.

To Reversing the results, we can use a stack.

```
public class Solution {
public IList<int> GrayCode(int n) {
IList<int> Result = new List<int>();
Result.Add(0);
if (n == 0) return Result;
Stack<int> stack = new Stack<int>();
stack.Push(0);
int Curr = 1;
for (int i = 0; i < n; i++)
{
int m;
while (stack.Count > 0)
{
m = stack.Pop();
Result.Add(m + Curr);
}
Curr = Curr * 2;
foreach (int j in Result)
{
stack.Push(j);
}
}
return Result;
}
}
```