位運算（位掩碼BitMask）的簡單應(yīng)用場景淺析

在Java中例嘱，位運算符有：與（&）狡逢、非（~）、或（|）拼卵、異或（^）奢浑、移位（<< 和 >>）、無符移位（<<< 和 >>>）腋腮。這些運算符在日常編碼中運用并不多雀彼，但在看 Android 源碼時發(fā)現(xiàn)其運用并不少，那么位運算究竟有什么利弊低葫，合適的應(yīng)用場景是什么呢详羡？下面我們通過例子來進(jìn)行探討。

簡單的例子

例如嘿悬，在一個系統(tǒng)中实柠，用戶一般有查詢(Select)、新增(Insert)善涨、修改(Update)窒盐、刪除(Delete)四種權(quán)限草则，四種權(quán)限有多種組合方式，也就是有16中不同的權(quán)限狀態(tài)（2的4次方）蟹漓。

一般情況下會想到用四個boolean類型變量來保存：

public class Permission {

    // 是否允許查詢
    private boolean allowSelect;

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

    // 是否允許刪除
    private boolean allowDelete;

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

    // 省略Getter和Setter
}

上面用四個boolean類型變量分別來保存每種權(quán)限狀態(tài)炕横。

通過位掩碼實現(xiàn)

使用位掩碼的話，用一個二進(jìn)制數(shù)即可葡粒，每一位來表示一種權(quán)限份殿，0表示無權(quán)限，1表示有權(quán)限嗽交。具體代碼如下：

public class NewPermission {

    // 是否允許查詢卿嘲，二進(jìn)制第1位，0表示否夫壁，1表示是
    public static final int ALLOW_SELECT = 1 << 0; // 0001

    // 是否允許新增拾枣，二進(jìn)制第2位，0表示否盒让，1表示是
    public static final int ALLOW_INSERT = 1 << 1; // 0010

    // 是否允許修改梅肤，二進(jìn)制第3位，0表示否邑茄，1表示是
    public static final int ALLOW_UPDATE = 1 << 2; // 0100

    // 是否允許刪除姨蝴，二進(jìn)制第4位，0表示否肺缕，1表示是
    public static final int ALLOW_DELETE = 1 << 3; // 1000

    // 存儲目前的權(quán)限狀態(tài)
    private int flag;

    /**
     * 重新設(shè)置權(quán)限
     */
    public void setPermission(int permission) {
        flag = permission;
    }

    /**
     * 添加一項或多項權(quán)限
     */
    public void enable(int permission) {
        flag |= permission;
    }

    /**
     * 移除一項或多項權(quán)限
     */
    public void disable(int permission) {
        flag &= ~permission;
    }

    /**
     * 是否擁有某項權(quán)限
     */
    public boolean isAllow(int permission) {
        return (flag & permission) == permission;
    }

    /**
     * 是否禁用了某些權(quán)限
     */
    public boolean isNotAllow(int permission) {
        return (flag & permission) == 0;
    }

    /**
     *  是否僅僅擁有某些權(quán)限
     */
    public boolean isOnlyAllow(int permission) {
        return flag == permission;
    }
}

以上代碼中似扔，用四個常量表示了每個二進(jìn)制位代碼的權(quán)限項。

ALLOW_SELECT = 1 << 0 轉(zhuǎn)成二進(jìn)制就是0001搓谆，二進(jìn)制第一位表示Select權(quán)限炒辉。
ALLOW_INSERT = 1 << 1 轉(zhuǎn)成二進(jìn)制就是0010，二進(jìn)制第二位表示Insert權(quán)限泉手。

private int flag存儲了各種權(quán)限的啟用和停用狀態(tài)黔寇，相當(dāng)于代替了Permission中的四個boolean類型的變量。

用flag的四個二進(jìn)制位來表示四種權(quán)限的狀態(tài)斩萌，每一位的0和1代表一項權(quán)限的啟用和停用缝裤，下面列舉了部分狀態(tài)表示的權(quán)限：

flag	刪除	修改	新增	查詢	權(quán)限
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	四項權(quán)限都不允許
15(1111)	1	1	1	1	四項權(quán)限都允許

使用位掩碼的方式，只需要用一個大于或等于0且小于16的整數(shù)即可表示所有的16種權(quán)限的狀態(tài)颊郎。

此外憋飞，設(shè)置權(quán)限和判斷權(quán)限的方法可以通過位運算實現(xiàn)，例如：

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

調(diào)用這個方法可以在現(xiàn)有的權(quán)限基礎(chǔ)上添加一項或多項權(quán)限姆吭。

添加一項權(quán)限：
```
permission.enable(NewPermission.ALLOW_UPDATE);
```
假設(shè)現(xiàn)有權(quán)限只有Select榛做，也就是flag是0001。執(zhí)行以上代碼，flag = 0001 | 0100检眯，也就是0101厘擂，便擁有了Select和Update兩項權(quán)限。
添加多項權(quán)限：
```
permission.enable(NewPermission.ALLOW_INSERT 
    | NewPermission.ALLOW_UPDATE | NewPermission.ALLOW_DELETE);
```
NewPermission.ALLOW_INSERT | NewPermission.ALLOW_UPDATE | NewPermission.ALLOW_DELETE運算結(jié)果是1110锰瘸。假設(shè)現(xiàn)有權(quán)限只有Select刽严，也就是flag是0001。flag = 0001 | 1110避凝，也就是1111舞萄，便擁有了這四項權(quán)限，相當(dāng)于添加了三項權(quán)限管削。

二者對比

設(shè)置僅允許Select和Insert權(quán)限

Permission：

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

NewPermission:

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

判斷是否允許Select鹏氧，Insert和Update權(quán)限

Permission：

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

NewPermission:

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

判斷是否只允許Select和Insert權(quán)限

Permission：

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

NewPermission:

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

二者對比可以感受到NewPermission位掩碼方式相對于Permission的優(yōu)勢，可以節(jié)省很多代碼量佩谣，位運算是底層運算，效率也非常高实蓬，而且理解起來也很簡單茸俭。

小白鼠試藥問題

我們先來看一道很常用被問到的面試題:

有 1000 個一模一樣的瓶子，其中有 999 瓶是普通的水安皱，有一瓶是毒藥调鬓。任何喝下毒藥的生物都會在一星期之后死亡。現(xiàn)在酌伊，你只有 10 只小白鼠和一星期的時間腾窝，如何檢驗出哪個瓶子里有毒藥？

根據(jù)2^9 < 1000 < 2^10=1024居砖，所以10個老鼠可以確定1000個瓶子具體哪個瓶子有毒虹脯。具體實現(xiàn)跟3個老鼠確定8個瓶子原理一樣。二進(jìn)制表示如下：

二進(jìn)制編碼	十進(jìn)制
000	0
001	1
010	2
011	3
100	4
101	5
110	6
111	7

三位的二進(jìn)制編碼位數(shù)中奏候，每一位表示一只老鼠循集，0 - 7 表示8個瓶子。

① 將1蔗草、3咒彤、5、7號瓶子的藥混起來給老鼠1吃

② 將2咒精、3镶柱、6、7號瓶子的藥混起來給老鼠2吃

③ 將4模叙、5歇拆、6、7號瓶子的藥混起來給老鼠3吃

哪個老鼠死了，相應(yīng)的位標(biāo)為1查吊。如老鼠1死了谐区、老鼠2沒死、老鼠3死了逻卖，那么就是101 = 5號瓶子有毒宋列。
同樣道理10個老鼠可以確定1000個瓶子（2^9 < 1000 < 2^10）

位運算符

1、左移運算符：<<

value << num ： num 指定要移位值value 移動的位數(shù)评也。

左移的規(guī)則只記住一點：丟棄最高位炼杖，0補(bǔ)最低位

如果移動的位數(shù)超過了該類型的最大位數(shù)，那么編譯器會對移動的位數(shù)取模

1 ) 運算規(guī)則
按二進(jìn)制形式把所有的數(shù)字向左移動對應(yīng)的位數(shù)盗迟，高位移出(舍棄)坤邪，低位的空位補(bǔ)零。
當(dāng)左移的運算數(shù)是int 類型時罚缕，每移動1位它的第31位就要被移出并且丟棄艇纺；
當(dāng)左移的運算數(shù)是long 類型時，每移動1位它的第63位就要被移出并且丟棄邮弹。
當(dāng)左移的運算數(shù)是byte 和short類型時黔衡，將自動把這些類型擴(kuò)大為 int 型。

2 ）數(shù)學(xué)意義
在數(shù)字沒有溢出的前提下腌乡，對于正數(shù)和負(fù)數(shù)盟劫，左移一位都相當(dāng)于乘以2的1次方，左移n位就相當(dāng)于乘以2的n次方

3 ）示例
先隨便定義一個int類型的數(shù)int与纽，十進(jìn)制的value = 733183670侣签，轉(zhuǎn)換成二進(jìn)制在計算機(jī)中的表示如下：

image

value << 1，左移1位

image

左移1位后換算成十進(jìn)制的值為：1466367340急迂，剛好是733183670的兩倍影所，有些人在乘2操作時喜歡用左移運算符來替代。

image

左移8位后變成了十進(jìn)制的值為：-1283541504僚碎，移動8位后型檀，由于首位變成了1，也就是說成了負(fù)數(shù)听盖，在使用中要考慮變成負(fù)數(shù)的情況胀溺。

根據(jù)這個規(guī)則，左移32位后皆看，右邊補(bǔ)上32個0值是不是就變成了十進(jìn)制的0了仓坞？答案是NO，當(dāng)int類型進(jìn)行左移操作時腰吟，左移位數(shù)大于等于32位操作時无埃，會先求余（%）后再進(jìn)行左移操作徙瓶。也就是說左移32位相當(dāng)于不進(jìn)行移位操作，左移40位相當(dāng)于左移8位（40%32=8）嫉称。當(dāng)long類型進(jìn)行左移操作時侦镇，long類型在二進(jìn)制中的體現(xiàn)是64位的，因此求余操作的基數(shù)也變成了64织阅，也就是說左移64位相當(dāng)于沒有移位壳繁，左移72位相當(dāng)于左移8位（72 % 64 = 8 ）。

2荔棉、右移運算符：>>

value >> num：num 指定要移位值value 移動的位數(shù)闹炉。

右移的規(guī)則只記住一點：符號位不變，左邊補(bǔ)上符號位

如果移動的位數(shù)超過了該類型的最大位數(shù)润樱，那么編譯器會對移動的位數(shù)取模

1）運算規(guī)則：
按二進(jìn)制形式把所有的數(shù)字向右移動對應(yīng)的位數(shù)渣触，低位移出(舍棄)，高位的空位補(bǔ)符號位壹若，即正數(shù)補(bǔ)零嗅钻，負(fù)數(shù)補(bǔ)1（符號位擴(kuò)展（保留符號位sign extension ））
當(dāng)右移的運算數(shù)是byte 和short類型時，將自動把這些類型擴(kuò)大為 int 型店展。

2 ）數(shù)學(xué)意義
在數(shù)字沒有溢出的前提下养篓，右移一位相當(dāng)于除2，右移n位相當(dāng)于除以2的n次方壁查。

3 ）示例

還是這個數(shù)：733183670

image

value >> 1，右移1位

image

右移1位后換算成十進(jìn)制的值為：366591835剔应，剛好是733183670的1半睡腿，有些人在除2操作時喜歡用右移運算符來替代。
value >> 8峻贮，右移8位看一下

image

和左移一樣席怪，int類型移位大于等于32位時，long類型大于等于64位時纤控，會先做求余處理再位移處理挂捻，byte，short移位前會先轉(zhuǎn)換為int類型（32位）再進(jìn)行移位船万。以上是正數(shù)的位移刻撒，我們再來看看負(fù)數(shù)的右移運算，如圖耿导，負(fù)數(shù)intValue：-733183670的二進(jìn)制表現(xiàn)如下圖：

image

右移8位声怔，intValue >> 8

image

3、無符號右移運算符：>>>

value >>> num：num 指定要移位值value 移動的位數(shù)舱呻。

無符號右移的規(guī)則只記住一點：忽略了符號位擴(kuò)展醋火，0補(bǔ)最高位

如果移動的位數(shù)超過了該類型的最大位數(shù)，那么編譯器會對移動的位數(shù)取模

其他與右移運算符一樣

1 ）示例

以-733183670>>>8為例來畫一下圖

image

4、按位與&

只有兩個操作數(shù)對應(yīng)位同為1時芥驳，結(jié)果為1柿冲，其余全為0. （或者是只要有一個操作數(shù)為0，結(jié)果就為0）

5兆旬、按位或|

只有兩個操作數(shù)對應(yīng)位同為0時假抄，結(jié)果為0，其余全為1.（或者是只要有一個操作數(shù)為1爵憎，結(jié)果就為1）

6慨亲、按位非~

對操作數(shù)每位進(jìn)行取反

7、按位異或 ^

只有兩個操作數(shù)對應(yīng)位不同即為1

位運算實際運用

1宝鼓、判斷奇偶

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

2刑棵、數(shù)據(jù)交換

    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與十六進(jìn)制數(shù)的轉(zhuǎn)換

轉(zhuǎn)換原理

Java中byte每個字符是由8個bit組成的蛉签，而16進(jìn)制中每個字符由4個bit組成的[16進(jìn)制中最大為:0xF(15)轉(zhuǎn)為二進(jìn)制為：1111組成的4個bit]。所以我們可以把一個byte轉(zhuǎn)換成兩個16進(jìn)制字符沥寥，即把高4位和低4位轉(zhuǎn)換成相應(yīng)的16進(jìn)制字符碍舍，并組合這兩個16進(jìn)制字符串，從而得到byte的16進(jìn)制字符串邑雅。同理片橡，相反的轉(zhuǎn)換也是將兩個16進(jìn)制字符轉(zhuǎn)換成一個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/