今天我们来看两个稍微复杂一点的例子。
n皇后问题位运算版
n皇后问题是啥我就不说了吧，学编程的肯定都见过。下面的十多行代码是n皇后问题的一个高效位运算程序，看到过的人都夸它牛。初始时，upperlim:=(1 shl n)-1。主程序调用test(0,0,0)后sum的值就是n皇后总的解数。拿这个去交USACO，0.3s，暴爽。procedure test(row,ld,rd:longint);
var
pos,p:longint;
begin
{ 1} if row<>upperlim then
{ 2} begin
{ 3} pos:=upperlim and not (row or ld or rd);
{ 4} while pos<>0 do
{ 5} begin
{ 6} p:=pos and -pos;
{ 7} pos:=pos-p;
{ 8} test(row+p,(ld+p)shl 1,(rd+p)shr 1);
{ 9} end;
{10} end
{11} else inc(sum);
end;
乍一看似乎完全摸不着头脑，实际上整个程序是非常容易理解的。这里还是建议大家自己单步运行一探究竟，实在没研究出来再看下面的解说。
和普通算法一样，这是一个递归过程，程序一行一行地寻找可以放皇后的地方。过程带三个参数，row、ld和rd，分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。我们以6×6的棋盘为例，看看程序是怎么工作的。假设现在已经递归到第四层，前三层放的子已经标在左图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置，位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来，得到该行所有的禁位，取反后就得到所有可以放的位置（用pos来表示）。前面说过-a相当于not a + 1，这里的代码第6行就相当于pos and (not pos + 1)，其结果是取出最右边的那个1。这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用test过程。注意递归调用时三个参数的变化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。最后，如果递归到某个时候发现row=111111了，说明六个皇后全放进去了，此时程序从第1行跳到第11行，找到的解的个数加一。
~~~~====~~~~===== 华丽的分割线 =====~~~~====~~~~
Gray码
假如我有4个潜在的GF，我需要决定最终到底和谁在一起。一个简单的办法就是，依次和每个MM交往一段时间，最后选择给我带来的“满意度”最大的MM。但看了dd牛的理论后，事情开始变得复杂了：我可以选择和多个MM在一起。这样，需要考核的状态变成了2^4=16种（当然包括0000这一状态，因为我有可能是玻璃）。现在的问题就是，我应该用什么顺序来遍历这16种状态呢？
传统的做法是，用二进制数的顺序来遍历所有可能的组合。也就是说，我需要以0000->0001->0010->0011->0100->…->1111这样的顺序对每种状态进行测试。这个顺序很不科学，很多时候状态的转移都很耗时。比如从0111到1000时我需要暂时甩掉当前所有的3个MM，然后去把第4个MM。同时改变所有MM与我的关系是一件何等巨大的工程啊。因此，我希望知道，是否有一种方法可以使得，从没有MM这一状态出发，每次只改变我和一个MM的关系（追或者甩），15次操作后恰好遍历完所有可能的组合（最终状态不一定是1111）。大家自己先试一试看行不行。
解决这个问题的方法很巧妙。我们来说明，假如我们已经知道了n=2时的合法遍历顺序，我们如何得到n=3的遍历顺序。显然，n=2的遍历顺序如下：
00
01
11
10
你可能已经想到了如何把上面的遍历顺序扩展到n=3的情况。n=3时一共有8种状态，其中前面4个把n=2的遍历顺序照搬下来，然后把它们对称翻折下去并在最前面加上1作为后面4个状态：
000
001
011
010 ↑
——–
110 ↓
111
101
100
用这种方法得到的遍历顺序显然符合要求。首先，上面8个状态恰好是n=3时的所有8种组合，因为它们是在n=2的全部四种组合的基础上考虑选不选第3个元素所得到的。然后我们看到，后面一半的状态应该和前面一半一样满足“相邻状态间仅一位不同”的限制，而“镜面”处则是最前面那一位数不同。再次翻折三阶遍历顺序，我们就得到了刚才的问题的答案：
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
这种遍历顺序作为一种编码方式存在，叫做Gray码（写个中文让蜘蛛来抓：格雷码）。它的应用范围很广。比如，n阶的Gray码相当于在n维立方体上的Hamilton回路，因为沿着立方体上的边走一步，n维坐标中只会有一个值改变。再比如，Gray码和Hanoi塔问题等价。Gray码改变的是第几个数，Hanoi塔就该移动哪个盘子。比如，3阶的Gray码每次改变的元素所在位置依次为1-2-1-3-1-2-1，这正好是3阶Hanoi塔每次移动盘子编号。如果我们可以快速求出Gray码的第n个数是多少，我们就可以输出任意步数后Hanoi塔的移动步骤。现在我告诉你，Gray码的第n个数（从0算起）是n xor (n shr 1)，你能想出来这是为什么吗？先自己想想吧。
下面我们把二进制数和Gray码都写在下面，可以看到左边的数异或自身右移的结果就等于右边的数。
二进制数 Gray码
000 000
001 001
010 011
011 010
100 110
101 111
110 101
111 100
从二进制数的角度看，“镜像”位置上的数即是对原数进行not运算后的结果。比如，第3个数010和倒数第3个数101的每一位都正好相反。假设这两个数分别为x和y，那么x xor (x shr 1)和y xor (y shr 1)的结果只有一点不同：后者的首位是1，前者的首位是0。而这正好是Gray码的生成方法。这就说明了，Gray码的第n个数确实是n xor (n shr 1)。
 
; 今年四月份mashuo给我看了这道题，是二维意义上的Gray码。题目大意是说，把0到2^(n+m)-1的数写成2^n * 2^m的矩阵，使得位置相邻两数的二进制表示只有一位之差。答案其实很简单，所有数都是由m位的Gray码和n位Gray码拼接而成，需要用左移操作和or运算完成。完整的代码如下：var
x,y,m,n,u:longint;
begin
readln(m,n);
for x:=0 to 1 shl m-1 do begin
u:=(x xor (x shr 1)) shl n; //输出数的左边是一个m位的Gray码
for y:=0 to 1 shl n-1 do
write(u or (y xor (y shr 1)),' '); //并上一个n位Gray码
writeln;
end;
end.
Matrix67原创
转贴请注明出处
听82一说,才知道Gray在社会主义建设中,有着如此重大的作用! 回去,肯下第13章.
"输出任意步数后Hanoi塔的移动步骤"
弱弱的问matrix67大牛,用Gray知道移动了第几个,但移动到哪,该如何求呢?
回复：最小的盘子往固定方向移动，其它盘子的移动方法都是唯一的
我也弱弱地６７大牛一个问题：
关于判断组合数C(N,K)是一个奇数还是一个偶数,为什么:
如果N and K=K; C(N,K)就是一个奇数呢?
回复：http://www.matrix67.com/blog/article.asp?id=329
哇，那个n皇后简直太帅了
回复：我也很帅
出神入化
请教一下N皇后问题中的Sum如何定义的？
回复：初始化为0，程序结束后即为答案
有个问题，这个不是无符号long吧，要不然执行pos:=pos-p有可能溢出啊～？
回复：这是位运算，我们不关心它实际表示的值，只关心它在计算机中的储存方式，因此有无符号无所谓；另外，pos-p不可能小于0，因为p上有1的位置pos上肯定有，因此不会出现不够减的情况
这个确实牛~~~~
但是还有一个更能牛的.有一本书上面写了一个n皇后问题的公式解法,O(1)时间,比0.3s如何.
回复：公式解只能构造出一个解，不能找出所有解
N皇后的位运算解法该如何输出皇后的位置吗？
test(row+p,(ld+p)shl 1,(rd+p)shr 1);
改成 test(row or p,(ld or p)shl 1,(rd or p)shr 1);
为何结果一样? 加 和 或 运算是完全不同的运算呀,
还是觉得或运算比较好理解.
那个N皇后问题的解法真是出神入化，令人不敢相信，大牛，你真是太厉害了
gray码第n位为n^(n>>1) 我理解为gary码其实就是从低位到高位，顺次改变二进制一位得来的，而第n位的状态就由第n-1位决定，即n-1位为1（即0->1）n位还为0就变为1，为1就不变，n-1位为0（还没有轮到n-1位改变）那n位当然也不变。这样n>>1就是取下一位，而异或就符合上述改变规则。
ps.先从Hanoi塔规则的联系想到的哇，反向也说明了和Hanoi塔的映射关系哇！！
大牛很强哇~~我刚学acm哇，受益匪浅~~~~
niubility!!!!
@Neil:
改成或运算的确好理解一些，但这里用加效果是一样的，因为p中为1的位在row，ld，rd中对应的位肯定为0。用加法也不会产生进位的问题。
回答10楼：
虽然这样反着写意义上是不同的，但因为初值是一样的，所以答案是一样的。
确实很牛，位运算博大精深。。。
两个问题：
1：upperlim是N个1吗？表示每行都已添好的状态？
2：位操作降低时间复杂度的机理和效果，可以用比较数学的方法解释一下吗？
十分感谢！
太牛了！这种方法第一次见，好精妙!
上面解n皇后问题的代码，调用下一层test时，把加号改成or是不是能更快一点？
Matrix67牛可以解释一下 这个代码吗？(ld+p)shl 1,(rd+p)shr 1)
为什么要对下一行的影响需要平移一位呢？
太牛了
usaco上面那题是要输出前3个解的
位运算怎么确定
还有那两张图的ld rd中1的个数又没有变化
那是用什么代表不可放？
PS.本人太菜，太难理解，望matrix67大牛指点
楼上的,我想前3个解的输出还是用最原始的DFS输出就行了吧.
位运算只是可以更好的求出方案数
ld与rd表示的是所放皇后的左边相邻一列的禁位和右边相邻一列的禁位，而row是什么含义呢？为什么并完之后就是所有禁位呢？
不好意思，俺明白了，前面理解错误了。
原来，都代表当前行上的禁位，因此可以并。
仍不太清楚的地方，upperlim 与 not (row or ld or rd)的作用是不是保持pos始终是N位呢？
能不能不用DFS，改变一下位运算，使其能记录下皇后的位置呢？
这个确实牛~~~~
楼上说的那个n皇后公式是什么啊？
确实够强大，受益了~~
Orz Martrix67 神牛……………
明天就NOIP2009了
n皇后那个，主要是数据可以放在参数里乖乖跟着递归栈走了，这叫个方便~ （原先传递数组是不可能的吧）
强大~~
procedure test(row,ld,rd:longint);
var
pos,p:longint;
begin
{ 1} if rowupperlim then
{ 2} begin
{ 3} pos:=upperlim and not (row or ld or rd);
{ 4} while pos0 do
{ 5} begin
{ 6} p:=pos and -pos;
{ 7} dec(pos,p); //M牛败笔,这么写又快很多
{ 8} test(row+p,(ld+p)shl 1,(rd+p)shr 1);
{ 9} end;
{10} end
{11} else inc(sum);
end;
还不错
我终于看懂了
I used your solution(rewritten in C++) for the USACO site but it takes 1.5 seconds! How is that 0.3 seconds???
Is it because C++ is bad???
Oh, I,m sorry, I forgot to output only firsst 3 cases, this algorithm actually works well
I’m pleased I found this weblog, I couldnt discover any info on this subject matter earlier to. I also operate a site and if you want to ever severe in a little bit of guest writing for me if possible really feel free to let me know, i am usually look for people to check out my site.Hey, appreciate it for taking the effort to do this. I like your webpage, although it took a sluggish reader like me some time to via throughout entire page and the many comments.
皇后太多怎么办？毕竟一个int 8bit
这个n皇后可以做到多大？
弱弱的问一下matrix67大牛，我是一个菜鸟，不会pascal语言，那个n皇后问题，您可不可以用c或者是c++写一下啊？？
弱弱的问一下matrix67大牛，我是一个菜鸟，不会pascal语言，那个n皇后问题，您可不可以用c或者是c++写一下啊？？?
回ls
/*
二进制解n皇后问题，hdu 2553
*/
#include
#include
using namespace std;
int sum, n;
void Queen(int row, int ld, int rd)
{
int pos, p;
int upperlim = (1 << n) – 1;
if (row != upperlim)
{
pos = upperlim & ~(row | ld | rd);
while (pos != 0)
{
p = pos & -pos;
pos -= p;
Queen(row + p, (ld + p) <> 1);
}
}
else ++sum;
}
int main()
{
int ans[11], i;
for (i=1; i<=10; ++i)
{
sum = 0;
n = i;
Queen(0, 0, 0);
ans[i] = sum;
}
while (scanf(“%d”, &n), n)
{
printf(“%dn”, ans[n]);
}
return 0;
}
不知道为什么写上去排版乱了。。。头文件也不见了！
Gray码的那个问题让我想起来什么呢？
就是大学物理那个所谓的卡诺图
厉害，我以前在USACO上搞了半天TLE才过。。。今天见识了这牛X代码(=@__@=）
确实够强大，受益了~~
简直帅呆了、。
简直是艺术~
恭喜你，第一届CSP押题成功！
CSP2019。。。。。。