利用性质：已知n-1位格雷码的情况下，对其进行镜像操作，并在最高位填上1，就可以n位格雷码。

递归实现

  1. import java.util.LinkedList;
  2. import java.util.List;
  4. public class GreyCode {
  5.     public static List<Integer> greyCode(int n) {
  6.         if (n == 1) {
  7.             List<Integer> ans = new LinkedList<>();
  8.             ans.add(0);
  9.             ans.add(1);
  10.             return ans;
  11.         }
  12.         List<Integer> ans = greyCode(n - 1);
  13.         for (int num = 1 << (n - 1), i = ans.size() - 1; i >= 0; --i) {
  14.             ans.add(ans.get(i) + num);
  15.         }
  16.         return ans;
  17.     }
  19.     public static void main(String[] args) {
  20.         System.out.println(greyCode(3));
  21.     }
  22. }

非递归

用循环实现，不需要递归，使用ArrayList在get的时候可以由更高的效率。

  1. import java.util.ArrayList;
  2. import java.util.List;
  4. public class GreyCode {
  5.     public static List<Integer> greyCode(int n) {
  6.         List<Integer> ans = new ArrayList<>(1 << n);
  7.         ans.add(0);
  8.         for (int i = 0, plus = 1; i < n; ++i, plus = 1 << i) {
  9.             for (int j = ans.size() - 1; j >= 0; --j) {
  10.                 ans.add(ans.get(j) + plus);
  11.             }
  12.         }
  13.         return ans;
  14.     }
  16.     public static void main(String[] args) {
  17.         System.out.println(greyCode(3));
  18.     }
  19. }

异或编码

  1. import java.util.ArrayList;
  2. import java.util.List;
  4. public class GreyCode {
  5.     public static List<Integer> greyCode(int n) {
  6.         List<Integer> ans = new ArrayList<>(1 << n);
  7.         for (int i = 0; i < 1 << n; ++i) {
  8.             ans.add(i ^ (i >> 1));
  9.         }
  10.         return ans;
  11.     }
  13.     public static void main(String[] args) {
  14.         System.out.println(greyCode(3));
  15.     }
  16. }