位运算的妙用

位运算的妙用

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

二进制编码方式

原码

原码就是符号位加上真值的绝对值,即用第一位表示符号,其余位表示值,例如八位二进制数:

+1 的原码 = 0000 0001
-1 的原码 = 1000 0001

反码

正数的反码是其本身,负数的反码是在其原码的基础上,符号位不变,其余各个位取反。例如:

+1 的原码 = 0000 0001   反码 = 0000 0001
-1 的原码 = 1000 0001   反码 = 1111 1110

补码

正数的补码是其本身,负数的补码是在其原码的基础上,符号位不变,其余位取反,然后再 +1 得到的(即反码 +1)。例如:

+1 的原码 = 0000 0001   反码 = 0000 0001  补码 = 0000 0001
-1 的原码 = 1000 0001   反码 = 1111 1110  补码 = 1111 1111

二进制数使用原码存储,计算时使用补码进行运算

Java 中的位运算符

运算符含义示例
&与运算6 & 3 = 2
|或运算6 | 3 = 7
^异或运算6 ^ 3 = 5
~取反运算~6 = -7
<<左移3 << 2 = 12
>>右移3 >> 1 = 1
>>>无符号右移3 >>> 1 = 1

上表中的取反运算有点难懂,运算步骤分解如下:

  1. 6 是正数,所以原码、反码、补码都是 00...0110
  2. 我们知道运算时都是拿补码进行运算的,所以 6 的补码取反之后为 11...1001
  3. 得到的结果还是补码,需要先 -1 转为反码为 11...1000
  4. 最后再把反码转原码为 10...0111,即为 -7

常见使用

  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;

不借助第三个变量,如何交换两个变量的值

// a = 5, b = 7
a = a ^ b;
b = a ^ b;
a = a ^ b;

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,得到的数转成十进制即为那瓶毒药的编号。