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

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

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