89. Gray Code

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res=new ArrayList<Integer>();
        res.add(0);
        int bit=1;
        for(int i=0;i<n;i++)
        {
            for(int j=res.size()-1;j>=0;j--)
                res.add(res.get(j)|bit);
            bit=bit<<1;
        }
        return res;
    }
}

 1st bit: 0->1->1->0->0->1->1->0

2nd bit: 0->0->1->1->1->1->0->0

3rd bit:  0->0->0->0->1->1->1->1

-------------

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res=new ArrayList<Integer>();
        int m=(int)Math.pow(2,n);
        for(int i=0;i<m;i++)
            res.add(i^(i>>1));
        return res;
    }
}