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

解题步骤如下：
1、把这 8 个瓶子从 0 到 7 进行编号，用二进制表示如下
0000010100111001011101112、将 0 到 7 编号中第一位为 1 的所有瓶子（即 1，3，5，7）的水混在一起给老鼠 1 吃，第二位值为 1 的所有瓶子（即2，3，6，7）的水混在一起给老鼠 2 吃，第三位值为 1 的所有瓶子（4，5，6，7）的水混在一起给老鼠 3 吃，现在假设老鼠 1，3 死了，那么有毒的瓶子编号中第 1，3 位肯定为 1，老鼠 2 没死，则有毒的瓶子编号中第 2 位肯定为 0，得到值 101 ，对应的编号是 5，也就是第五瓶的水有毒。
这道题及其相关的变种在面试中出现地比较频繁，比如我现在把 8 瓶水换成 1000 瓶，问你至少需要几只老鼠才能测出有毒的瓶子，有了上述的思路相信应该不难，几只老鼠就相当于几个进制位，显然 2^10 = 1024 > 1000，即 10 只老鼠即可测出来。
2、 leetcode 232

给定一个数，判断它是否是可以用 2 的幂次方表示，可以返回 true，不可以返回 false，比如 8 = 2^3, 说明可以用 2 的幂次方表示，返回 true，9 不可以，所以返回 false 。

解题分析：这题常规解法是做个循环不断地乘以 2 ，看下是否等于给定的值，如果等于说明是 2 的幂次方，否则如果不断累乘 2 后大于给定的值，说明不能用 2 的幂次方表示，时间复杂度是所做的累乘的次数，即 2^n >= 给定的值中的 n 。
那是否有更快的解法呢?
上文的介绍中其实我们已经埋下伏笔了，没错用 x & (x-1)，首先我们要发现能用 2 的幂次方表示的数的特点：它的所有位中有且仅有一位为 1，如
000012^0 = 1000102^1 = 2001002^2 = 4010002^3 = 8100002^3 = 16如图示，所有 2 的幂次方最多只有一位为 1
明白了这一点，我们的思路就简单了，由于符合 2 的幂次方的数只有一位为 1，x & (x-1) 是把最后一位 1 置为 0，所以只要做一次 x & (x-1) 运算，看它的值是否等于 0 即可，如果是 0 说明它可以用 2 的幂次方表示，否则不可以，代码如下:

if(x&(x-1)) { //使用与运算判断一个数是否是2的幂次方printf("%d不是2的幂次方！n", num);} else {printf("%d是2的%d次方！n", num, log2(num));}

只用一行代码即可搞定，方便了很多！
3、 leetcode 232

给定一个非负整数 num. 对于 0 ≤ i ≤ num 范围中的每个数字 i, 计算其二进制数中 1 的数目并将它们作为数组返回。输入: 5 输出: [0,1,1,2,1,2]

这题的常规解法相信大家都能猜到，就是从 0 到 num 循环一遍，求出每个数字 i 中 1 的数目。
如果用位运算怎么做呢，先来看下解法，然后我们再来分析为啥这样写，非常巧妙！
Python 代码

vector<int> countBits(int num) {	vector<int> bits(num+1, 0);	for (int i = 1; i<= num; i++) {bits[i] += bits[i & (i-1)] + 1;	}}

JAVA 代码

public static int[] countBits(int num) {int[] bits = new int[num+1];Arrays.fill(bits, 0);for (int i = 1; i <= num; i++) {bits[i] = bits[i & (i-1)] + 1;}return bits;}

最关键的代码看这一行
bits[i] += bits[i & (i-1)] + 1;这行代码是啥意思呢，i & (i-1) 是把 i 的最后一个值为 1 的位设为 0，不难发现整数「i & (i-1)」中 1 的位数比 i 中 1 的位数少一个，所以要加 1（即 bits[i & (i-1)] + 1）。非常巧妙，这样从 1 开始走一遍循环即可，中间不要做任何针对变量 i 的 1 的个数的计算，只不过付出了一个 bits 数组的代价。这里也是利用了以空间换时间的思想。
4、利用位运算来解八皇后问题
接下来我们来看看终级 Boss 题，如何用位运算来解八皇后问题，解题中运用到了非常多的位运算技巧，相信你学完会收获不少。

在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法

举个简单的下图所示的例子，如果在棋盘上放置一个皇后，则与这个皇后同一行，同一列，且皇后所在斜线经过的格子不能再放其他皇后。

文章插图

如图示，在其中任意一行放置一个皇后，则与此皇后同行，同列，同对角线的都不允许再放其他皇后，图中蓝色区块不允许放其他皇后。
一般我们用回溯法解八皇后。这里简单介绍一下啥是回溯法。
在第一行从左到右先选择一个位置放置皇后，由于第一行放了皇后，第二行可放皇后的位置受到了限制（下图蓝色区块表示对应行的格子不能放皇后）