java 位运算的一些应用
位运算在日常编码中很少用到,所以尝试探究位运算的应用。
感谢:http://xxgblog.com/2013/09/15/java-bitmask/
一、优化运算速度
最近看java的一些底层实现,发现运算操作基本都是位运算。
比如ArrayList中的扩容方法grow(),需要让数组大小扩大至原来的1.5倍。因为计算的是数组的大小,所以结果必须为int,我估计会这样写:
1 |
int newCapacity = (int) (oldCapacity * 1.5); |
javap一下:
可以看到bipush和ldc2_w准备了两个double,通过dmul指令计算10 * 1.5,并将结果压入了栈顶。
在源码中,却使用了位运算:
1 |
int newCapacity = oldCapacity + (oldCapacity >> 1); |
javap一下:
可以看到只有ishr位移操作和iadd相加操作。
只看代码似乎看不出什么区别…进行计算测试:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
package testBitwise; public class Test { public static void getBitwiseTime() { int num = 15; long time = System.currentTimeMillis(); for (int i = 0; i < 100000; i++) { num = (int) (num * 1.5); } System.out.println("getNormalTime:" + (System.currentTimeMillis() - time)); } public static void getNormalTime() { int num = 15; long time = System.currentTimeMillis(); for (int i = 0; i < 100000; i++) { num = num + (num >> 1); } System.out.println("getBitwiseTime:" + (System.currentTimeMillis() - time)); } public static void main(String[] args) { getBitwiseTime(); getNormalTime(); } } |
结果为:
1 2 |
getNormalTime:4 getBitwiseTime:2 |
在效率上存在细微差别。我个人认为,位运算更贴近机器语言,所以运算效率更高。
那么问题来了,为了提升这一点效率而使用位运算,是否值得呢?
使用oldCapacity + (oldCapacity >> 1)确实比oldCapacity * 1.5效率更高,但是确实失去了一部分可读性,具体使用还需见仁见智。
二、优化算法
此节内容涉及一些算法技巧,也可以理解为“找规律”。
(1)判断某数是否为奇数
我会这样写:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
package testBitwise; public class NewTest { public static void main(String[] args) { int num = 5; if ((num % 2) == 1) { System.out.println(num); } } } |
这里存在一个陷阱,一旦某数是负数,那就糟糕了。负数不能取模,导致无法识别为负数的奇数。所以还要做负数的判断:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
package testBitwise; public class NewTest { public static void main(String[] args) { int num = -3; if (num < 0) { num = -num; } if ((num % 2) == 1) { System.out.println(num); } } } |
但是,如果使用位运算,完全可以这样实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
package testBitwise; public class NewTest { public static void main(String[] args) { int num = -3; if ((num & 1) == 1) { System.out.println(num); } } } |
(2)判断某数是否为2的n次方幂
我会这样写:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
package testBitwise; public class NewTest { public static boolean validate(int num) { if (num <= 0) { return false; } else if (num == 1) { return true; } else { do { if (num % 2 == 0) { num = num / 2; } else { return false; } } while (num != 1); return true; } } public static void main(String[] args) { System.out.println(validate(1024)); } } |
这并不是最好的解决方案。如果从位运算的角度来看这个问题,会有以下解决方案(这里只列举部分解法):
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的个数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
package testBitwise; public class NewTest { public static boolean validate(int num) { int count = 0; if (num < 0) { return false; } while (num != 0) { if ((num & 1) == 1) { // 当前末尾数为1 count++; // 记录次数 } num >>= 1; // 数据右移一位,去掉已记录的末尾 } return count == 1; } public static void main(String[] args) { System.out.println(validate(2)); } } |
把“判断某数是否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 2 3 4 5 6 7 8 9 10 11 12 13 14 |
package testBitwise; public class NewTest { public static boolean validate(int num) { return ((num > 0) && ((num & (num - 1)) == 0)); } public static void main(String[] args) { System.out.println(validate(1024)); } } |
这种规律可能比较难想,但是好的算法就是如此简单精悍。
三、优化业务
(1)使用位运算表示事物的整体状态
位运算中存在大量的0和1,0和1可以代表“是否”,即可以表现事物的状态。
先看一道面试题:
参考:https://www.zhihu.com/question/19676641
有1000个一模一样的瓶子,其中有999瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后挂掉。现在,你只有10只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?
很明显小白鼠的数量和时间都存在限制,所以必须使用一定的策略。刚看这道题的人可能会有点懵逼(当时我也是这样…),但是接触过的人肯定知道,这道题在考二进制。
其解答为:根据2^10=1024,所以10个老鼠可以确定1000个瓶子具体哪个瓶子有毒。具体实现跟3个老鼠确定8个瓶子原理一样。
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。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
package testBitwise; public class TestAuth { public static boolean ALLOW_SELECT = false; public static boolean ALLOW_INSERT = false; public static boolean ALLOW_UPDATE = false; public static boolean ALLOW_DELETE = false; public static boolean isALLOW_SELECT() { return ALLOW_SELECT; } public static void setALLOW_SELECT(boolean aLLOW_SELECT) { ALLOW_SELECT = aLLOW_SELECT; } public static boolean isALLOW_INSERT() { return ALLOW_INSERT; } public static void setALLOW_INSERT(boolean aLLOW_INSERT) { ALLOW_INSERT = aLLOW_INSERT; } public static boolean isALLOW_UPDATE() { return ALLOW_UPDATE; } public static void setALLOW_UPDATE(boolean aLLOW_UPDATE) { ALLOW_UPDATE = aLLOW_UPDATE; } public static boolean isALLOW_DELETE() { return ALLOW_DELETE; } public static void setALLOW_DELETE(boolean aLLOW_DELETE) { ALLOW_DELETE = aLLOW_DELETE; } } |
因为状态单独占据四个字段,所以要这样设计数据库:
2.使用位运算的思想进行设计
核心思想是使用int表示四种操作的权限,允许为1,不允许为0。可以这样设计:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
package testBitwise; public class TestAuth { // 是否允许查询,二进制第1位,0表示否,1表示是 public static final int ALLOW_SELECT = 1 << 0; // 0001 // 是否允许新增,二进制第2位,0表示否,1表示是 public static final int ALLOW_INSERT = 1 << 1; // 0010 // 是否允许修改,二进制第3位,0表示否,1表示是 public static final int ALLOW_UPDATE = 1 << 2; // 0100 // 是否允许删除,二进制第4位,0表示否,1表示是 public static final int ALLOW_DELETE = 1 << 3; // 1000 // 存储目前的权限状态 private int flag; /** * 重新设置权限 */ public void setPermission(int permission) { flag = permission; } /** * 添加一项或多项权限 */ public void enable(int permission) { flag |= permission; } /** * 删除一项或多项权限 */ public void disable(int permission) { flag &= ~permission; } /** * 是否拥某些权限 */ public boolean isAllow(int permission) { return (flag & permission) == permission; } /** * 是否禁用了某些权限 */ public boolean isNotAllow(int permission) { return (flag & permission) == 0; } /** * 是否仅仅拥有某些权限 */ public boolean isOnlyAllow(int permission) { return flag == permission; } } |
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 | 四项权限都允许 |
因此数据库可以这样设计:
查询角色是否拥有某权限时,只需要获取角色的整体权限status,通过isAllow方法即可取得:
1 2 3 4 5 6 |
/** * 是否拥某些权限 */ public boolean isAllow(int permission) { return (flag & permission) == permission; } |
这两种设计一对比,第二种设计的数据库无疑更加轻巧。问题是该结构不够直观,需要开发人员对此种设计有充分的理解。