Gray Code Sequence

When a dial or sensor counts in ordinary binary, several bits can flip at once: going from 3 (011) to 4 (100) changes all three. A reading taken halfway through the change can be badly wrong. A Gray code avoids this by listing the numbers in an order where each one differs from the one before it in exactly one bit.

Write gray_code(n) that returns a list of all the numbers from 0 to 2^n - 1, each exactly once, such that:

• the list starts with 0,
• each number differs from the one before it in exactly one bit,
• and the last number also differs from the first in exactly one bit, so the sequence can loop forever.

Several orders follow these rules; any of them is accepted.

Examples

gray_code(1)    # returns [0, 1]
gray_code(2)    # returns [0, 1, 3, 2]    (one possible answer)
gray_code(3)    # returns [0, 1, 3, 2, 6, 7, 5, 4]    (one possible answer)

In binary, [0, 1, 3, 2] is 00, 01, 11, 10: every step changes one bit, and so does the jump from 10 back to 00.

Constraints

• 0 <= n <= 16
• For n = 0 the only number is 0, so the answer is [0]