前言
先抛出一个问题?
题目来源：https://www.zhihu.com/question/19676641/answer/12613290
有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
如果用二分法：
1000 / 2 = 500
500 / 2 = 250
250 /2 = 125
125 / 2 = 62 + 63
63 / 2 = 31 + 32
到现在位置你已经用完了所有的小白鼠，你只能确定32or31中的一堆，显然是无法实现了。
可以用位运算来思考，该问题。
1,把1000瓶标号：1,2,3,4,5,6...1000.
2,所有老鼠排列在一起组成一个2进制队列: 0000000000
0代表不喝，1代表喝
3,0000000001代表第一瓶水被喝情况
0000000010代表第二瓶水被喝情况
0000000011代表第三瓶水被喝情况
0000000100代表第四瓶水被喝情况
...
1111101000代表第1000瓶水被喝情况
4,第7天，喝了毒药的老鼠都死了，那个二进制队列转为为十进制就是毒药的标号。
比如第3只老鼠死亡，其他老鼠没死，队列为0000000100，第四瓶水有毒。
第1，5，6，8老鼠死亡，其他没死，队列为0010110001，第177瓶水有毒。
作者：kirch
链接：https://www.zhihu.com/question/19676641/answer/14123096
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
日常开发中位运算不是很常用，但是巧妙的使用位运算可以大量减少运行开销，优化算法。举个例子，翻转操作比较常见，比如初始值为1，操作一次变为0，再操作一次变为1。可能的做法是使用三木运算符，判断原始值为1还是0，如果是1，设置为0，否则设置为0.但是使用位运算，不用判断原始值，直接改变值就可以：1^num，
java支持的位运算符
1、原码、反码和补码说明：
一个数可以分成符号位（0正1负）+ 真值，原码是我们正常想法写出来的二进制。由于计算机只能做加法，负数用单纯的二进制原码书写会出错，于是规定了反码（正数不变，负数符号位不变，真值部分取反）；再后来由于+0， -0的争端，于是改进反码，变成补码（正数不变，负数符号位不变，真值部分取反，然后+1）。二进制前面的0都可以省略，所以总结来说：计算机里的负数都是用补码（符号位1，真值部分取反+1）表示的。
2、位运算符和2的关系
位运算符和乘2、除2在大多数时候是很相似的，可以进行替代，同时效率也会高的多，但是两者切记不能混淆 ；很多时候有人会把两者的概念混淆，尤其是数据刚好是 2、4、6、8、100等偶数的时候，看起来就更相似了，但是对于奇数，如本文使用的12345 ，右移之后结果为6172 ，这个结果就和数学意义上的除以2不同了，不过对于int 类型的数据，除2 会对结果进行取整，所以结果也是6172 ，这就更有迷惑性了。
按位与（&）
按位与的运算规则
| 操作数1 | 0 | 0 | 1 | 1 |
|---|---|---|---|---|
| 操作数2 | 0 | 1 | 0 | 1 |
| 按位与 | 0 | 0 | 0 | 1 |
规则总结：只有两个操作数对应位同为1时，结果为1，其余全为0. （或者是只要有一个操作数为0，结果就为0）。
按位或（|）
按位或的运算规则
| 操作数1 | 0 | 0 | 1 | 1 |
|---|---|---|---|---|
| 操作数2 | 0 | 1 | 0 | 1 |
| 按位或 | 0 | 1 | 1 | 1 |
规则总结：只有两个操作数对应位同为0时，结果为0，其余全为1.（或者是只要有一个操作数为1，结果就为1）
按位非（~）
按位非的运算规则
| 操作数 | 0 | 1 |
|---|---|---|
| 按位或 | 1 | 0 |
按位异或（^）
按位异或的运算规则
| 操作数1 | 0 | 0 | 1 | 1 |
|---|---|---|---|---|
| 操作数2 | 0 | 1 | 0 | 1 |
| 按位异或 | 0 | 1 | 1 | 0 |
规则总结：异：1
关于异或运算符，有很多非常有用的特性，我们在这里梳理总结一下。
Ⅰ、异或运算符满足交换律
也就是说，ab与ba是等价的，虽然a和b交换了位置，但还是会运算出相同的结果。这个规律还可以推广到N个操作数，也就是说，如果有N个变量都参与了异或运算，那么它们的位置无论如何交换，运算的结果都是相同的。
Ⅱ、任何两个相同的数字进行异或操作，所得到的结果都必然为0
这个特性并不难理解，因为两个相同的数字，换算成补码后，每个二进制位上的数也都相同，这样在进行异或运算时，按照运算规则，每个二进制位上得到的运算结果也都是0，这N个0所组成的二进制串就是数字0的补码。我们可以利用这个特性快速的判断两个整数是否相同。另外，利用这个特性还可以实现内存的快速清零操作，比如我们可以在代码中写上a=a^a;这条语句能快速的把变量a所占据的那几个字节的内存迅速清零。
Ⅲ、对于任意一个二进制位来说，这个位上的数与0进行异或运算，运算结果与这个二进制位上的数是相同的，而与1进行异或运算，结果与这个二进制位上的数字相反
注意，我们现在说的是二进制位上的数字，所谓相反不是说原来这个位上是1，运算结果是-1，而是说原来是1，运算结果为0，原来如果是0，运算结果是1，这才是此处所说的”相反”的概念。这个特性也非常好理解，小伙伴们一定要记住它，在以后进行一些位运算操作的时候经常会用到这个特性。
Ⅳ、对于任何两个整数a和b，abb等于a
这个结论为什么成立呢？简单说来，就是因为这个表达式中有bb，而bb的结果为0，前文已讲过，任何一个数与0进行按位异或操作，结果仍然是这个数本身，所以，abb等于a。这个特性在加密运算方面有着很普遍的应用。我们可以把a当作要加密的数据，而把b当作密钥。a异或b就是把a用密钥b进行了加密操作，当需要解密时，仍然以b作为密钥，再进行一次异或就实现了解密。
这个特性还可以推出另外一个结论：对于任何两个整数a和b，aba等于b。我们能够得到这个结论的原因也很简单，就是因为按照交换律，ab与ba的运算结果是一样的，所以aba等价于baa，这个表达式中出现了aa，aa的值也为0，所以整个表达式的其实就相当于b^0，最终结果还是b。
左移（<<）
运算规则：按二进制形式把所有的数字向左移动对应的位数，高位移出（舍弃），低位的空位补零。例如： 12345 << 1，则是将数字12345左移1位：
img
位移后十进制数值变成：24690，刚好是12345的二倍，所以有些人会用左位移运算符代替乘2的操作，但是这并不代表是真的就是乘以2，很多时候，我们可以这样使用，但是一定要知道，位移运算符很多时候可以代替乘2操作，但是这个并不代表两者是一样的。
思考一下：如果任意一个十进制的数左位移32位，右边补位32个0，十进制岂不是都是0了？当然不是！！！ 当int 类型的数据进行左移的时候，当左移的位数大于等于32位的时候，位数会先求余数，然后再进行左移，也就是说，如果真的左移32位 12345 << 32 的时候，会先进行位数求余数，即为 12345<<(32%32) 相当于 12345<< 0 ，所以12345<< 33 的值和12345<<1 是一样的，都是 24690。
右移（>>）
同样，还是以12345这个数值为例，12345右移1位： 12345>>1。
img
右移后得到的值为 6172 和int 类型的数据12345除以2取整所得的值一样，所以有些时候也会被用来替代除2操作。另外，对于超过32位的位移，和左移运算符一样，会先进行位数求余数。
无符号右移（>>>）
无符号右移运算符和右移运算符是一样的，不过无符号右移运算符在右移的时候是补0的，而右移运算符是补符号位的。以下是-12345二进制表示：
img
对于源码、反码、补码不熟悉的同学，请自行学习，这里就不再进行补充了讲解了，这里提醒一下，在右移运算符中，右移后补0，是由于正数 12345 符号位为0 ，如果为1，则应补1。
img
运算符的优先次序
在对一个表达式进行计算时，如果表达式中含有多种运算符，则要安运算符的优先次序一次从高向低进行。运算符的优先次序如下：
img
小白鼠实验应用
我们到此可以回归题目，用代码把题目做出来：
代码如下：
public static void main(String[] args) {
//结果反推第几瓶
System.out.println("结果反推第几瓶:");
Scanner input = new Scanner(System.in);
System.out.println("请用户输入总共死亡的个数:");
int dead = input.nextInt(); // dead用于储存死亡的个数
System.out.println("它们的编号从小到大依次为（从0开始）:");
int[] deadRats = new int[dead]; // number数组用于储存死亡试验品的标签序号
for(int i = 0; i < dead; i++){
deadRats[i] = input.nextInt();
}
double result = 0;
for(int i = 0; i < deadRats.length; i++){
result = result + Math.pow(2, deadRats[i]);
}
System.out.println("毒药编号:" + result);
//验算实验过程
//编号每一个小白鼠，1代表正常，0代表死亡
int[] srcRatsArray = new int[10];
for(int i = 0; i < 10; i++){
srcRatsArray[i] = 1;
}
//定义1000瓶水和药，不为零的即为毒药，从编号1开始，那么1000瓶，长度为1001
int[] bottleArray = new int[1001];
//记录结果的老鼠数组
int[] dtsRatsArray = new int[10];
for(int i = 0; i < 10; i++){
dtsRatsArray[i] = 1;
}
System.out.println("请指定毒药编号:");
int bottle = input.nextInt();
bottleArray[bottle] = 1;
//利用异或（^）运算， 活着的老鼠 1 碰到毒药 1 就会为0
for(int j = 1; j < 1001; j++){
String s = Integer.toBinaryString(j);
char[] chars = s.toCharArray();
//遍历j的二进制每一位
for(int x = chars.length - 1; x >= 0; x--){
if(chars[x] == '1'){
//index需要倒序
int realIndex = 9 - x;
//记录死亡的结果
if((srcRatsArray[realIndex] ^ bottleArray[j])== 0){
dtsRatsArray[realIndex] = 0;
}
}
}
}
for(int i = 0; i < 10; i++){
if(dtsRatsArray[i] == 0){
System.out.println("死亡老鼠:" + i);
}
}
}
参考：
网友评论