N皇后II

这一题的做法很是nb，首先是两个位运算，对于任何一个二进制，满足补码的有：

  1. bit & (-bit)     // 获取最后一个1
  2. 比如：01100100，其负数是反码加一，即：10011100，取与就是00000100
  4. bit & (bit - 1) // 将最后一个1改为0
  5. 比如：01100100，减一为01100011，取与即01100000
  7. (1 << n) - 1    // 获取n个1

核心为这两个运算，即我们可以初始化一个全1的序列，比如4皇后问题，那么就是初始化一个1111，每个1对应每一行可以放置的位置，注意到了吗，这次把4*4的空间折叠起来了，虽然时间没变。

当放入第一个1的时候，我们使用策略1获取到：0001
即放置一个皇后在第一行的最后一个1处

此时如何进入下一个问题呢？并且正确的用1标注出来可以放置的位置？
答案是继续使用标识列，左斜和右斜的三个数组，但是这里我们用位数组
那么对于放置在0001的问题，其不能重复的列首先就是本身：0001 | 0000
左斜就是在其左边，因为在进入下一个问题之后就是第二行了，所以应该是：
(0001 | 0000) << 1 = 0010
那么右斜显然就是：(0001 | 0000) >> 1 = 0000对于0010可能更清楚些

最后的问题是，如何利用这三个数组剪枝呢？其实我们上面的过程已经自然剪枝了。

最后就是判断执行到了第几位，是否还需要执行，就!(col | dia1 | dia2) & 1111即可，因为col | dia1 | dia2三者中的1代表了第几位不能放皇后，取或就是所有不能放皇后的位置，此时再与全1与的话，就得到了还能放皇后的位置，一定是使得最后结果大于1的。可以看代码了：

  1. /// 52. N皇后 II
  2. pub fn total_n_queens(n: i32) -> i32 {
  3.     fn dfs(n: i32, depth: i32, col: i32, dia1: i32, dia2: i32, res: &mut usize) {
  4.         if depth >= n {
  5.             *res += 1;
  6.             return;
  7.         }
  9.         let mut bites = !(col | dia1 |dia2) & ((1 << n) - 1);
  10.         while bites > 0 {
  11.             let temp = bites & (-bites);                        // 获取最后一个1
  12.             dfs(n, depth+1, col | temp
  13.                 , (dia1 | temp) <<1, (dia2 | temp) >> 1, res);
  14.             bites &= (bites - 1);
  15.         }
  16.     }
  17.     let mut res = 0;
  18.     dfs(n, 0, 0, 0, 0, &mut res);
  19.     res as i32
  20. }