由一道简单的Leetcode题 “620. 有趣的电影 ”发现了一个有趣的东西 -- “位运算中的按位与运算”

今天掌柜随手翻了一道Leetcode的题来玩，对，就是上面的620这道题????找出有趣的电影 。这道题确实很简单，筛选数据的条件就三个，一个是判断description 不是boring；另一个就是id必须是奇数；最后还要按评分降幂排列。

具体的题目和解法掌柜就不贴出来了，大家可以去leetcode官网查看。掌柜在自己提交了解法后会习惯性地去看别人的解法，想看看有没有更优解。于是就意外的发现一个高票的答案里面使用了标题里面的????位运算。


于是就随手一搜，发现这是个很有趣的东西，打算这里多聊几句，也算是个小小的总结，如果对你有帮助就更好！????

PS:如有错误，请指出，谢谢。

好了，现在回到正题，准确的来说这里这位答主使用的是位运算里面的按位与运算来判断奇偶数。所以第一个问题来了????什么是按位与运算呢？

掌柜决定来拆解一下这三个字“按位与”，先看第二个字????：
位，它指的是把两个数（这里是十进制数）转换成对应的二进制位 数；

那么最后的那个字 “与” ????，其实是AND的意思。还记得布尔运算吗？当我们对两个内容进行True or False判断的时候，只有两者同为True的时候，我们才能得到True值；否则就是False。

那么一开始的 “按” ????就是说按照 布尔运算的法则来对二进制位对比判断，如果这两个二进制位(同为True），即都是1的时候，那么结果位就是 1；否则就是 0。

可以看下面这个示例更加容易理解上面的 “按位与”运算，比如现在我们有两个整数 1 和 10 ，此时我们对他们进行按位与运算。首先把1 和 10 转换成二进制位数（这里使用的是八位的二进制位数）应该是 ：

1  = 0000 0001
&
10 = 0000 1010

然后再进行运算：

1  = 0000 0001
&
10 = 0000 1010
--------------
     0000 0000

此时我们得到了结果是 0000 0000，再将这个结果转换成十进制数，就可以得到 1和10 的按位与运算结果是0，即1 & 10 = 0。

现在我们知道了什么是按位与运算，那么第二个问题来了：如何用 按位与运算来判断奇偶数呢？ 掌柜再写一个示例，你就会很快明白????。

1  = 0000 0001
&
5  = 0000 0101
--------------
     0000 0001

这次按位与运算的是 1 & 5，根据上面的运算规律，可以得到 1 & 5 = 1。 不知道你发现没有，当我们用 1 & 后面跟的是奇数的时候，所得到的结果就是1；而跟的是偶数的时候，运算结果就是 0。所以当我们要判断一个数（这里指的是整数）是奇偶数的时候，直接用某个数与1进行按位与，就可以得到结果。 附上代码可能更好理解：

接着掌柜用Python对10万个整数进行了一个奇偶数的判断，分别用了模运算和位运算的按位与运算看两者的效率：


上面????是模运算，下面是按位与运算????


看看这效率差的好明显！！！????，同样是对10万个整数进行奇偶数判断，模运算耗时39.9秒；而按位与运算只花了3.6秒！运算时间快了10倍多。怪不得那个哥们在620这题的MySQL答案提交击败了98%的其他用户，原来如此。

好了，今天由一道简单的SQL题中的一个小点延伸了对按位与运算的浅谈????。当然，位运算可不止这一个运算，还有其他运算比如按位或（|）、按位异或（^）、按位取反（~）、左移运算 （<<）以及右移运算（>>），这些掌柜后面遇到了再来聊聊。

感谢这些参考资料：
二进制与位运算实用操作汇总（基础篇）
七分钟全面了解位运算
用python的位运算来判断数值的奇偶性
数学专栏课外加餐（二） | 位操作的三个应用实例
python 判断奇偶数的三种方法，最后一种90%的人没见过。