描述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 - 001 - 111 - 310 - 2Note:• For a given n, a gray code sequence is not uniquely defined.• For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.• For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.分析格雷码 (Gray Code) 的定义请参考 wikipedia http://en.wikipedia.org/wiki/Gray_code。自然二进制码转换为格雷码：g0 = b0, gi = bi ⊕ bi−1保留自然二进制码的最高位作为格雷码的最高位，格雷码次高位为二进制码的高位与次高位异或，其余各位与次高位的求法类似。例如，将自然二进制码 1001，转换为格雷码的过程是：保留最高位；然后将第 1 位的 1 和第 2 位的 0 异或，得到 1，作为格雷码的第 2 位；将第 2 位的 0 和第 3 位的 0 异或，得到 0，作为格雷码的第 3 位；将第 3 位的 0 和第 4 位的 1 异或，得到 1，作为格雷码的第 4 位，最终，格雷码为 1101。格雷码转换为自然二进制码：b0 = g0, bi = gi ⊕ bi−1保留格雷码的最高位作为自然二进制码的最高位，次高位为自然二进制高位与格雷码次高位异或，其余各位与次高位的求法类似。例如，将格雷码 1000 转换为自然二进制码的过程是：保留最高位 1，作为自然二进制码的最高位；然后将自然二进制码的第 1 位 1 和格雷码的第 2 位 0 异或，得到1，作为自然二进制码的第 2 位；将自然二进制码的第 2 位 1 和格雷码的第 3 位 0 异或，得到 1，作为自然二进制码的第 3 位；将自然二进制码的第 3 位 1 和格雷码的第 4 位 0 异或，得到 1，作为自然二进制码的第 4 位，最终，自然二进制码为 1111。格雷码有数学公式，整数 n 的格雷码是 n ⊕ (n/2)。这题要求生成 n 比特的所有格雷码。最简单的方法，利用数学公式，对从 0 ∼ 2n − 1 的所有整数，转化为格雷码。n 比特的格雷码，可以递归地从 n − 1 比特的格雷码生成。
这题我折腾了很久，勉强的通过了。但偶尔看到有更简洁的方法（@爱做饭的小莹子），在建数组时用了递归。为方便自己学习，所以也贴上来。
代码：
1 import java.util.ArrayList; 2 3 public class Graycode { 4 5 public static void main(String[] args) { 6 int n=3; 7 System.out.println(grayCode(n)); 8 } 9 public static ArrayList<Integer> grayCode(int n) { 10 if(n==0) { 11 ArrayList<Integer> result = new ArrayList<Integer>(); 12 result.add(0); 13 return result; 14 } 15 16 ArrayList<Integer> result = grayCode(n-1); 17 // ArrayList<Integer> result = new ArrayList<Integer>(n); 18 int addNumber = 1 << (n-1); 19 int asize=result.size(); 20 21 for(int i=asize-1;i>=0;i--) { 22 result.add(addNumber + result.get(i)); 23 } 24 return result; 25 } 26 }然后，我有看到了更简单的方法。格雷码，二进制转格雷码的方法是将二进制前补0，然后前后两位异或。gi = bi ^ bi+1 比如 二进制 0101， 则前面添0后 00101，
然后从右向左两两位异或得0111 （相异为1，相同为0），得到格雷码 0111， 其实就是对二进制x做 (x>>1)^x 操作。
1 public class Solution { 2 public List grayCode(int n) { 3 List list = new ArrayList(); 4 if(n<0) { 5 return list; 6 } 7 for(int i=0; i< (1<<n); i++) { 8 list.add((i>>1)^i); 9 } 10 return list; 11 } 12 }
转载于:https://www.cnblogs.com/ncznx/p/9165087.html
