位运算（位掩码BitMask）的简单应用场景浅析

在Java中，位运算符有：与（&）、非（~）、或（|）、异或（^）、移位（<< 和 >>）、无符移位（<<< 和 >>>）。这些运算符在日常编码中运用并不多，但在看 Android 源码时发现其运用并不少，那么位运算究竟有什么利弊，合适的应用场景是什么呢？下面我们通过例子来进行探讨。

简单的例子

例如，在一个系统中，用户一般有查询(Select)、新增(Insert)、修改(Update)、删除(Delete)四种权限，四种权限有多种组合方式，也就是有16中不同的权限状态（2的4次方）。

一般情况下会想到用四个boolean类型变量来保存：

public class Permission {

    // 是否允许查询
    private boolean allowSelect;

    // 是否允许新增
    private boolean allowInsert;

    // 是否允许删除
    private boolean allowDelete;

    // 是否允许更新
    private boolean allowUpdate;

    // 省略Getter和Setter
}

上面用四个boolean类型变量分别来保存每种权限状态。

通过位掩码实现

使用位掩码的话，用一个二进制数即可，每一位来表示一种权限，0表示无权限，1表示有权限。具体代码如下：

public class NewPermission {

    // 是否允许查询，二进制第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;
    }
}

以上代码中，用四个常量表示了每个二进制位代码的权限项。

ALLOW_SELECT = 1 << 0 转成二进制就是0001，二进制第一位表示Select权限。
ALLOW_INSERT = 1 << 1 转成二进制就是0010，二进制第二位表示Insert权限。

private int flag存储了各种权限的启用和停用状态，相当于代替了Permission中的四个boolean类型的变量。

用flag的四个二进制位来表示四种权限的状态，每一位的0和1代表一项权限的启用和停用，下面列举了部分状态表示的权限：

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	四项权限都允许

使用位掩码的方式，只需要用一个大于或等于0且小于16的整数即可表示所有的16种权限的状态。

此外，设置权限和判断权限的方法可以通过位运算实现，例如：

  public void enable(int permission) {
        flag |= permission;
    }

调用这个方法可以在现有的权限基础上添加一项或多项权限。

1. 添加一项权限：

   permission.enable(NewPermission.ALLOW_UPDATE);
   

   假设现有权限只有Select，也就是flag是0001。执行以上代码，flag = 0001 | 0100，也就是0101，便拥有了Select和Update两项权限。

2. 添加多项权限：

   permission.enable(NewPermission.ALLOW_INSERT 
       | NewPermission.ALLOW_UPDATE | NewPermission.ALLOW_DELETE);
   
   

   NewPermission.ALLOW_INSERT | NewPermission.ALLOW_UPDATE | NewPermission.ALLOW_DELETE运算结果是1110。假设现有权限只有Select，也就是flag是0001。flag = 0001 | 1110，也就是1111，便拥有了这四项权限，相当于添加了三项权限。

二者对比

1. 设置仅允许Select和Insert权限

   Permission：

   permission.setAllowSelect(true);
   permission.setAllowInsert(true);
   permission.setAllowUpdate(false);
   permission.setAllowDelete(false);
   

   NewPermission:

   permission.setPermission(NewPermission.ALLOW_SELECT | NewPermission.ALLOW_INSERT);
   

2. 判断是否允许Select，Insert和Update权限

   Permission：

   if (permission.isAllowSelect() && permission.isAllowInsert() && permission.isAllowUpdate())
   

   NewPermission:

   if (permission. isAllow (NewPermission.ALLOW_SELECT 
       | NewPermission.ALLOW_INSERT | NewPermission.ALLOW_UPDATE))
   

3. 判断是否只允许Select和Insert权限

   Permission：

   if (permission.isAllowSelect() && permission.isAllowInsert() 
       && !permission.isAllowUpdate() && !permission.isAllowDelete())
   

   NewPermission:

   if (permission. isOnlyAllow (NewPermission.ALLOW_SELECT | NewPermission.ALLOW_INSERT))
   

二者对比可以感受到NewPermission位掩码方式相对于Permission的优势，可以节省很多代码量，位运算是底层运算，效率也非常高，而且理解起来也很简单。

小白鼠试药问题

我们先来看一道很常用被问到的面试题:

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

根据2^9 < 1000 < 2^10=1024，所以10个老鼠可以确定1000个瓶子具体哪个瓶子有毒。具体实现跟3个老鼠确定8个瓶子原理一样。二进制表示如下：

二进制编码	十进制
000	0
001	1
010	2
011	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个瓶子（2^9 < 1000 < 2^10）

位运算符

1、左移运算符：<<

value << num ： num 指定要移位值value 移动的位数。

左移的规则只记住一点：丢弃最高位，0补最低位

如果移动的位数超过了该类型的最大位数，那么编译器会对移动的位数取模

1 ) 运算规则
按二进制形式把所有的数字向左移动对应的位数，高位移出(舍弃)，低位的空位补零。
当左移的运算数是int 类型时，每移动1位它的第31位就要被移出并且丢弃；
当左移的运算数是long 类型时，每移动1位它的第63位就要被移出并且丢弃。
当左移的运算数是byte 和short类型时，将自动把这些类型扩大为 int 型。

2 ）数学意义
在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方

3 ）示例
先随便定义一个int类型的数int，十进制的value = 733183670，转换成二进制在计算机中的表示如下：

image

value << 1，左移1位

image

左移1位后换算成十进制的值为：1466367340，刚好是733183670的两倍， 有些人在乘2操作时喜欢用左移运算符来替代。

image
左移8位后变成了十进制的值为：-1283541504，移动8位后，由于首位变成了1，也就是说成了负数，在使用中要考虑变成负数的情况。

根据这个规则，左移32位后，右边补上32个0值是不是就变成了十进制的0了？答案是NO，当int类型进行左移操作时，左移位数大于等于32位操作时，会先求余（%）后再进行左移操作。也就是说左移32位相当于不进行移位操作，左移40位相当于左移8位（40%32=8）。当long类型进行左移操作时，long类型在二进制中的体现是64位的，因此求余操作的基数也变成了64，也就是说左移64位相当于没有移位，左移72位相当于左移8位（72 % 64 = 8 ）。

2、右移运算符：>>

value >> num：num 指定要移位值value 移动的位数。

右移的规则只记住一点：符号位不变，左边补上符号位

如果移动的位数超过了该类型的最大位数，那么编译器会对移动的位数取模

1）运算规则：
按二进制形式把所有的数字向右移动对应的位数，低位移出(舍弃)，高位的空位补符号位，即正数补零，负数补1（符号位扩展（保留符号位sign extension ））
当右移的运算数是byte 和short类型时，将自动把这些类型扩大为 int 型。

2 ）数学意义
在数字没有溢出的前提下，右移一位相当于除2，右移n位相当于除以2的n次方。

3 ）示例

还是这个数：733183670

image
value >> 1，右移1位
image
右移1位后换算成十进制的值为：366591835，刚好是733183670的1半， 有些人在除2操作时喜欢用右移运算符来替代。
value >> 8，右移8位看一下
image
和左移一样，int类型移位大于等于32位时，long类型大于等于64位时，会先做求余处理再位移处理，byte，short移位前会先转换为int类型（32位）再进行移位。以上是正数的位移，我们再来看看负数的右移运算，如图，负数intValue：-733183670的二进制表现如下图：
image
右移8位，intValue >> 8
image

3、无符号右移运算符：>>>

value >>> num：num 指定要移位值value 移动的位数。

无符号右移的规则只记住一点：忽略了符号位扩展，0补最高位

如果移动的位数超过了该类型的最大位数，那么编译器会对移动的位数取模

其他与右移运算符一样

1 ）示例

以-733183670>>>8为例来画一下图

image

4、按位与&

只有两个操作数对应位同为1时，结果为1，其余全为0. （或者是只要有一个操作数为0，结果就为0）

5、按位或|

只有两个操作数对应位同为0时，结果为0，其余全为1.（或者是只要有一个操作数为1，结果就为1）

6、按位非~

对操作数每位进行取反

7、按位异或 ^

只有两个操作数对应位不同即为1

位运算实际运用

1、判断奇偶

    public static boolean isOdd(int a) {
        return (a & 1) != 0;
    }

2、数据交换

    public static void swap(int a, int b){
        a^=b;
        b^=a;
        a^=b;
    }

3、求绝对值

    public static int abs(int x) {
        int y;
        y = x >> 31;
        return (x ^ y) - y;        //or: (x+y)^y
    }

4、byte与十六进制数的转换

转换原理

Java中byte每个字符是由8个bit组成的，而16进制中每个字符由4个bit组成的[16进制中最大为:0xF(15)转为二进制为：1111组成的4个bit]。所以我们可以把一个byte转换成两个16进制字符，即把高4位和低4位转换成相应的16进制字符，并组合这两个16进制字符串，从而得到byte的16进制字符串。同理，相反的转换也是将两个16进制字符转换成一个byte。

    public static String byteArrayToHexString(byte[] data) {
        StringBuilder sb = new StringBuilder(data.length * 2);
        for (byte b : data) {
            int v = b & 0xff;
            if (v < 16) {
                sb.append('0');
            }
            sb.append(Integer.toHexString(v));
        }
        return sb.toString();
    }

参考

• https://zhuanlan.zhihu.com/p/30108890
• http://xxgblog.com/2013/09/15/java-bitmask/