位的巧妙应用

前言

前几天做了一个笔试题目，当时没多想，今天翻看博客才发现，原来每个笔试题都藏的很深啊。

原文链接：http://blog.csdn.net/u010429424/article/details/77856133。
先说题目
面试题：8个试剂，其中一个有毒，毒性一定时间后发作，最少多少只小白鼠能检测出有毒试剂。

方法一：二分

这个题目，第一反应就是二分，4 4分，两个老鼠各喝四瓶，活下来的接着用。2 2分，再拿一只新老鼠，上一轮活着的接着用。最后直接在毒死老鼠的那两瓶中随意找一瓶，所以3只老鼠就够了。8-15只都一样，3只足够了。以15只为例，7 7分，3 3分，1 1，也就是log2n向下取整个。但这个方法比较耗时，只有等前面的死了之后才能进行下一轮，而且需要的瓶子数量也蛮多，至少保正每种酒需要三瓶(不知道哪瓶有毒)。

额外说些废话。没有时间上面的考虑，一只老鼠足够了，一瓶一瓶去喝，总能试出来，但时间太慢了。考虑下其他几只老鼠的情况，纯属于锻炼思维，跟这个题毫无关系，没兴趣的下面就不用看了。两只老鼠怎么样？从8瓶酒中选出四瓶，每只老鼠喝两瓶，有一只中毒死了，说明一定是在这两瓶中，另一只老鼠再从两瓶酒中随机选取一瓶，就不多说了。如果两只老鼠都没有死，说明在另一堆中，每只老鼠再喝两瓶，判断方法就和上面差不多了。就是说，2只老鼠，把一只老鼠时间减少了4倍左右。三只老鼠呢？一样，选8瓶，每次喝四瓶，把一只老鼠的时间缩短了8倍左右。这里的分析纯属无聊，因为用不上，下面这个解法，才应该是本题想考察的意图。

方法二：位

这个方法楼主思考了好久，发现结果和推到过程对应起来，怎么说都有些牵强，所以，这里的过程，仁者见仁，智者见智，欢迎大家留言，这里只是给出我的看法。
假设我们有n只老鼠，那么可以对应多少种情况？即C_n⁰+C_n¹+…+C_nⁿ是多少？
很显然，这里需要数学功底，答案是C_n⁰+C_n¹+…+C_nⁿ=2ⁿ
所以，很明显，2^3=8，所以三只老鼠足够了，即三个老鼠喝出八种状态，分别是死0只老鼠(0种情况)，死1只老鼠(3种情况)，死2只老数(3种情况)，死3只老鼠(1种情况)。为1的死了，为0的活着。具体关系可以用位如下所示：

# [3、2、1]
0 0 1 = 1  # 2、3没死，1死了
0 1 0