江苏龙网

  1. 主页 > 生活百科 > >

位运算与经典八皇后问题

位运算

文章来源：
https://mp.weixin.qq.com/s/14jQ1yLL4Cw6ufI2E3R-yg
作者：码海
前言位运算在生产或算法解题中并不常见，不过如果你用得好，可以达到事半功倍的效果，而且位运算用得好，也可以极大地提升性能，如果在生产或面试中能看到使用位运算来解题，会让人眼前一亮，觉得你还是有点逼格的，巧用位运算，不仅会提升性能，还会让代码的可读性更好，达到四两拨千斤的效果，今天我们就来学学位运算在解题中的一些技巧，最后会用位运算来看看怎么解八皇后这道大 Boss 题，相信你看完肯定会有收获！
本文将会从以下几个方面来讲解位运算
  • 什么是位运算，位运算常见操作
  • 位运算使用技巧简介
  • 巧用位运算解算法题
什么是位运算，位运算常见操作在现代计算机中所有的数据在内存中都是以二进制存在的，位运算就是直接对整数在内存中的二进制位进行操作，由于位运算直接对内存数据进行操作，无需转成十进制，因此使用位运算的处理速度是很快的 。
举个简单的例子，当我们要计算 6 & 4 的结果，在做位运算的时候首先要把 6，4 转成二进制，然后再做相应的位操作（与） 。
位运算与经典八皇后问题

文章插图
 
基本的位运算有与、或、异或、取反、左移、右移这6种，介绍如下：
& 与：只有当两位都是 1 时结果才是 1，否则为 0。
0110&0100-----------0100| 或：两位中只要有 1 位为 1 结果就是 1，两位都为 0 则结果为 0 。
0110&0110-----------0110^ 异或：两个位相同则为 0，不同则为 1
0110^0100-----------0010~ 取反：0 则变为 1，1 则变为 0
~0110-----------1001<< 左移：向左进行移位操作，高位丢弃，低位补 0
int a = 8;a << 3;移位前：0000 0000 0000 0000 0000 0000 0000 1000移位后：0000 0000 0000 0000 0000 0000 0100 0000>> 右移：向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位
unsigned int a = 8;a >> 3;移位前：0000 0000 0000 0000 0000 0000 0000 1000移位后：0000 0000 0000 0000 0000 0000 0000 0001int a = -8;a >> 3;移位前：1111 1111 1111 1111 1111 1111 1111 1000移位后：1111 1111 1111 1111 1111 1111 1111 1111位运算使用技巧简介接下来我们就由浅入深地来学习一下使用位运算的那些黑科技
1、 判断整型的奇偶性
使用位运算操作如下
if((x & 1) == 0) {// 偶数} else {// 奇数}这个例子相信大家都见过，只需判断整型的第一位是否是 1 即可，如果是说明是奇数，否则是偶数
2、 判断第 n 位是否设置为 1
【位运算与经典八皇后问题】if (x & (1<<n)) {// 第 n 位设置为 1}else {// 第 n 位设置为 1}在上例中我们判断第一位是否为 1，所以如果要判断第 n 位是否 1，只要把 1 左移 n 位再作与运算不就完了 。
3、 将第 n 位设置为 1
y = x | (1<<n)思路同第二步，先把 1 移到第 n 位再作或运算，这样第 n 位就肯定为 1 。
4、 将第 n 位设置为 0
y = x & ~(1<<n)先将 1 左移到 第 n 位，再对其取反，此时第 n 位为 0，其他位都为 1，这样与 x 作与运算后，x 的第 n 位肯定为 0 。
5. 将第 n 位的值取反
y = x ^ (1<<n)我们知道异或操作是两个数的每一位相同，结果为 0，否则是 1，所以现在把 1 左移到第 n 位，则如果 x 的第 n 位为 1，两数相同结果 0，如果 x 的第 n 位为 0，两数不相同，则为 1 。来看个简单的例子
01110101^00100000--------01010101如图示，第五位刚好取反
6、 将最右边的 1 设为 0
y = x & (x-1)如果说上面的 5 点技巧有点无聊，那第 6 条技巧确实很有意思，也是在 leetcode 经常出现的考点，下文中大部分习题都会用到这个知识点，务必要谨记！掌握这个很重要，有啥用呢，比如我要统计 1 的位数有几个，只要写个如下循环即可，不断地将 x 最右边的 1 置为 0，最后当值为 0 时统计就结束了 。
count = 0while(x) {x = x & (x - 1);count++;}先介绍这么多吧，如果大家对其他的位运算技巧感兴趣可以看看文末的参考链接
巧用位运算解算法题接下来我们看看位运算在算法题中的应用 。
1、 高频面试题：老鼠试毒
有 8 个一模一样的瓶子，其中有 7 瓶是普通的水，有一瓶是毒药 。任何喝下毒药的生物都会在一星期之后死亡 。现在，你只有 3 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？


推荐阅读


上一篇：Python求解特征向量和拉普拉斯矩阵

下一篇：分类算法其实也可做回归分析——以knn为例