题目1
有100瓶水, 其中一瓶有毒, 老鼠喝了有毒的水一周后就会死亡
问至少用多少只老鼠才能在一周内试出哪瓶水是有毒的
解答
这个问题可以使用二进制方式去解决
先说这道题得出答案的统一方法, 总共有多少瓶水, 把这个数字-1后转化为2进制
99转化为二进制就是1100011
这个二进制数有7位, 那么就需要7只老鼠
具体操作方法
将这100瓶水从0开始编号直到99
每一瓶水对应编号的二进制数如下表所示
| 十进制数 | 二进制数 |
|---|---|
| 0 | 0 0 0 0 0 0 0 |
| 1 | 0 0 0 0 0 0 1 |
| 2 | 0 0 0 0 0 1 0 |
| 3 | 0 0 0 0 0 1 1 |
| … | … |
| 99 | 1 1 0 0 0 1 1 |
现在让每一只老鼠对应二进制中的一位
如果这一位上是1, 那么就喝这瓶中的水, 如果是0就不喝
等到最后一天看这7只老鼠当中有哪些死亡
如果某一位上的老鼠存活, 那么代表有毒水编号的这一位是0, 反之则是1
比如第2,5,6,7位置上的老鼠死亡, 其他存活
则代表有毒水的编号是0100111
那么转化为十进制就是39
题目2
有100个囚犯站成一排, 从1开始报数, 奇数枪毙, 偶数留下
剩下的人继续按照该规则进行, 直到最后剩下1个人释放
问开始的时候站在哪个位置可以最终活下来
解答
可以采取倒推的方式
最后活下来的人, 在最后一轮必定是站在第2位
在倒数第二轮必定是站在第4位
在倒数第三轮必定是站在第8位
依此类推, 16 32 64
100以内2的幂次方最大就是64了, 所以是开始的时候站在64位的人最终存活
简单来说, 就是每一轮执行过去之后, 如果自己存活, 那么自己的序号就会除以2
每一轮结束之后都要保证自己所在的位置是偶数或者是1
只有2的幂次方的数可以满足此条件
并且在总数人>=2的情况下, 自己的序号不会变成1
只有总人数里面的最大的2的幂次方可以满足此条件
补码
补码是整数在内存当中的存储方式
- 原码: 最高位是符号位, 1表示负数, 0表示正数, 后面的位是这个数的绝对值
- 补码: 正数的补码与原码相同, 负数的补码就是对该负数的绝对值求反加1, 0的补码是0
比如一个byte类型的变量, 它是1个字节, 也就是8位
最大的正数很容易想到, 就是0 1 1 1 1 1 1 1, 它表示127
0的补码就是 0 0 0 0 0 0 0 0
要求一个负数的补码
比如-2
那么要先对该数求绝对值, 就是2, 2对应的原码是 0 0 0 0 0 0 1 0
取反是1 1 1 1 1 1 0 1
再+1就是1 1 1 1 1 1 1 0, 它就是-2的补码
那么已知一个补码, 怎么求对应的十进制数呢?
首先看最高位判断正负, 如果是0, 那么它是个正数, 正数就是二进制转化十进制的基本规则
这个很简单
如果是1, 那么它是个负数
巧妙之处就在于同样可以套用这个规则, 也可以逆向套用, 结果都一样
直接套用规则
比如1 1 1 1 1 1 1 1 , 取反就是0 0 0 0 0 0 0 0再+1是0 0 0 0 0 0 0 1
这个数表示+1, 它是最初负数的绝对值, 那么最初的负数就是-1
逆向套用规则1 1 1 1 1 1 1 1 , 先-1就是1 1 1 1 1 1 1 0再取反是0 0 0 0 0 0 0 1
结果是相同的
在8位的范围内, 能表示的最小负数是1 0 0 0 0 0 0 0
同样套用上述规则, 它表示-128
所以byte类型变量的范围就是 -128 ~ +127
更大容量的变量类型, char是2个字节, int是4个字节, 只要是整数, 计算方式都是相同的