10瓶毒药其中只有一瓶有毒至少需要几只老鼠可以找到有毒的那瓶

　　　　身似浮云，心如飞絮，气若游丝。

• 用二分查找和二进制位运算的思想都可以把死亡的老鼠降到最低。
• 其中，二进制位运算就是每一只老鼠代表一个二进位0或1，0就代表老鼠存活，1代表老鼠死亡；根据数学运算 2³ = 8、2⁴  = 16，那么至少需要四只老鼠可以找到其中的那瓶毒药。

/**
 * binary : 0001 : 第1瓶药水
 * binary : 0010 : 第2瓶药水
 * binary : 0011 : 第3瓶药水
 * binary : 0100 : 第4瓶药水
 * binary : 0101 : 第5瓶药水
 * binary : 0110 : 第6瓶药水
 * binary : 0111 : 第7瓶药水
 * binary : 1000 : 第8瓶药水
 * binary : 1001 : 第9瓶药水
 * binary : 1010 : 第10瓶药水
 * 药液混合后的数组1: [1, 3, 5, 7, 9]
 * 药液混合后的数组2: [2, 3, 6, 7, 10]
 * 药液混合后的数组3: [4, 5, 6, 7]
 * 药液混合后的数组4: [8, 9, 10]
 *
 * 打印结果如上，此时就可以按照二进制逻辑判定哪瓶是毒药了。
 * 此时用四只老鼠分别去喝四组混合后的药液，即老鼠1和混合要和后的数组1，老鼠2喝混合数组2，老鼠3喝混合数组3，老鼠4和混合数组4
 * 假设第七瓶是毒药
 * 那么可以观察到混合药液后的数组1、数组2、数组3 都混入的毒药7
 * 所以就是第一只老鼠死亡，第二只老鼠死亡，第三只老鼠死亡，第四只存活，之前混合药液的逻辑就是 1有毒 0无毒
 * 所以它们对应的二进制就是：1110，也就是上述的：binary : 0111 : 第7瓶药水
 *
 * 假设第六瓶是毒药就是对应着：0110，也就是第一只老鼠存活、第二只老鼠死亡、第三只老鼠死亡、第四只老鼠存活
 *
 * 所以，最后可以根据老鼠的死亡和存活状态 & 结合混合后的药液数组 判定哪瓶是毒药
 * 同理 1000瓶毒药至少需要10只老鼠可以找出那瓶有毒
 * 2∧10 = 1024
 */

 1 package com.bebird.vote;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Arrays;
 5 import java.util.List;
 6 
 7 public class TestVirus {
 8 
 9     public static void main(String[] args) {
10         // 给十瓶毒药标序号,用1~10标记，并转为二进制
11         List<Integer> virusArr = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
12         // 四个药液混合的数组
13         List<Integer> list1 = new ArrayList<>();
14         List<Integer> list2 = new ArrayList<>();
15         List<Integer> list3 = new ArrayList<>();
16         List<Integer> list4 = new ArrayList<>();
17         for(int i = 0; i < virusArr.size(); i++) {
18             Integer num = virusArr.get(i);
19             // 设置返回至少4位数字：使用5位数字并切掉第一位数字。
20             String binary = Integer.toBinaryString(num + 0b10000).substring(1);
21             System.out.println("binary : " + binary.concat(" : 第").concat(String.valueOf(i + 1)).concat("瓶药水"));
22             /**
23              * 把二进制数组中，个位数为1的 十位数为1的 和百位数为1的 千位数为一的 分别组成一个数组
24              * 为什么这样做，其实就假设二进制中，1位的是有毒，0位是无毒，按这种逻辑把十瓶药水混合成四平给四只老鼠喝
25              */
26             // 判断二进制 个十百千 位数是否为1:
27             // 个位为1
28             boolean flagGe = (Integer.parseInt(binary) >> 0 & 1) == 1;
29             if (flagGe) {
30                 list1.add(i + 1);
31             }
32             // 十位为1
33             boolean flagShi = (Integer.parseInt(binary) >> 1 & 1) == 1;
34             if (flagShi) {
35                 list2.add(i + 1);
36             }
37             // 百威为1
38             boolean flagBai = (Integer.parseInt(binary) >> 2 & 1) == 1;
39             if (flagBai) {
40                 list3.add(i + 1);
41             }
42             // 千位为1
43             if (binary.startsWith("1")) {
44                 list4.add(i + 1);
45             }
46 
47         }
48         System.out.println("药液混合后的数组1: "+ list1);
49         System.out.println("药液混合后的数组2: "+ list2);
50         System.out.println("药液混合后的数组3: "+ list3);
51         System.out.println("药液混合后的数组4: "+ list4);
52         /**
53          * binary : 0001 : 第1瓶药水
54          * binary : 0010 : 第2瓶药水
55          * binary : 0011 : 第3瓶药水
56          * binary : 0100 : 第4瓶药水
57          * binary : 0101 : 第5瓶药水
58          * binary : 0110 : 第6瓶药水
59          * binary : 0111 : 第7瓶药水
60          * binary : 1000 : 第8瓶药水
61          * binary : 1001 : 第9瓶药水
62          * binary : 1010 : 第10瓶药水
63          * 药液混合后的数组1: [1, 3, 5, 7, 9]
64          * 药液混合后的数组2: [2, 3, 6, 7, 10]
65          * 药液混合后的数组3: [4, 5, 6, 7]
66          * 药液混合后的数组4: [8, 9, 10]
67          *
68          * 打印结果如上，此时就可以按照二进制逻辑判定哪瓶是毒药了。
69          * 此时用四只老鼠分别去喝四组混合后的药液，即老鼠1和混合要和后的数组1，老鼠2喝混合数组2，老鼠3喝混合数组3，老鼠4和混合数组4
70          * 假设第七瓶是毒药
71          * 那么可以观察到混合药液后的数组1、数组2、数组3 都混入的毒药7
72          * 所以就是第一只老鼠死亡，第二只老鼠死亡，第三只老鼠死亡，第四只存活，之前混合药液的逻辑就是 1有毒 0无毒
73          * 所以它们对应的二进制就是：1110，也就是上述的：binary : 0111 : 第7瓶药水
74          *
75          * 假设第六瓶是毒药就是对应着：0110，也就是第一只老鼠存活、第二只老鼠死亡、第三只老鼠死亡、第四只老鼠存活
76          *
77          * 所以，最后可以根据老鼠的死亡和存活状态 & 结合混合后的药液数组 判定哪瓶是毒药
78          * 同理 1000瓶毒药至少需要10只老鼠可以找出那瓶有毒
79          * 2∧10 = 1024
80          */
81 
82 
83     }
84 
85 
86 }