这个运算相当于,对于n-1取与:
这个是一个很经典的位运算运用,广泛用于各种高性能框架。例如在生成缓存队列槽位的时候,一般生成2的n次方个槽位,因为这样在选择槽位的时候,就可以用取与代替取余;java中的ForkJoinPool的队列长度就是定为2的n次方;netty中的缓存池的叶子节点都是2的n次方,当然这也是因为是平衡二叉查找树算法的实现。
我们来看下性能会好多少:
@Benchmark @Warmup(iterations = 0) @Measurement(iterations = 300) public void mod2_n_1(Generator generator) { int result = 0; for (int j = 0; j < generator.divide.length; j++) { int l = generator.divide[j]; result += Integer.MAX_VALUE % l; } } @Benchmark @Warmup(iterations = 0) @Measurement(iterations = 300) public void mod2_n_2(Generator generator) { int result = 0; for (int j = 0; j < generator.divide.length; j++) { int l = generator.divide[j]; result += Integer.MAX_VALUE & (l - 1); } }
结果:
Benchmark Mode Cnt Score Error Units BitUtilTest.mod2_n_1 thrpt 300 10632698.855 ± 5843378.697 ops/s BitUtilTest.mod2_n_2 thrpt 300 80339980.989 ± 21905820.262 ops/s
同时,我们从这里也可以引申出,判断一个数是否是2的n次方的方法,就是看这个数与这个数减一取与运算看是否是0,如果是,则是2的n次方,n为正整数。
进一步的,奇偶性判断就是看对2取余是否为0,那么就相当于对(2-1)=1取与。
4. 求与数字最接近的2的n次方
这个广泛运用于各种API优化,上文中提到,2的n次方是一个好东西。我们在写框架的很多时候,想让用户传入一个必须是2的n次方的参数来初始化某个资源池,但这样不是那么灵活,我们可以通过用户传入的数字N,来找出不大于N的最大的2的n次方,或者是大于N的最小的2的N次方。
抽象为比较直观的理解就是,找一个数字最左边的1的左边一个1(大于N的最小的2的N次方),或者是最左边的1(小于N的最大的2的N次方),前提是这个数字本身不是2的n次方。
那么,如何找呢?一种思路是,将这个数字最高位1之后的所有位都填上1,最后加一,就是大于N的最小的2的N次方。右移一位,就是小于N的最大的2的N次方。
如何填补呢?可以考虑按位或计算,我们知道除了0或0=0以外,其他的都是1. 我们现在有了最左面的1,右移一位,与原来按位或,就至少有了两位是1,再右移两位并按位或,则至少有四位为1。。。以此类推:
用代码表示是:
n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; n += 1; //大于N的最小的2的N次方 n = n >>> 1; //小于N的最大的2的N次方
如果有兴趣,可以看一下Java的ForkJoinPool类的构造器,其中的WorkQueue大小,就是通过这样的转换得来的。
5. 交换两个数字
这个在单片机编程中经常会使用这个位运算性质:一个数字异或自己为零,一个数字异或0为自己本身。那么我们就可以利用这个性质交换两个数字。
假设有数字x,y。 我们有x^y^y = x^(y^y)= x^0 = x
还有x^y^y^x^y = 0^y = y
那么我们可以利用:
x = x ^ y; y = x ^ y; //代入后就是x^y^y x = x ^ y; //代入后就是x^y^y^x^y
这个方法虽然很巧妙,但是是一种时间换空间的方式; 我们常用的利用另一个变量实现交换是一种空间换时间的方式,来对比下性能:
@Benchmark @Warmup(iterations = 0) @Measurement(iterations = 300) public int swap_1() { int x = Integer.MAX_VALUE, y = Integer.MAX_VALUE / 2; int z = x; x = y; y = z; return x + y; } @Benchmark @Warmup(iterations = 0) @Measurement(iterations = 300) public int swap_2() { int x = Integer.MAX_VALUE, y = Integer.MAX_VALUE / 2; x ^= y; y ^= x; x ^= y; return x + y; }
结果:
Benchmark Mode Cnt Score Error Units BitUtilTest.swap_1 thrpt 300 267787894.370 ± 559479133.393 ops/s BitUtilTest.swap_2 thrpt 300 265768807.925 ± 387039155.884 ops/s
测试来看,性能差异并不明显,利用位运算减少了空间占用,减少了GC,但是交换减少了cpu运算,但是GC同样是消耗cpu计算,所以,很难界定。目前还是利用中间变量交换的更常用,也更易读一些。
6. bit状态位
我们为了节省空间,尝尝利用一个数字类型(例如long类型)作为状态数,每一位代表一个状态是true还是false。假设我们使用long类型,则一个状态数可以最多表示64个属性。代码上一般这么写:
public static class Test { //如果你的field是会被并发修改访问,那么最好还是加上缓存行填充防止false sharing @jdk.internal.vm.annotation.Contended private long field; private static final long SWITCH_1_MASK = 1; private static final long SWITCH_2_MASK = 1 << 1; private static final long SWITCH_3_MASK = 1 << 2; public boolean isSwitch1On() { return (field & SWITCH_1_MASK) == 1; } public void turnOnSwitch1() { field |= SWITCH_1_MASK; } public void turnOffSwitch1() { field &= ~SWITCH_1_MASK; } }
这样能节省大量空间,在实际应用中,很多地方做了这种优化。最直接的例子就是,Java对象的对象头:
|-------------------------------------------------------|--------------------| | Mark Word (32 bits) | State | |-------------------------------------------------------|--------------------| | identity_hashcode:25 | age:4 | biased_lock:1 | lock:2 | Normal | |-------------------------------------------------------|--------------------| | thread:23 | epoch:2 | age:4 | biased_lock:1 | lock:2 | Biased | |-------------------------------------------------------|--------------------| | ptr_to_lock_record:30 | lock:2 | Lightweight Locked | |-------------------------------------------------------|--------------------| | ptr_to_heavyweight_monitor:30 | lock:2 | Heavyweight Locked | |-------------------------------------------------------|--------------------| | | lock:2 | Marked for GC | |-------------------------------------------------------|--------------------|
7. 位计数
基于6,有时候我们想某个状态数里面,有多少个状态是true,就是计算这个状态数里面多少位是1.
比较朴素的方法就是:先判断n的奇偶性,为奇数时计数器增加1,然后将n右移一位,重复上面的步骤,直到移位完毕。
高效一点的方法通过:
n & (n - 1)
可以移除最后一位1 (假设最后一位本来是0, 减一后必为1,0 & 1为 0, 最后一位本来是1,减一后必为0,0 & 1为 0)- 移除了最后一位1之后,计数加1,如果结果不为零,则用结果继续第一步。
int n = Integer.MAX_VALUE; int count = 0; while(n != 0) { n &= n -1; count++; }