Bitwise Operation導(dǎo)語

眾所周知計(jì)算機(jī)是基于二進(jìn)制01進(jìn)行運(yùn)算的，理所當(dāng)然地，位運(yùn)算相對于各種算術(shù)運(yùn)算更加貼合計(jì)算機(jī)的二進(jìn)制語義，運(yùn)算效率會更快。這樣計(jì)算機(jī)是舒服了，人類讀起來就太生澀了，所以這是把雙刃劍。好的代碼本身就要Trade Off計(jì)算效率性和代碼可讀性。

我們經(jīng)常會用移位運(yùn)算(Bit Shift)比如左移或者右移來分別實(shí)現(xiàn)乘法或者除法運(yùn)算，但是很多人會忽略左移是有可能造成數(shù)據(jù)越界，必然需要做好程序?qū)用娴目刂?，否則這種BUG太容易被掩蓋。下面的章節(jié)我會列舉一些常見的位運(yùn)算場景，供大家參考。

基本概念

開始前先把Java位運(yùn)算的基本概念提一下下：

bit operators.png

運(yùn)算符的優(yōu)先級：~ 的優(yōu)先級最高，其次是 <<、>> 和 >>>，再次是＆，然后是 ^，優(yōu)先級最低的是 |。

關(guān)于負(fù)數(shù)的二進(jìn)制轉(zhuǎn)換，采用的 補(bǔ)碼 規(guī)則，有興趣的同學(xué)可以研究一下它背后的數(shù)學(xué)意義。

Linux 權(quán)限控制

image.png

Linux的日常，無處不見上圖中的文件權(quán)限，而這個(gè)權(quán)限控制的原理就是使用的二進(jìn)制位運(yùn)算。Linux中的權(quán)限有點(diǎn)像三權(quán)分立，分別是讀、寫、執(zhí)行。

access.png

實(shí)現(xiàn)原理也很簡單，r w x 三個(gè)權(quán)限分別對應(yīng)三位的二進(jìn)制標(biāo)志位。如下圖，“執(zhí)行X”權(quán)限使用二進(jìn)制為001，即：八進(jìn)制1?！皩懭隬”權(quán)限使用二進(jìn)制為010，即：八進(jìn)制2。“讀取R”權(quán)限使用二進(jìn)制為100，即：八進(jìn)制4。

前面提到的三權(quán)分立也就是考慮到三者分別在不同的標(biāo)志位上，相互完全獨(dú)立。由此展開我們的權(quán)限管理ING:

1 添加權(quán)限

增加權(quán)限使用 或（|） 運(yùn)算實(shí)現(xiàn)。
如，為某用戶增加“讀取”、“寫入”兩種權(quán)限。
“讀寫”兩種權(quán)限，權(quán)限碼為6（110），本質(zhì)是由權(quán)限碼2（010）和4（100）進(jìn)行或（|）運(yùn)算后實(shí)現(xiàn)，即6 = 2 | 4，當(dāng)然直觀也可以視作基本的算術(shù)加 6 = 2 + 4 計(jì)算得出。

2 判斷權(quán)限

在需要判斷用戶權(quán)限時(shí)，可使用 與（&） 運(yùn)算。
如，判斷權(quán)限碼為6用戶是否有讀取權(quán)限。權(quán)限碼6（110）和4（100）的與運(yùn)算結(jié)果為4，即：4 = 6 & 4。
如，判斷權(quán)限碼為6用戶是否有執(zhí)行權(quán)限。權(quán)限碼6（110）和1（001）的與運(yùn)算結(jié)果為0，即：0 = 6 & 1。

總結(jié)下就是，當(dāng)與運(yùn)算結(jié)果為所要判斷權(quán)限的本身值時(shí)，我們可以認(rèn)為用戶具有這個(gè)權(quán)限。而當(dāng)運(yùn)算結(jié)果為 0 時(shí)，我們可以認(rèn)為用戶不具有這個(gè)權(quán)限。

3 移除權(quán)限

移除用戶的權(quán)限可使用 異或（^） 運(yùn)算。
如，將權(quán)限碼為7的用戶，移除執(zhí)行權(quán)限。權(quán)限碼7（111）和1（001）的異或運(yùn)算結(jié)果為6，即：6 = 7 ^ 1，也可以由算術(shù)減 6 = 7 - 1計(jì)算得出。

Linux "umask"命令指定在建立文件時(shí)預(yù)設(shè)的權(quán)限掩碼，而掩碼就是用來移除權(quán)限的。比如大部分系統(tǒng)運(yùn)行umask輸出的是“002”或者“0002”, 表示默認(rèn)去掉了其他用戶的寫權(quán)限。

從上面的介紹可以看出，在基于位運(yùn)算的權(quán)限管理系統(tǒng)中，每種權(quán)限碼都是唯一的；而且要求每個(gè)權(quán)限碼的二進(jìn)制數(shù)形式，都只能有一位值為1。簡單的說，權(quán)限碼都是2的冪數(shù)。

基于位運(yùn)算的權(quán)限管理，優(yōu)點(diǎn)很明顯：運(yùn)算速度快、效率高、節(jié)省存儲空間、對權(quán)限控制非常靈活。而且擴(kuò)展性也不錯(cuò)，隨時(shí)可以擴(kuò)展新的標(biāo)志位。除了權(quán)限，有些可以組合的業(yè)務(wù)類型也可以通過這種獨(dú)立位運(yùn)算的方式來實(shí)現(xiàn)。

BitMask 位掩碼

這里我們延展到另一個(gè)概念: 位掩碼BitMask。Linux權(quán)限就是位掩碼的一種特例。我們這里再看一種典型的位掩碼實(shí)現(xiàn)。

搞研發(fā)的同學(xué)對于fastjson這個(gè)阿里巴巴的開源組件應(yīng)該很熟悉吧？ 我們經(jīng)常會用它來做一些請求/應(yīng)答數(shù)據(jù)的序列化和反序列化。在序列化的場景，我們可能會用一些特別的features來滿足特定需求，比如：

// 按照類的屬性名排序輸出
JSON.toJSONString(obj, SerializerFeature.SortField)
// 輸出標(biāo)準(zhǔn)格式的日期格式
JSON.toJSONString(obj, SerializerFeature.WriteDateUseDateFormat)

如果需要多種feature組合的話，只要傳入一個(gè)feature數(shù)組即可。那么fastjson如何做到對feature的管理有如Linux權(quán)限那般的靈活和可擴(kuò)展的呢？我們先看下 SerializerFeature 這個(gè)枚舉類的實(shí)現(xiàn)：

public enum SerializerFeature {
QuoteFieldNames,
UseSingleQuotes,
WriteMapNullValue,

IgnoreErrorGetter;

SerializerFeature(){
    mask = (1 << ordinal());
}

public final int mask;

public final int getMask() {
    return mask;
}

public static boolean isEnabled(int features, SerializerFeature feature) {
   return (features & feature.mask) != 0;
}

Java枚舉類中的 ordinal() 方法會返回枚舉常量的聲明順序，如SerializerFeature.QuoteFieldNames.ordinal()返回 0，以此類推。所以，mask這個(gè)掩碼會按照枚舉常量的順序進(jìn)行移位。

也就是每個(gè)Feature都會有自己的標(biāo)志位，以后就算新增一個(gè)新的Feature，依序聲明即可，原有的變量聲明為了保持兼容性順序盡量不要更改，以防有人直接使用了mask的值進(jìn)行邏輯判斷之類。當(dāng)然，如果沒有暴露接口讓調(diào)用方直接傳入hardcode的mask整型值，新增Feature塞到任何一個(gè)位置，理論上也不影響服務(wù)升級。

QuoteFieldNames.getMask() = 001(二進(jìn)制)
UseSingleQuotes.getMask() = 010(二進(jìn)制)
WriteMapNullValue,getMask() = 100(二進(jìn)制)
.......

我們再看下 isEnabled() 這個(gè)方法，用來判斷所有的Features中是否包含某個(gè)Feature, 與Linux權(quán)限的玩法是不是類似呢？

JSON.toString() 本質(zhì)上其實(shí)就是構(gòu)造了一個(gè)對象 SerializeWriter，而它就會把傳入Feature數(shù)組運(yùn)用簡單的 或 運(yùn)算最終合成了一個(gè) int 類型的 features 值。后續(xù)對于feature的判斷和過濾就和上文的權(quán)限大同小異了。

Redis Bitmap

開始前我先拋出一個(gè)需求：實(shí)時(shí)統(tǒng)計(jì)當(dāng)日在線的用戶數(shù)。你可能會想這個(gè)需求太簡單啦，redis里面存一個(gè)簡單的計(jì)數(shù)器鍵值對，登入就+1，登出就-1。
真就這么簡單么？OK, 再延伸出第二個(gè)需求：實(shí)時(shí)統(tǒng)計(jì)近七日內(nèi)登入過的用戶數(shù)（活躍數(shù)），和近一個(gè)月登入過的用戶數(shù)。若仍舊使用計(jì)數(shù)器的方式，那就需要 online_users_today, online_users_7days, online_users_30days三個(gè)KEY，而且每次用戶的登入登出都需要同時(shí)維護(hù)三個(gè)KEY。See, 計(jì)數(shù)器方案已經(jīng)暴露出無法擴(kuò)展的缺點(diǎn)了。
話不多少，我們直接切入Bitmap這個(gè)Redis里在某些場景算作“神器”的數(shù)據(jù)類型。事實(shí)上Bitmap（或者官方說的Bit arrays）只是String類型的一種特例，即value是一個(gè)類似位的數(shù)組，配合特定的Redis指令達(dá)到高效位運(yùn)算的效果。

摘自Redis官方說明：
https://redis.io/topics/data-types-intro

Bit arrays (or simply bitmaps): it is possible, using special commands, to handle String values like an array of bits: you can set and clear individual bits, count all the bits set to 1, find the first set or unset bit, and so forth.

image.png

$redis = new Redis();
$redis->connect('127.0.0.1');

//設(shè)置今日的在線Key
$redisKey = 'online_users_20170707';

//用戶userId=0登入, 更新Bitmap
$offset = 0;
$redis->setBit($redisKey, $offset, 1);

//用戶userId=15登入, 更新Bitmap
$offset = 15;
$redis->setBit($redisKey, $offset, 1);

//用戶userId=7登出, 更新Bitmap
$offset = 7;
$redis->setBit($redisKey, $offset, 0);

//計(jì)算今日實(shí)時(shí)在線總?cè)藬?shù)
echo $redis->bitCount($redisKey)

//計(jì)算最近7天的總登入人數(shù)
//注意: 該統(tǒng)計(jì)不需要考慮登出的情況
echo $redis->bitOp('AND', 'online_users', ''online_users_20170701', 'online_users_20170702', 'online_users_20170703','online_users_20170704','online_users_20170705','online_users_20170706','online_users_20170707')

echo $redis->bitCount('online_users')

結(jié)合圖示和偽代碼，該需求實(shí)現(xiàn)應(yīng)該是比較容易理解的方案，不再花篇幅說明。使用Bitmap的方案的關(guān)鍵兩個(gè)要素是如何選擇設(shè)計(jì)redis key和value中的offset。
示例中key選擇了天這個(gè)維度，value中的offset采用了用戶的userId（這個(gè)id對應(yīng)的是數(shù)據(jù)庫中的自增長主鍵）。然后我們評估下這個(gè)方案的占用內(nèi)存大小：假設(shè)我們有1億用戶，那么每日活躍用戶數(shù)占用內(nèi)存是 1億/8 = 12.5M字節(jié)，一個(gè)月的占用量也就是12.5M*30=375M，這個(gè)容量理論上是可以接受的。如果1億用戶里面有不少僵尸用戶，即在這12.5M的每日Bitmap數(shù)據(jù)里0的占比要遠(yuǎn)遠(yuǎn)大于1，那你可以key選擇用戶userId這個(gè)維度，value中的offset采用一年中的第幾天作為偏移量，讀者請自行考慮下如何實(shí)現(xiàn)，有何優(yōu)劣。

BloomFilter 布隆過濾器

Hash哈希函數(shù)在計(jì)算機(jī)領(lǐng)域，尤其是數(shù)據(jù)快速查找領(lǐng)域，加密領(lǐng)域用的極廣。其作用是將一個(gè)大的數(shù)據(jù)集映射到一個(gè)小的比如散列表等數(shù)據(jù)集上面。引用一下吳軍博士的《數(shù)學(xué)之美》中所言，哈希表的空間效率還是不夠高。如果用哈希表存儲一億個(gè)垃圾郵件地址，每個(gè)Email地址對應(yīng)8bytes, 而哈希表的存儲效率一般不超過50%，因此一個(gè)Email地址需要占用16bytes. 因此一億個(gè)Email地址占用1.6GB，如果存儲幾十億個(gè)Email地址則需要上百GB的內(nèi)存。
所以要引入本節(jié)的Bloom Filter。如果想判斷一個(gè)元素是不是在一個(gè)集合里，通常想到的是將通過Iterate集合中的元素通過比較來確定?？梢赃x擇List、Map、HashTable等等數(shù)據(jù)結(jié)構(gòu)。但是如果隨著集合中元素的增加，數(shù)據(jù)量級指數(shù)上升，它需要的存儲空間也就越來越大，同時(shí)檢索速度也越來越慢。

image.png

Bloom Filter 是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，可以看做是對 Bitmap 的擴(kuò)展，它只需要哈希表 1/8 到 1/4 的大小就能解決同樣的問題。優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過一般的算法，缺點(diǎn)是有一定的誤識別率和刪除困難。
說白了就是原理很簡單，用位數(shù)組和k個(gè)不同的HASH函數(shù)。將HASH函數(shù)對應(yīng)的值的位數(shù)組置1，查找時(shí)如果發(fā)現(xiàn)所有HASH函數(shù)對應(yīng)位都是1說明存在。
Bloom Filter一般適用于大數(shù)據(jù)量的對精確度要求不是100%的去重或者匹配場景。像上面提到的垃圾郵箱過濾(黑名單匹配)，敏感詞過濾(或者AC自動(dòng)機(jī))，爬蟲系統(tǒng)的URL去重(已爬網(wǎng)址去重)，網(wǎng)站的UV統(tǒng)計(jì)(同一用戶去重)。

有趣的位算法

1. 10個(gè)老鼠1000個(gè)瓶子中找到有毒的
   (鋪墊：3個(gè)老鼠8個(gè)瓶子)
   https://www.zhihu.com/question/19676641

2. leetcode 位運(yùn)算算法
   數(shù)組A中，除了某一個(gè)數(shù)字X之外，其他數(shù)字都出現(xiàn)了三次，而X只出現(xiàn)了一次。請給出最快的方法找到X。（鋪墊：其他數(shù)字出現(xiàn)兩次）
   http://blog.csdn.net/morewindows/article/details/12684497
   http://blog.csdn.net/morewindows/article/details/8214003

3. 常見加解密算法
   很有趣的位運(yùn)算資料分享

《Hacker's Delight》- 各種位運(yùn)算黑科技
http://www.hackersdelight.org/

《你可曾聽過位運(yùn)算的天籟》- "聽見"位運(yùn)算
https://zhuanlan.zhihu.com/p/24912672

本文篇幅有限，不可能窮舉出所有的位運(yùn)算場景，但已經(jīng)是本人目前腦子里最近可以巴拉出來的大部分應(yīng)用場景了。如有您有其它更好的場景說明，可留言給我。