位运算与经典八皇后问题( 四 ) _位运算

还有一个问题，已知当前行的 column，pie，na，怎么确定下一行的 column，pie，na 的值（毕竟选完当前行的皇后后，要确定下一行的可用格子，而下一行的可用格子依赖于 column，pie，na 的值）
上文可知，我们已经选出了当前行可用的格子（相应位为 1 对应的格子可用），假设我们在当前行选择了其中一个格子来放置皇后，此位置记为 p（如果是当前行的最后一个格子最后一个格子，则值为 1，如果放在倒数第二个，值为 10，倒数第三个则为 100，依此类推），则对于下一行来说，显然 column = column | p
那么 pie 呢，仔细看下图，显然应该为 (pie | p) << 1, 左斜线往下一行的格子延展时，相当于左移一位，

文章插图

如图示：下一行的 pie 显然为 (pie | p) << 1 。
同理下一行的 na 为 (na | p) >> 1 。
有了以上详细地解析，我们就可以写出伪代码了

void queenSettle(row, colomn,pie,na) {
N = 8; // 8皇后
if (row >= N) {
// 遍历到最后一行说明已经找到符合的条件了
count++;return
}
// 取出当前行可放置皇后的格子
bits = (~(colomn|pie|na)) & ((1 << N)-1)
while(bits > 0) {
// 每次从当前行可用的格子中取出最右边位为 1 的格子放置皇后
p = bits & -bits
// 紧接着在下一行继续放皇后
queenSettle(row+1, colomn | p, (pie|p) << 1, (na | p) >> 1)
// 当前行最右边格子已经选完了，将其置成 0，代表这个格子已遍历过
bits = bits & (bits-1)
}
}

一开始传入 queenSettle(0,0,0,0) 这样即可得到最终的解。伪代码写得很清楚了，相信用相关语言不难实现，这里就留给大家作个练习吧。
总结本文带大家由浅入深地完成了位运算的学习，掌握好位运算不仅仅是为了提升逼格，还能极大地提升效率，位运算也广泛地应用于代码编写中，运用得当能极大地简化代码，且可读性更好，限于篇幅关系，这里不展开，大家如有兴趣可参考文末的链接。
如有帮助，欢迎大家关注公号哦。之后将会讲解大量算法的解题思路，希望我们一起攻克算法难题！