【小知識大道理】被忽視的位運算

2019 年 11 月 5 日
筆記

Bitwise Operation導語眾所周知電腦是基於二進位01進行運算的，理所當然地，位運算相對於各種算術運算更加貼合電腦的二進位語義，運算效率會更快。這樣電腦是舒服了，人類讀起來就太生澀了，所以這是把雙刃劍。好的程式碼本身就要Trade Off計算效率性和程式碼可讀性。我們經常會用移位運算(Bit Shift)比如左移或者右移來分別實現乘法或者除法運算，但是很多人會忽略左移是有可能造成數據越界，必然需要做好程式層面的控制，否則這種BUG太容易被掩蓋。下面的章節我會列舉一些常見的位運算場景，供大家參考。

基本概念

開始前先把Java位運算的基本概念提一下下：

bit operators.png

運算符的優先順序：~ 的優先順序最高，其次是 <<、>> 和 >>>，再次是＆，然後是 ^，優先順序最低的是 |。

關於負數的二進位轉換，採用的補碼規則，有興趣的同學可以研究一下它背後的數學意義。

Linux 許可權控制

image.png

Linux的日常，無處不見上圖中的文件許可權，而這個許可權控制的原理就是使用的二進位位運算。Linux中的許可權有點像三權分立，分別是讀、寫、執行。

access.png

實現原理也很簡單，r w x 三個許可權分別對應三位的二進位標誌位。如下圖，「執行X」許可權使用二進位為001，即：八進位1。「寫入W」許可權使用二進位為010，即：八進位2。「讀取R」許可權使用二進位為100，即：八進位4。

前面提到的三權分立也就是考慮到三者分別在不同的標誌位上，相互完全獨立。由此展開我們的許可權管理ING:

1 添加許可權

增加許可權使用或（|）運算實現。如，為某用戶增加「讀取」、「寫入」兩種許可權。「讀寫」兩種許可權，許可權碼為6（110），本質是由許可權碼2（010）和4（100）進行或（|）運算後實現，即6 = 2 | 4，當然直觀也可以視作基本的算術加 6 = 2 + 4 計算得出。

2 判斷許可權

在需要判斷用戶許可權時，可使用與（&）運算。如，判斷許可權碼為6用戶是否有讀取許可權。許可權碼6（110）和4（100）的與運算結果為4，即：4 = 6 & 4。如，判斷許可權碼為6用戶是否有執行許可權。許可權碼6（110）和1（001）的與運算結果為0，即：0 = 6 & 1。

總結下就是，當與運算結果為所要判斷許可權的本身值時，我們可以認為用戶具有這個許可權。而當運算結果為 0 時，我們可以認為用戶不具有這個許可權。

3 移除許可權

移除用戶的許可權可使用異或（^）運算。如，將許可權碼為7的用戶，移除執行許可權。許可權碼7（111）和1（001）的異或運算結果為6，即：6 = 7 ^ 1，也可以由算術減 6 = 7 – 1計算得出。

Linux "umask"命令指定在建立文件時預設的許可權掩碼，而掩碼就是用來移除許可權的。比如大部分系統運行umask輸出的是「002」或者「0002」, 表示默認去掉了其他用戶的寫許可權。

從上面的介紹可以看出，在基於位運算的許可權管理系統中，每種許可權碼都是唯一的；而且要求每個許可權碼的二進位數形式，都只能有一位值為1。簡單的說，許可權碼都是2的冪數。

基於位運算的許可權管理，優點很明顯：運算速度快、效率高、節省存儲空間、對許可權控制非常靈活。而且擴展性也不錯，隨時可以擴展新的標誌位。除了許可權，有些可以組合的業務類型也可以通過這種獨立位運算的方式來實現。

BitMask 位掩碼

這裡我們延展到另一個概念: 位掩碼BitMask。Linux許可權就是位掩碼的一種特例。我們這裡再看一種典型的位掩碼實現。

搞研發的同學對於fastjson這個阿里巴巴的開源組件應該很熟悉吧？我們經常會用它來做一些請求/應答數據的序列化和反序列化。在序列化的場景，我們可能會用一些特別的features來滿足特定需求，比如：

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

如果需要多種feature組合的話，只要傳入一個feature數組即可。那麼fastjson如何做到對feature的管理有如Linux許可權那般的靈活和可擴展的呢？我們先看下 SerializerFeature 這個枚舉類的實現：

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這個掩碼會按照枚舉常量的順序進行移位。

也就是每個Feature都會有自己的標誌位，以後就算新增一個新的Feature，依序聲明即可，原有的變數聲明為了保持兼容性順序盡量不要更改，以防有人直接使用了mask的值進行邏輯判斷之類。當然，如果沒有暴露介面讓調用方直接傳入hardcode的mask整型值，新增Feature塞到任何一個位置，理論上也不影響服務升級。

QuoteFieldNames.getMask() = 001(二進位) UseSingleQuotes.getMask() = 010(二進位) WriteMapNullValue,getMask() = 100(二進位) …….

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

JSON.toString() 本質上其實就是構造了一個對象 SerializeWriter，而它就會把傳入Feature數組運用簡單的或運算最終合成了一個 int 類型的 features 值。後續對於feature的判斷和過濾就和上文的許可權大同小異了。

Redis Bitmap

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

摘自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'); //設置今日的在線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); //計算今日實時在線總人數 echo $redis->bitCount($redisKey) //計算最近7天的總登入人數 //注意: 該統計不需要考慮登出的情況 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')

結合圖示和偽程式碼，該需求實現應該是比較容易理解的方案，不再花篇幅說明。使用Bitmap的方案的關鍵兩個要素是如何選擇設計redis key和value中的offset。示例中key選擇了天這個維度，value中的offset採用了用戶的userId（這個id對應的是資料庫中的自增長主鍵）。然後我們評估下這個方案的佔用記憶體大小：假設我們有1億用戶，那麼每日活躍用戶數佔用記憶體是 1億/8 = 12.5M位元組，一個月的佔用量也就是12.5M*30=375M，這個容量理論上是可以接受的。如果1億用戶裡面有不少殭屍用戶，即在這12.5M的每日Bitmap數據里0的佔比要遠遠大於1，那你可以key選擇用戶userId這個維度，value中的offset採用一年中的第幾天作為偏移量，讀者請自行考慮下如何實現，有何優劣。

BloomFilter 布隆過濾器

Hash哈希函數在電腦領域，尤其是數據快速查找領域，加密領域用的極廣。其作用是將一個大的數據集映射到一個小的比如散列表等數據集上面。引用一下吳軍博士的《數學之美》中所言，哈希表的空間效率還是不夠高。如果用哈希表存儲一億個垃圾郵件地址，每個Email地址對應8bytes, 而哈希表的存儲效率一般不超過50%，因此一個Email地址需要佔用16bytes. 因此一億個Email地址佔用1.6GB，如果存儲幾十億個Email地址則需要上百GB的記憶體。所以要引入本節的Bloom Filter。如果想判斷一個元素是不是在一個集合里，通常想到的是將通過Iterate集合中的元素通過比較來確定。可以選擇List、Map、HashTable等等數據結構。但是如果隨著集合中元素的增加，數據量級指數上升，它需要的存儲空間也就越來越大，同時檢索速度也越來越慢。

image.png

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

有趣的位演算法

10個老鼠1000個瓶子中找到有毒的 (鋪墊：3個老鼠8個瓶子) https://www.zhihu.com/question/19676641
leetcode 位運算演算法數組A中，除了某一個數字X之外，其他數字都出現了三次，而X只出現了一次。請給出最快的方法找到X。（鋪墊：其他數字出現兩次） http://blog.csdn.net/morewindows/article/details/12684497 http://blog.csdn.net/morewindows/article/details/8214003
常見加解密演算法很有趣的位運算資料分享

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

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

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