最近在看
Matrix67大牛的位运算4则(还只看到第3则),看到这,大牛推荐的。
然后就做了下,不过建议先自己理解,别看大牛给的程序,
这个题是二维的格雷码,把两个合并起来。
题意是把0到2^(n +m)-1的数写成2^n * 2^m的矩阵,使得位置相邻两数的二进制表示只有一位之差
这样的话就是把n位的格雷码和m位的格雷码合并起来就行了
拿n = 1 m = 2来说吧
可以自己先穷举一下会发现时下面的样子
一
|
二
|
三
|
四
|
000(0)
|
100(4)
|
110(6)
|
010(2)
|
001(1)
|
101(5)
|
111(7)
|
011(3)
|
可以发现各列的前两位是一样的,也是m位的gray(其实先把所有列合并起来,然后再在后面加上n的gray就成了这个了)
这样的话,实现起来就比较容易了
代码如下(第n个gray码是n ^ (n >> 1)(其中n从0开始))
for(x = 0;x < 1<<n;x++)
{//列的gray 就可以把一行搞成几行
u = (x ^ (x >> 1));//计算n位的gray
for(y = 0;y < 1<<m;y++)
{//计算m位的gray
t = (y ^ (y >> 1)) << n;//移位,这里就是左移一位
printf("%d ",(u | t));//输出,由于这里的不会出现进位,所以可以用加
}
printf("\n");
}