一切要从一瓶有毒的水和一群可怜的老鼠说起

有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？(hint: 有毒的无论怎么稀释都有毒哦)

首先给瓶子编号，默认 1 - 1000，考虑到老鼠喝了水之后就是死或者不死的状态。因为老鼠的个数是有限的，所以肯定是要想办法通过混合的方法。具体怎么混合呢？想象一下，10 只老鼠按照死和不死的状态而言，能够表示出 Pow(2, 10) = 1024 种信息。现在的情况是 1000 个瓶子，如果说用二进制表示就是

1
2
3
4
5
6
7
8
9
1 1
2 10
3 11
4 110
5 111
6 1110
...
999  1111100111
1000 1111101000

最大的 1000 用二进制表示是 1111101000 总计 10 位。如果把 1 到 1000 的每个数都用 n = 1..10 位二进制表示就不难发现只要把第 n 位为 1 的数找出来，混在一起给编号也为 n 的小老鼠喝。那么小老鼠如果死了就说明毒药肯定在第 n 位为 1 的瓶子中。最后再确定一个 10 位二进制数转换为 10 进制就找到了。同理，如果这个题目告诉我们有两瓶毒药就把这 1000 瓶按照两两组合最后得到 C(1000,2) = 499500 个组合。再转换成上一种问题即可。

不用中间数交换两个数

是的没错，千万不能写成

1
2
3
int temp = a;
a = b;
b = temp;

这样做就大错特错了。所以怎么写呢？当然是位运算! 

1
2
3
4
a = a ^ b;
b = a ^ b;
a = a ^ b;
`

案例

一个整数数组，里面的数字都出现两次，只有一个数字出现了一次，我们管它叫单身数字，你要写代码找到这个单身数字。我们知道相同数字异或得到 0，0 和任何数字异或都是那个数字。说明只需要把数组中所有数异或即可。

1
2
3
4
5
public int findSingleNumber(int[] nums) {
   int result = 0;
   for (int num: nums) result ^= num;
   return result;
 }