第一种方法是直接排列
以二进制为0值的格雷码为第零项,第一项改变最右边的位元,第二项改变右起第一个为1的位元的左边位元,第三、四项方法同第一、二项,如此反复,即可排列出n个位元的格雷码。
vector<int> grayCode(int n) {
vector<int> res;
res.push_back(0);
if (n == 0) return res;
res.push_back(1);
int total = 1 << n;
for (int i = 2;i < total; i+=2)
{
int j = 1;
while((res.back() & j) == 0)
j <<= 1;
j <<= 1;
res.push_back(res.back() ^ j);
res.push_back(res.back() ^ 1);
}
return res;
}
第二种方法是镜射排列
vector<int> grayCode(int n) {
vector<int> res;
if (n == 0)
{
res.push_back(0);
return res;
}
res.push_back(0);
res.push_back(1);
for (int i = 2; i <= n; i++)
{
int s = 1 << (i-1);
for (int j = res.size() - 1; j >= 0; j--)
{
res.push_back(res[j] + s);
}
}
return res;
}