二进制相关问题

位运算问题

1. 记得使用lowBit = n&(-n)。
2. 负数右位移，高位补1；正数右位移，高位补0。

老鼠试毒

问题：
假设只有8瓶水，其中1瓶有毒。小白鼠只要尝一点带毒的水24小时后就会死亡，问至少要多少只小白鼠才能在24小时内鉴别出哪瓶水有毒？

思路1：
使用 3 位二进制对这 8 瓶水编号，将对应编号的水喂给符合编号的老鼠。例如，第 3 瓶水，二进制为 011，则喂给第 2 和第 3 只老鼠。
由于每一瓶水的编号都是唯一的，因此每一瓶水对应的死亡状况也是唯一的。例如，第 5 瓶水有毒，二进制为 101，那么第 1 和第 3 只老鼠会死。
只要查看老鼠的死亡状况，即可知道有毒的水是哪一瓶了。

思路2：

• 从 8 瓶中选 瓶，不给任何老鼠喂，如果没有老鼠死亡，则这瓶是有毒的
• 从剩余 7 瓶中选 瓶，分别喂给 3 只老鼠，哪只死了，则对应一瓶是有毒的
• 从剩余 4 瓶中选 瓶，每一瓶都喂给 2 只老鼠，不要喂重复了，哪两只死了，则对应的一瓶是有毒的
• 最后一瓶喂给 3 只老鼠，如果都死了，则这瓶是有毒的