位运算的妙用

二进制中的 0 和 1 作为计算机处理的符号，如果在编码的过程中多使用位运算来解决问题，效率较高，在此记录一些常见的使用场景。

常见使用

1. 左移一位代表乘2，又移一位代表除2。
2. 奇偶判断可以用(n & 1 == 1)来判断。
3. 判断一个数是否为2的次幂，只有最高位为1的数才是2的次幂，所以可以用(n & (n - 1) == 0)来判断。
4. 给定一个int型的非负整数n，求大于它的最小二次幂的数。

n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
n = n + 1;

1. 判断正整数n的二进制表示中有多少个1。

while(n != 0){
    count++;
    n = n & (n - 1);
}

1. 异或(^)的特性：n ^ n = 0；0 ^ n = n；a ^ (b ^ c) = b ^ (a ^ c)。数组中，只有一个数出现一次，剩下都出现两次，找出出现一次的数。由于异或支持交换律和结合率，解答：

// 1^2^3^4^5^1^2^3^4 =（1^1)^(2^2)^(3^3)^(4^4)^5 = 0^0^0^0^5 = 5
int tmp = arr[0];
for(int i = 1;i < arr.length; i++){
    tmp = tmp ^ arr[i];
}
return tmp;

JDK源码中的位运算

1. ReentrantReadWriteLock 读写锁使用 AQS 中 state 的高16位表示读锁的次数，低16位表示写锁的可重入次数，设计到相关值得获取和判断都是用位运算实现的。
2. HashMap 初始化数组大小、定位数组下标、扩容重新定位新下标时都用了位运算。
3. ThreadPoolExecutor 使用变量 ctl 的高三位存储线程池状态，低29位存储线程数量，获取相关值时用位运算获得。
4. 还有很多，就不一一列举了。

小白鼠试毒问题

10瓶药里面有1瓶是毒药，小白鼠喝了有毒的药会在24小时后死亡，请问最少能用几只小白鼠在24小时内（包括24小时）试出那瓶毒药呢？

这里就可以用位掩码的思想来做，给10瓶药编号0-9并转为二进制，编号低一位为1的各取一滴做一个混合剂。同理低二位、低三位、低四位为一的都分别做混合剂。一共4瓶混合剂分别给4只小白鼠喝，24小时后看小白鼠的死亡情况。将死了的小白鼠编号对应成二进制位上的1，得到的数转成十进制即为那瓶毒药的编号。