位运算的妙用

位运算的妙用

二进制中的 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. 异或(^)的特性:任何数与自己异或等于零、与零异或等于本身,同时异或还满足结合律。
    问题:数组中,只有一个数出现一次,剩下都出现两次,找出出现一次的数。
    解答:利用异或支持交换律和结合律
// 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,得到的数转成十进制即为那瓶毒药的编号。