如何快速嘗出毒酒？- 用bit解決問題

國王有一百桶酒，比自己的生命還重要。結果有一天其中一桶被投了慢性毒藥，喝了以後半個小時以後就會死掉。國王大怒，指令玩忽職守的侍衛去試毒。酒不能被混合，一個侍衛可以喝多桶酒，一桶酒也可以由多個侍衛喝，怎麼樣才能用最少的侍衛、在最短的時間知道哪桶是毒酒。侍衛可以了解為線程，即怎麼樣用最少的線程用最快的速度完成這個工作。

此問題是我在面試時經常用的一道題目，主要考察的是候選人能不能以計算機的思維考慮問題。

最簡單的方案肯定是找100個人，每個人試一桶酒，那麼用時30分鐘，就可以判斷出哪一桶就有毒。

再進一步的，可以使用分段法，把酒分成n份，先找n個侍衛試酒，可以定位出哪一段的酒有毒，再接着分段試酒。但這種方案，分段數目越少，試出毒酒的平均耗時就越長。

如果用計算機的思維來分析這個問題，那麼首先考慮如何存儲這100桶酒。100桶酒可以用二進制7個bit來表示（27>100）。對應那一桶毒酒，其二進制表示中為1的位置如果能夠可以定位出來，就可以定位出此桶毒酒。可以找7個侍衛編号1-7。對于每一桶酒的二進制表示（不足七位前面用0表示），從第一位到第七位，如果是1，則對應編号的侍衛喝此桶酒。這樣，每個侍衛喝掉對應的酒。30分鐘後，侍衛按照編号1-7，死掉的置為1，活着的置為0，如此，侍衛的一個序列如0000111就表示第七桶酒為毒酒。

上述最後一種方案提現了在計算機中使用bit來解決問題的思路。當需要節省存儲的時候，使用bit來做經常會有出其不易的效果。就比如最近很火的電影《天才槍手》中，主角們記憶選擇題的答案A、B、C、D，完全可以使用位編碼來表示四種答案:00-A 01-B 10-C 11-D，四個bit轉換為一個十六進制數字，如此就可以節省一半的存儲，記憶起來也會簡單很多。此外，我們處理大資料去重/計數使用的Bitmap、BloomFilter，也都是一種使用bit節省存儲的思路。

原文出處：後端技術雜談

<a href="http://www.rowkey.me/blog/2018/01/04/king-rec-pois-wine/" target="_blank">原文連結</a>

轉載請與作者聯系，同時請務必标明文章原始出處和原文連結及本聲明。