Bitwise Operation導(dǎo)語
眾所周知計算機(jī)是基于二進(jìn)制01進(jìn)行運(yùn)算的吆鹤，理所當(dāng)然地蝇闭，位運(yùn)算相對于各種算術(shù)運(yùn)算更加貼合計算機(jī)的二進(jìn)制語義蕴侣，運(yùn)算效率會更快泊交。這樣計算機(jī)是舒服了，人類讀起來就太生澀了宏浩，所以這是把雙刃劍知残。好的代碼本身就要Trade Off計算效率性和代碼可讀性。
我們經(jīng)常會用移位運(yùn)算(Bit Shift)比如左移或者右移來分別實(shí)現(xiàn)乘法或者除法運(yùn)算比庄，但是很多人會忽略左移是有可能造成數(shù)據(jù)越界橡庞，必然需要做好程序?qū)用娴目刂疲駝t這種BUG太容易被掩蓋印蔗。下面的章節(jié)我會列舉一些常見的位運(yùn)算場景扒最，供大家參考。
基本概念
開始前先把Java位運(yùn)算的基本概念提一下下：
運(yùn)算符的優(yōu)先級：~ 的優(yōu)先級最高华嘹，其次是 <<吧趣、>> 和 >>>，再次是＆耙厚，然后是 ^强挫，優(yōu)先級最低的是 |。
關(guān)于負(fù)數(shù)的二進(jìn)制轉(zhuǎn)換薛躬，采用的 補(bǔ)碼 規(guī)則俯渤，有興趣的同學(xué)可以研究一下它背后的數(shù)學(xué)意義。
Linux 權(quán)限控制
Linux的日常型宝，無處不見上圖中的文件權(quán)限八匠，而這個權(quán)限控制的原理就是使用的二進(jìn)制位運(yùn)算。Linux中的權(quán)限有點(diǎn)像三權(quán)分立趴酣，分別是讀梨树、寫、執(zhí)行岖寞。
實(shí)現(xiàn)原理也很簡單抡四，r w x 三個權(quán)限分別對應(yīng)三位的二進(jìn)制標(biāo)志位。如下圖，“執(zhí)行X”權(quán)限使用二進(jìn)制為001指巡，即：八進(jìn)制1淑履。“寫入W”權(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 計算得出些举。
2 判斷權(quán)限
在需要判斷用戶權(quán)限時，可使用 與（&） 運(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)限的本身值時星立，我們可以認(rèn)為用戶具有這個權(quán)限。而當(dāng)運(yùn)算結(jié)果為 0 時葬凳，我們可以認(rèn)為用戶不具有這個權(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計算得出琳袄。
Linux "umask"命令指定在建立文件時預(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)限碼都是唯一的碎紊；而且要求每個權(quán)限碼的二進(jìn)制數(shù)形式，都只能有一位值為1樊诺。簡單的說仗考，權(quán)限碼都是2的冪數(shù)。
基于位運(yùn)算的權(quán)限管理词爬，優(yōu)點(diǎn)很明顯：運(yùn)算速度快秃嗜、效率高、節(jié)省存儲空間顿膨、對權(quán)限控制非常靈活锅锨。而且擴(kuò)展性也不錯，隨時可以擴(kuò)展新的標(biāo)志位恋沃。除了權(quán)限必搞，有些可以組合的業(yè)務(wù)類型也可以通過這種獨(dú)立位運(yùn)算的方式來實(shí)現(xiàn)。
BitMask 位掩碼
這里我們延展到另一個概念: 位掩碼BitMask囊咏。Linux權(quán)限就是位掩碼的一種特例顾画。我們這里再看一種典型的位掩碼實(shí)現(xiàn)。
搞研發(fā)的同學(xué)對于fastjson這個阿里巴巴的開源組件應(yīng)該很熟悉吧匆笤？ 我們經(jīng)常會用它來做一些請求/應(yīng)答數(shù)據(jù)的序列化和反序列化研侣。在序列化的場景，我們可能會用一些特別的features來滿足特定需求炮捧，比如：
// 按照類的屬性名排序輸出
JSON.toJSONString(obj, SerializerFeature.SortField)
// 輸出標(biāo)準(zhǔn)格式的日期格式
JSON.toJSONString(obj, SerializerFeature.WriteDateUseDateFormat)
如果需要多種feature組合的話庶诡，只要傳入一個feature數(shù)組即可。那么fastjson如何做到對feature的管理有如Linux權(quán)限那般的靈活和可擴(kuò)展的呢咆课？我們先看下 SerializerFeature 這個枚舉類的實(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這個掩碼會按照枚舉常量的順序進(jìn)行移位。
也就是每個Feature都會有自己的標(biāo)志位殊校，以后就算新增一個新的Feature晴玖，依序聲明即可，原有的變量聲明為了保持兼容性順序盡量不要更改，以防有人直接使用了mask的值進(jìn)行邏輯判斷之類呕屎。當(dāng)然让簿，如果沒有暴露接口讓調(diào)用方直接傳入hardcode的mask整型值，新增Feature塞到任何一個位置秀睛，理論上也不影響服務(wù)升級尔当。
QuoteFieldNames.getMask() = 001(二進(jìn)制)
UseSingleQuotes.getMask() = 010(二進(jìn)制)
WriteMapNullValue,getMask() = 100(二進(jìn)制)
.......
我們再看下 isEnabled() 這個方法，用來判斷所有的Features中是否包含某個Feature, 與Linux權(quán)限的玩法是不是類似呢蹂安？
JSON.toString() 本質(zhì)上其實(shí)就是構(gòu)造了一個對象 SerializeWriter椭迎，而它就會把傳入Feature數(shù)組運(yùn)用簡單的 或 運(yùn)算最終合成了一個 int 類型的 features 值。后續(xù)對于feature的判斷和過濾就和上文的權(quán)限大同小異了田盈。
Redis Bitmap
開始前我先拋出一個需求：實(shí)時統(tǒng)計當(dāng)日在線的用戶數(shù)畜号。你可能會想這個需求太簡單啦，redis里面存一個簡單的計數(shù)器鍵值對缠黍，登入就+1弄兜，登出就-1药蜻。
真就這么簡單么瓷式？OK, 再延伸出第二個需求：實(shí)時統(tǒng)計近七日內(nèi)登入過的用戶數(shù)（活躍數(shù)），和近一個月登入過的用戶數(shù)语泽。若仍舊使用計數(shù)器的方式贸典，那就需要 online_users_today, online_users_7days, online_users_30days三個KEY，而且每次用戶的登入登出都需要同時維護(hù)三個KEY踱卵。See, 計數(shù)器方案已經(jīng)暴露出無法擴(kuò)展的缺點(diǎn)了廊驼。
話不多少，我們直接切入Bitmap這個Redis里在某些場景算作“神器”的數(shù)據(jù)類型惋砂。事實(shí)上Bitmap（或者官方說的Bit arrays）只是String類型的一種特例妒挎，即value是一個類似位的數(shù)組，配合特定的Redis指令達(dá)到高效位運(yùn)算的效果西饵。
摘自Redis官方說明：
https://redis.io/topics/data-types-introBit 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.
$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);//計算今日實(shí)時在線總?cè)藬?shù)
echo $redis->bitCount($redisKey)//計算最近7天的總登入人數(shù)
//注意: 該統(tǒng)計不需要考慮登出的情況
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)鍵兩個要素是如何選擇設(shè)計redis key和value中的offset期虾。
示例中key選擇了天這個維度，value中的offset采用了用戶的userId（這個id對應(yīng)的是數(shù)據(jù)庫中的自增長主鍵）驯嘱。然后我們評估下這個方案的占用內(nèi)存大邢獍：假設(shè)我們有1億用戶，那么每日活躍用戶數(shù)占用內(nèi)存是 1億/8 = 12.5M字節(jié)鞠评，一個月的占用量也就是12.5M*30=375M茂蚓，這個容量理論上是可以接受的。如果1億用戶里面有不少僵尸用戶，即在這12.5M的每日Bitmap數(shù)據(jù)里0的占比要遠(yuǎn)遠(yuǎn)大于1煌贴，那你可以key選擇用戶userId這個維度御板，value中的offset采用一年中的第幾天作為偏移量，讀者請自行考慮下如何實(shí)現(xiàn)牛郑，有何優(yōu)劣怠肋。
BloomFilter 布隆過濾器
Hash哈希函數(shù)在計算機(jī)領(lǐng)域，尤其是數(shù)據(jù)快速查找領(lǐng)域淹朋，加密領(lǐng)域用的極廣笙各。其作用是將一個大的數(shù)據(jù)集映射到一個小的比如散列表等數(shù)據(jù)集上面。引用一下吳軍博士的《數(shù)學(xué)之美》中所言础芍，哈希表的空間效率還是不夠高杈抢。如果用哈希表存儲一億個垃圾郵件地址，每個Email地址對應(yīng)8bytes, 而哈希表的存儲效率一般不超過50%仑性，因此一個Email地址需要占用16bytes. 因此一億個Email地址占用1.6GB惶楼，如果存儲幾十億個Email地址則需要上百GB的內(nèi)存。
所以要引入本節(jié)的Bloom Filter诊杆。如果想判斷一個元素是不是在一個集合里歼捐，通常想到的是將通過Iterate集合中的元素通過比較來確定〕啃冢可以選擇List豹储、Map、HashTable等等數(shù)據(jù)結(jié)構(gòu)淘这。但是如果隨著集合中元素的增加剥扣，數(shù)據(jù)量級指數(shù)上升，它需要的存儲空間也就越來越大铝穷，同時檢索速度也越來越慢钠怯。
Bloom Filter 是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，可以看做是對 Bitmap 的擴(kuò)展曙聂，它只需要哈希表 1/8 到 1/4 的大小就能解決同樣的問題晦炊。優(yōu)點(diǎn)是空間效率和查詢時間都遠(yuǎn)遠(yuǎn)超過一般的算法，缺點(diǎn)是有一定的誤識別率和刪除困難筹陵。
說白了就是原理很簡單刽锤，用位數(shù)組和k個不同的HASH函數(shù)。將HASH函數(shù)對應(yīng)的值的位數(shù)組置1朦佩，查找時如果發(fā)現(xiàn)所有HASH函數(shù)對應(yīng)位都是1說明存在并思。
Bloom Filter一般適用于大數(shù)據(jù)量的對精確度要求不是100%的去重或者匹配場景。像上面提到的垃圾郵箱過濾(黑名單匹配)语稠，敏感詞過濾(或者AC自動機(jī))宋彼，爬蟲系統(tǒng)的URL去重(已爬網(wǎng)址去重)弄砍，網(wǎng)站的UV統(tǒng)計(同一用戶去重)。
有趣的位算法
10個老鼠1000個瓶子中找到有毒的
(鋪墊：3個老鼠8個瓶子)
https://www.zhihu.com/question/19676641leetcode 位運(yùn)算算法
數(shù)組A中输涕，除了某一個數(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常見加解密算法
很有趣的位運(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)用場景了碴卧。如有您有其它更好的場景說明，可留言給我乃正。
