leetcode:Gray Code

一、テーマ
数nを入力し、この数のグレイコードを出力します.
たとえば、2を入力して{0,1,3,2}を返します.
二、分析
1、バイナリコード->グレイコード(符号化):右端の1つから、各ビットと左側の1つのイソOR(XOR)を順番に、グレイコードに対応するビットの値として、一番左の1つは変わらない(左が0に相当する).(以上のコードに対応するforループ内のループ体).
グレイコード->バイナリコード(復号):左の2番目のビットから、各ビットと左のビットが復号された値を、そのビットが復号された値として異ならせる(最も左のビットは依然として変わらない).
2、規則を探す
3ビットグレイコードを例に挙げます.
         0 0 0
         0 0 1
         0 1 1
         0 1 0
        1 1 0
        1 1 1
        1 0 1
        1 0 0
nビット目のグレイ符号は,n−1ビットのグレイ符号の一部と,1<(n−1)とn−1ビットのグレイ符号の逆シーケンスの和を加えた2つの部分から構成されていることがわかる.
次のようになります.
       (0)00
      (0)01
      (0)11
      (0)10
        100+010=110
        100+011=111
        100+001=101
        100+000=100
 

class Solution {
public:
    vector<int> grayCode(int n) {
        int num = 1<<n;
		vector<int> ans;
		ans.reserve(num);
		for(int i=0;i<num;i++)
			ans.push_back(i^(i>>1));
		return ans; 
    }
};

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;
        if(n==0){
        	ans.push_back(0);
        	return ans;
        }
        vector<int> res = grayCode(n-1); 
        int len = res.size()-1;
        int adder = 1<<(n-1);
        for(int i=len;i>=0;i--){
        	res.push_back(adder+res[i]);
        }
        return res;
    }
};