java 位运算的一些应用

位运算在日常编码中很少用到,所以尝试探究位运算的应用。

感谢:http://xxgblog.com/2013/09/15/java-bitmask/

 

一、优化运算速度

最近看java的一些底层实现,发现运算操作基本都是位运算。

比如ArrayList中的扩容方法grow(),需要让数组大小扩大至原来的1.5倍。因为计算的是数组的大小,所以结果必须为int,我估计会这样写:

javap一下:

6

可以看到bipush和ldc2_w准备了两个double,通过dmul指令计算10 * 1.5,并将结果压入了栈顶。

在源码中,却使用了位运算:

javap一下:

6

可以看到只有ishr位移操作和iadd相加操作。

只看代码似乎看不出什么区别…进行计算测试:

结果为:

在效率上存在细微差别。我个人认为,位运算更贴近机器语言,所以运算效率更高。

那么问题来了,为了提升这一点效率而使用位运算,是否值得呢?

使用oldCapacity + (oldCapacity >> 1)确实比oldCapacity * 1.5效率更高,但是确实失去了一部分可读性,具体使用还需见仁见智。

二、优化算法

此节内容涉及一些算法技巧,也可以理解为“找规律”。

(1)判断某数是否为奇数

我会这样写:

这里存在一个陷阱,一旦某数是负数,那就糟糕了。负数不能取模,导致无法识别为负数的奇数。所以还要做负数的判断:

但是,如果使用位运算,完全可以这样实现:

(2)判断某数是否为2的n次方幂

我会这样写:

这并不是最好的解决方案。如果从位运算的角度来看这个问题,会有以下解决方案(这里只列举部分解法):

1.二进制的所有位中都只有一个1

2 -> 10
4 -> 100
13 -> 1101
16 -> 10000
32 -> 100000

只要是2的n次方的整数,它的二进制的所有位中都只有一个1,并且这个1肯定在最高位。现在问题变成了:“如何计算二进制位中1的个数”。如果只有1位,那么这个数肯定是2的n次方。

于是有这样一种思路:首先计算num & 1,如果num的二进制最后一位为1,那么计算结果肯定为1,记录次数+1(如果结果为0就不需要记录),然后让num右移一位,再次进行计算。通过遍历整个num,就可以计算出num中1的个数。

把“判断某数是否2的n次方”转换为“计算某数中含有多少个1”,是非常聪明的做法。

2.(n)&(n-1)=0(进阶)

以4(100)、7(0111)、8(1000)为例:

4 & 3 -> 100 & 011 = 0

7 & 6 -> 0111 & 0110 != 0

8 & 7 -> 1000 & 0111 = 0

只要n & (n-1)为0,n必定是2的n次方。可以改变算法如下:

这种规律可能比较难想,但是好的算法就是如此简单精悍。

三、优化业务

(1)使用位运算表示事物的整体状态

位运算中存在大量的0和1,0和1可以代表“是否”,即可以表现事物的状态。

先看一道面试题:

参考:https://www.zhihu.com/question/19676641

有1000个一模一样的瓶子,其中有999瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后挂掉。现在,你只有10只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?

很明显小白鼠的数量和时间都存在限制,所以必须使用一定的策略。刚看这道题的人可能会有点懵逼(当时我也是这样…),但是接触过的人肯定知道,这道题在考二进制。

其解答为:根据2^10=1024,所以10个老鼠可以确定1000个瓶子具体哪个瓶子有毒。具体实现跟3个老鼠确定8个瓶子原理一样。

000 = 0
001 = 1 // 只有老鼠1吃了瓶1中的药,如果只有老鼠1挂了,证明瓶1有毒
010 = 2
011 = 3 // 只有老鼠1、2吃了瓶3中的药。如果只用老鼠1、2挂了,证明瓶3有毒
100 = 4
101 = 5
110 = 6
111 = 7

一位表示一个老鼠,0-7表示8个瓶子。也就是分别将1、3、5、7号瓶子的药混起来给老鼠1吃,2、3、6、7号瓶子的药混起来给老鼠2吃,4、5、6、7号瓶子的药混起来给老鼠3吃,哪个老鼠挂了,相应的位标为1。如果老鼠1挂了、老鼠2没挂、老鼠3挂了,那么就是101=5号瓶子有毒。同样的道理,10个老鼠可以确定1000个瓶子。

老鼠的状态(也就是0、1)就表示了哪瓶药有毒。我们可以发散思维,一个老鼠的状态就是单独的0或1,通过多只老鼠状态的组合,就可以表示出对象的整体状态(哪个瓶子中的药有毒)。

(2)使用位运算的思想进行设计

有这样一个需求,需要展示某角色对数据的操作权限(增删改查),应该如何设计?

1.普通的设计

一般我们会这样设计:使用四个boolean分别表示四种操作权限,如果允许为true,不允许则为false,默认情况下为false。

因为状态单独占据四个字段,所以要这样设计数据库:

6

2.使用位运算的思想进行设计

核心思想是使用int表示四种操作的权限,允许为1,不允许为0。可以这样设计:

通过四种状态的组合,只需要一个int就能表现当前用户角色所拥有的权限:
flag 删除 修改 新增 查询
1(0001) 0 0 0 1 只允许查询(即等于ALLOW_SELECT)
2(0010) 0 0 1 0 只允许新增(即等于ALLOW_INSERT)
4(0100) 0 1 0 0 只允许修改(即等于ALLOW_UPDATE)
8(1000) 1 0 0 0 只允许删除(即等于ALLOW_DELETE)
3(0011) 0 0 1 1 只允许查询和新增
0 0 0 0 0 四项权限都不允许
15(1111) 1 1 1 1 四项权限都允许

因此数据库可以这样设计:

7

查询角色是否拥有某权限时,只需要获取角色的整体权限status,通过isAllow方法即可取得:


这两种设计一对比,第二种设计的数据库无疑更加轻巧。问题是该结构不够直观,需要开发人员对此种设计有充分的理解。

四、总结

个人认为,如果不是性能要求特别高,不需要刻意使用位运算。相比之下,可读性可能会更加重要,两者需要权衡。

发表评论

电子邮件地址不会被公开。 必填项已用*标注