java 位运算的一些应用 2017年5月23日
未分类
0 条评论

java 位运算的一些应用

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

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

 

一、优化运算速度

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

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

1
int newCapacity = (int) (oldCapacity * 1.5);

javap一下：

6

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

在源码中，却使用了位运算：

1
int newCapacity = oldCapacity + (oldCapacity >> 1);

javap一下：

6

可以看到只有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个瓶子原理一样。

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。

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;
}
}

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

6

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;
}
}

通过四种状态的组合，只需要一个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方法即可取得：

1
2
3
4
5
6
/**
* 是否拥某些权限
*/
public boolean isAllow(int permission) {
return (flag & permission) == permission;
}

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

四、总结

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