LeetCodeGray 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.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0  01 - 1  11 - 3  10 - 2

When n=3:
000
001
011
010
110
111 
101
100
From: http://www.darrensunny.me/leetcode-gray-code/
We can construct a gray code sequence of length n using a gray code sequence of length n−1 . Specifically, adding a preceding '0' to each of the numbers in binary format preserves the property that two successive values differ in only one bit. We do it and name the new sequence as s1. If we reverse the order of the numbers, and add a preceding '1' to each, the property is preserved as well.

public ArrayList<Integer> grayCode(int n) {

        ArrayList<Integer> result = new ArrayList<Integer>();

        if (n < 0)      // Invalid input

            return result;

        result.add(0);

        if (n == 0)     // No bit

            return result;

        result.add(1);  // With one bit

 

        // Iteratively contruct the grey code of n bits on that of n-1 bits

        // gc(n) = gc(n-1) ... gc'(n-1)+2^(n-1), where

        // gc'(n-1) means the reverse sequence of gc(n-1), and +2^(n-1) means adding

        // 2^(n-1) to each number in the sequence

        for (int i = 2; i <= n; i++) {

            int size = result.size();

            for (int j = size-1; j >= 0; j--)

                result.add(result.get(j)+(1<<(i-1)));

        }

 

        return result;

    }

vector<int> grayCode(int n)  
{  
  vector<int> ret;  
  int size = 1 << n;  
  for(int i = 0; i < size; ++i)  
ret.push_back((i >> 1)^i);  
  return ret;  
}
Also refer to http://www.darrensunny.me/leetcode-gray-code/
http://www.programering.com/a/MDO0kDMwATM.html
Read full article from 水中的鱼: [LeetCode] Gray Code 解题报告