原理

二进制中，任何位都代表2个状态，

所以

• 1位可以表示2种状态
• 2位可以表示4种状态
• 3位可以表示8种状态
• n位可以表示2ⁿ种状态

同时，也代表我们可以只用n个数，表示出1到2ⁿ-1之间的所有数(排除0)

这几个数分别是2⁰ 2¹ 2² .....2ⁿ

• 用1，2可以表示出1-3之间的所有数 1， 2，1+2
• 用1，2，4可以表示出1-7之间的所有数 1，2，1+2，4，1+4，2+4，1+2+4
• 用1，2，4，8可以表示出1-15之间的所有数 1，2，1+2，4，1+4，2+4，1+2+4，8，1+8，2+8，1+2+8，4+8，1+4+8，2+4+8，1+2+4+8

每个数，有且只有1种固定的组合，不会出现2个数，他们的组合一样

比如，7用 1+2+4表示，不会有其他的数用这个组合，7也只能用1+2+4表示

为什么？

这其实就是用2进制的方式表示这个数

1表示为 0001 1

2表示为 0010 2

3表示为 0011 2 + 1

4表示为 0100 4

5表示为 0101 4 + 1

6表示为 0110 4 + 2

7表示为 0111 4 + 2 + 1

8表示为 1000 8

9表示为 1001 8 + 1

10表示为 1010 8 + 2

11表示为 1011 8 + 2 + 1

12表示为 1100 8 + 4

13表示为 1101 8 + 4 + 1

14表示为 1110 8 + 4 + 2

15表示为 1111 8 + 4 + 2 + 1

每个数都有自己的二进制表示方式，正好对应了1 2 4 8的组合方式

黄金工资

假设有一个工人要为老板工作15天，老板，用一块黄金作为这15天的工资

但是需要每天支付当天工资，所以需要把黄金切开

那么，最少切几刀才能每天都正常支付工资？

由于15<16，所以，我们可以用1，2，4，8这4个数，表示出1-15之间的所有数

那么，我们只需要切3刀即可

第1刀，切下整段黄金的1/15（用1表示）

第2刀，切下整段黄金的2/15（用2表示）

第3刀，切下整段黄金的4/15（用4表示）

剩下的部分是8/15（用8表示）

支付工资时，

天数	使用的组合	说明
第1天	1	给1
第2天	2	给2，取回1
第3天	1 + 2	给1
第4天	4	给4，取回1、2
第5天	1 + 4	给1
第6天	2 + 4	给2，取回1
第7天	1 + 2 + 4	给1
第8天	8	给8，取回1、2、4
第9天	1 + 8	给1
第10天	2 + 8	给2，取回1
第11天	1 + 2 + 8	给1
第12天	4 + 8	给4，取回1、2
第13天	1 + 4 + 8	给1
第14天	2 + 4 + 8	给2，取回1
第15天	1 + 2 + 4 + 8	给1

超重的药丸A

有10瓶药丸（数量足够多），其中9瓶是正常的，1瓶是有问题的

正常的药丸，每粒都是1g

有问题的药丸，每粒都是1.1g

如何使用精密仪器只称重1次，就找出有问题的瓶子

解题思路：让每一瓶贡献的“额外重量”是唯一的

给瓶子编号，1-10，第n瓶里取出n粒

• 1号瓶子取1粒

• 2号瓶子取2粒

• ......

• 10号瓶子取10粒

将这55粒药丸称重，都正常的话应该是55g，超出的部分就是有问题的

• 如果结果是55.1，则超出了0.1g，即有1粒有问题，那么这个有问题的药丸，来自1号瓶
• 如果结果是55.2，则超出了0.2g，即有2粒有问题，那么这个有问题的药丸，来自2号瓶
• ....
• 如果结果是56，则超出了1g，即有10粒有问题，那么这个有问题的药丸，来自10号瓶

超重的药丸B

有10瓶药丸（数量足够多），其中有n瓶有问题(n>0)

正常的药丸，每粒都是1g

有问题的药丸，每粒都是1.1g

如何使用精密仪器只称重1次，就找出有问题的瓶子

解题思路：让每一瓶贡献的“额外重量”是唯一的

给瓶子编号，1-10，第n瓶里取出2^(n-1)粒

• 1号瓶子取2⁰ = 1粒
• 2号瓶子取2¹ = 2粒
• 3号瓶子取2² = 4粒
• 4号瓶子取2³ = 8粒
• 5号瓶子取2⁴ = 16粒
• 6号瓶子取2⁵ = 32粒
• 7号瓶子取2⁶ = 64粒
• 8号瓶子取2⁷ = 128粒
• 9号瓶子取2⁸ = 256粒
• 10号瓶子取2⁹ = 512粒

总共取出1023粒，称重，正常应该是1023g，超出部分则是有问题的药丸

• 如果结果是1023.1，则超出了0.1g，即有1粒有问题，那么这个有问题的药丸，来自1号瓶
• 如果结果是1023.2，则超出了0.2g，即有2粒有问题，那么这个有问题的药丸，来自2号瓶
• 如果结果是1031，则超出了8g，即有80粒有问题，那么这个有问题的药丸，来自5和7号瓶， 因为80 = 16 + 64，5号瓶贡献16粒，7号瓶贡献64粒
• 如果结果是1112.6，则超出了89.6g，即有896粒有问题，那么这个有问题的药丸，来自8 9 10号瓶，因为896 = 128 + 256 + 512
• 以此类推

这里，不能像超重的药丸A一样，每瓶取自然数粒，因为，有问题的瓶子数未知

比如，最后称重的结果显示有3粒有问题，你不知道这些药丸是来自来自3号瓶的3粒，还是1号瓶的1粒+2号瓶的2粒

小白鼠与毒药A

你有 100瓶药水，其中有1瓶有毒的，毒的效果在小白鼠喝下后 24小时内显现

现在你有 24小时 来找出哪一瓶是毒药

尽可能少的小白鼠来做实验，以确定哪一瓶是毒药

解题思路

小白鼠喝了药之后，会出现 活或死2种状态，所以，可以用二进制解决

接下来，确定小白鼠的数量

因为有100瓶药水，而小白鼠的数量又要尽可能的少，所以，就需要每只小白鼠喝下不同的药瓶中的水，确保每瓶药都有小白鼠喝，所以，每只小白鼠的生死状态组合，必须要超过100，因为2⁷ = 128>100

所以，至少需要7只

给100瓶药瓶编号，从1 1 2 3.....100

用7位二进制方式表示

• 第1瓶：0000001
• 第2瓶：0000010
• 第3瓶：0000011
• 第4瓶：0000100
• 第99瓶：1100011
• 第100瓶：1100100

给7只小白鼠编号， 0 1 2 3 4 5 6 ，分别对应二进制的第0到第6位（从右到左）

接下来，开始喂小白鼠喝药水

• 第0只，喝下所有二进制编码后，第0位为1的药瓶中的水
• 第1只，喝下所有二进制编码后，第1位为1的药瓶中的水
• 第2只，喝下所有二进制编码后，第2位为1的药瓶中的水
• 第3只，喝下所有二进制编码后，第3位为1的药瓶中的水
• 第4只，喝下所有二进制编码后，第4位为1的药瓶中的水
• 第5只，喝下所有二进制编码后，第5位为1的药瓶中的水
• 第6只，喝下所有二进制编码后，第6位为1的药瓶中的水

这样，24小时后，观察每只小白鼠的死亡状况，

死亡的小白鼠标记为1，活着的小白鼠标记为0，最终组合成一个二进制数，这就是毒药的编号

比如

0，1，3号死亡，2，4，5，6号存活

那么这个二进制数字是 0(编号6) 0(编号5) 0(编号4) 1(编号3) 0(编号2) 1(编号1) 1(编号0)

0001011，代表10进制的11，所以，是第11号瓶有毒

为什么？

11号瓶的二进制编码是0001011，它的第0 1 3 位是1

按照规则，编号是 0 1 3 号的小白鼠会喝下这瓶水，其他4只小白鼠不会喝（因为其他4位是0）

所以，0 1 3 会死亡，剩下的4只存活

同样，如果1号瓶有毒，那么只有0号小白鼠来喝这瓶，也只有0号小白鼠死亡