Question

c语言的一道题

在很久很久以前，有一个国王他拥有n瓶葡萄酒，而且国王将在24小时之后举办一个大型的庆祝活动，并且这n瓶葡萄酒都将用于宴请，但是国王从007里得到消息，这n瓶酒中的其中一瓶，被人下了毒，而且这种毒为慢性毒药，中毒者当场不会有任何表现，而是在10-20小时左右才会表现出中毒的状态并且毒发身亡。国王拥有成千上万的奴隶正在建造新宫殿，他可以从中选取一定数量的奴隶来充当试酒的人，而因为选中的人会耽误工程，所以他希望能够选最少的奴隶试酒并找出那瓶毒酒。
假如你就是那个国王，假如你拥有足够多用于试酒的杯子，你最少需要多少名奴隶才能在24小时之内找出哪一瓶为毒酒

输入要求
输入数据有多组。
每组数据仅有一个整数N（1 ≤ N ≤ 100,000），N代表国王拥有的葡萄酒数量。

输出要求
每组输出一行包含一个整数M，M为国王最少需要试毒的奴隶

示例输入

2

示例输出输出

1

Answer 1

这些以身试毒的奴隶，就是一堆bit，1到N这些数字对应酒的编号，所有bit0（化成二进制，最低位是0bit）是1的数字，都给一个人喝；所有bit1是1的数字，依次类推，这样到20小时后，所有中毒奴隶代表的bit组成的数，就是有毒那瓶酒。
如果酒的数量恰好是2的整数次幂，拿走编号最大的那瓶，剩下的按同样方法做。
例：
3瓶酒，要2个人，编号为0和1，0喝最低位是1的酒，即1号瓶和3号瓶
1喝bit1是1的酒，即2号瓶喝3号瓶
这样，结果显而易见，最终中毒的bit是1，没中毒的是0，这个二进制数就是要找的那瓶酒的编号。