酷应用

使用位运算来吾日三省吾身

百家作者：程序人生 2018-09-05 08:06:34

点击上方“程序人生”，选择“置顶公众号”

第一时间关注程序猿（媛）身边的故事

题图 | @望川鸟

作者

寒食君i

已获原作者授权，如需转载，请联系原作者。

在文章之前我先抛出一个有趣的问题，相信有的同学是看过的，没有看过的也不打紧儿，文章下面会进行解答。问题如下：

现在有1000个瓶子，里面999瓶是水，1瓶是毒药。最少通过多少次的试验，能确定哪瓶是毒药。

这个问题你可以思考一下，我先来说一说最近在生活中遇到的另一间相关的事。

前段时间在设计一张数据表的时候遇到了一个小问题。情况是这样的，一条数据有着三种状态，这三种状态是可能叠加并且重复的。什么意思呢？我举一个通俗的例子来类比一下。

孔子曰：吾日三省吾身。高乎？帅乎？富乎？高、富、帅可以说是一个人的三种状态。比如通过「骨骼生长」这个函数的处理，人可以拥有「高」这个状态；通过「自我打理、运动健身」这个函数的处理，人可以拥有「帅」这个状态；通过「发奋图强」这个函数的处理，人可以拥有「富」这个状态。什么是叠加？就是一个人可以拥有其中的多种状态；什么是重复？比如一个人多次「奋发图强」，依然会拥有「富」的状态。

解释完这些，再回到问题本身。我当时想的是，给每个状态一个单独的布尔类型（可以判断真或假）的字段，然后在进行处理时对相应状态进行分别判断。这样虽然也能完成任务，但是显得笨重且不优雅。举两个显而易见的例子：

假如这条数据将来不止三种状态，难道需要重新对数据库进行改造吗？而且程序也要相应地修改。数据库作为基础设施，一旦确定，修改地成本是很高的。
因为一条数据可能会经过多次相同类型地处理，假如这样设计，每次处理前程序都需要知道当前状态是真是假，处理完再决定是否修改状态码。这会导致程序的冗余、不简洁。
...

针对这些问题，X叔（组里一位我很敬重的老哥）建议我可以用一个笼统的字段 status,然后每种状态的值可以设置为1、2、4...这样。我心想，妙啊。

多重状态叠加产生的值是不会产生重复的，比如「高富」=3，「高帅」=5，「富帅」=6等等。而且以后有新的状态，假设新增「健康」这些，到时候，直接约定为相应值8、16等等。

那这和位运算有什么关系呢?我们来看下面这张图。

而在重复处理方面，位与运算带来了更加简洁的操作。举个例子，假如当前状态时是「高帅」，需要再次进行「帅」处理，如果按照传统的加减方式，需要判断当前有没有「帅」这个状态4，有的话不加，没有的话加上4。这无疑是非常繁琐的。

使用位与运算，会简洁很多，比如:

很方便。在进行位或的时候也是如此，可以结合具体情况试一试。

除此之外，在一些编程语言的源码里，经常会用到位运算，因为它不仅高效，而且有时候更灵活。比如JDK8里在优化HashMap的扩容时，将取模运算换成了位运算。

解决了这个问题。回头看看文章开头的智力题。

可以先公布一下答案：10。

假设现在有十只小白鼠，如何10只小白鼠的生死来找出那一瓶毒药呢？我们先将1000个瓶子用二进制编号，就像下图：

从000000001-1111111111，代表1号到1024号（1001-1024个瓶子可以忽视，因为只需要1000个），可以看到，每个数都有十位，那么我们让每只小白鼠负责一列，将这一列的编号出现1的瓶子中的液体混合着喝下去。如果某只小白鼠死了那么可以判定这列为1的所有瓶子中，有一瓶是毒药。通过十只小白鼠的生死情况组合来看，不难发现那瓶是毒药的瓶子编号。

如果你觉得数量太大，有些纳闷，可以减少数量，假设总共共有八个瓶子，其中一瓶是毒药。仔通过这种方式来计算一下。