奇怪的知識(shí)——位掩碼
在春節(jié)假期無(wú)聊刷手機(jī)的時(shí)候，偶然間看到了一篇關(guān)于“位掩碼”的文章，本身就是奇怪知識(shí)的它可以用來(lái)解決一些奇怪的問(wèn)題，實(shí)在是非常有趣。
位運(yùn)算符
在了解“位掩碼”之前，首先要學(xué)會(huì)位運(yùn)算符。
我們知道，在計(jì)算機(jī)中數(shù)據(jù)其實(shí)都是以二進(jìn)制的形式所儲(chǔ)存的，而位運(yùn)算符則可以對(duì)二進(jìn)制數(shù)據(jù)進(jìn)行操作。舉個(gè)簡(jiǎn)單的例子，給定兩個(gè)二進(jìn)制數(shù)據(jù)（其中?0b 是二進(jìn)制數(shù)據(jù)的前綴）：
const?A?=?0b1010
const?B?=?0b1111
1、按位非運(yùn)算符?~
對(duì)每一位執(zhí)行非（NOT）操作，也可以理解為取反碼。
2、按位與運(yùn)算符?&
對(duì)每一位執(zhí)行與（AND）操作，只要對(duì)應(yīng)位置均為 1 時(shí)，結(jié)果才為 1，否則為 0。
3、按位或運(yùn)算符?|
對(duì)每一位執(zhí)行或（OR）操作，只要對(duì)應(yīng)位置有一個(gè) 1 時(shí)，結(jié)果就為 1。
4、按位異或運(yùn)算符?^
對(duì)每一位執(zhí)行異或（XOR）操作，當(dāng)對(duì)應(yīng)位置有且只有一個(gè) 1 時(shí)，結(jié)果就為 1，否則為 0。
5、左移運(yùn)算符?<<
將數(shù)據(jù)向左移動(dòng)一定的位（<32），右邊用 0 填充。
6、右移運(yùn)算符?>>
將數(shù)據(jù)向右移動(dòng)一定的位（<32），遺棄被丟出的位。
在學(xué)習(xí)完了位運(yùn)算符以后，肯定有人會(huì)說(shuō)，道理都明白了，那么這些位運(yùn)算符有什么用呢？應(yīng)該在什么場(chǎng)合使用呢？平時(shí)的業(yè)務(wù)開(kāi)發(fā)中也沒(méi)見(jiàn)過(guò)，是不是其實(shí)學(xué)了也沒(méi)什么用？
對(duì)于這個(gè)問(wèn)題，答案確實(shí)是“是的，這個(gè)知識(shí)其實(shí)沒(méi)什么用“。但是呢，秉承著探索的精神，我們也許可以用這個(gè)”沒(méi)什么用的知識(shí)“去解決一些已知的問(wèn)題。當(dāng)然，在后續(xù)的例子中，你可能會(huì)覺(jué)得我在小題大做。不過(guò)沒(méi)關(guān)系，學(xué)習(xí)本來(lái)就是枯燥的事情，能夠找到些有趣的方式去學(xué)習(xí)枯燥的知識(shí)，也是很快樂(lè)的。
權(quán)限系統(tǒng)
假設(shè)我們有一個(gè)權(quán)限系統(tǒng)，它通過(guò) JSON 的方式記錄了某個(gè)用戶的權(quán)限開(kāi)通情況（姑且假設(shè)權(quán)限集是 CURD)：
const?permission?=?{
??create:?false,
??update:?false,
??read:?true,
??delete:?false,
}
如果我們把 false 寫成 0，true 寫成 1，那么這個(gè) permisson 對(duì)象可以簡(jiǎn)寫為?0b0010。
const?permission?=?{
??create:?false,
??update:?false,
??read:?true,
??delete:?false,
}
//?從左往右，依次為?create,?update,?read,?delete?所對(duì)應(yīng)的值
const?permissionBinary?=?0b0010
對(duì)于 JSON 對(duì)象的權(quán)限集，如果我們要查看或者修改該用戶的某些權(quán)限，只需要通過(guò)形如 permission.craete 的普通對(duì)象操作即可。那么如果對(duì)于二進(jìn)制形式的權(quán)限集，我們又應(yīng)該如何進(jìn)行查看或者修改的操作呢？接下來(lái)我們就開(kāi)始使用奇怪的知識(shí)——位掩碼來(lái)進(jìn)行了。
位掩碼
首先進(jìn)行名詞解釋，什么是”位掩碼“。
位掩碼（BitMask），是”位（Bit）“和”掩碼（Mask）“的組合詞。”位“指代著二進(jìn)制數(shù)據(jù)當(dāng)中的二進(jìn)制位，而”掩碼“指的是一串用于與目標(biāo)數(shù)據(jù)進(jìn)行按位操作的二進(jìn)制數(shù)字。組合起來(lái)，就是”用一串二進(jìn)制數(shù)字（掩碼）去操作另一串二進(jìn)制數(shù)字“的意思。
明白了位掩碼的作用以后，我們就可以通過(guò)它來(lái)對(duì)權(quán)限集二進(jìn)制數(shù)進(jìn)行操作了。
1、查詢用戶是否擁有某個(gè)權(quán)限
已知用戶權(quán)限集二進(jìn)制數(shù)為 permissionBinary = 0b0010。如果我想知道該用戶是否存在 update 這個(gè)權(quán)限，可以先給定一個(gè)位掩碼 mask = 0b1。
由于 update 位于右數(shù)第三項(xiàng)，所以只需要把位掩碼向左移動(dòng)兩位，剩余位置補(bǔ)0。最后和權(quán)限集二進(jìn)制數(shù)進(jìn)行按位與運(yùn)算即可得到結(jié)果。
最后算出來(lái)的 result 為?0b0000，使用 Boolean()?函數(shù)處理之即可得到 false 的結(jié)果，也就是說(shuō)該用戶的 update 權(quán)限為 false。
//?從左往右，依次為?create,?update,?read,?delete?所對(duì)應(yīng)的值
const?permissionBinary?=?0b0010
//?由于?update?位于右數(shù)第三位，因此只需要讓掩碼向左移動(dòng)2位即可
const?mask?=?0b1?<
const?result?=?permissionBinary?&?mask
Boolean(result)?//?false
2、修改用戶的某個(gè)權(quán)限
當(dāng)我們明白了如何用位掩碼來(lái)查詢權(quán)限后，要修改對(duì)應(yīng)的權(quán)限也就手到擒來(lái)了，無(wú)非就是換一種位運(yùn)算。假設(shè)還是 update 權(quán)限，如果我想把它修改成 true，我們可以這么干：
只需要把按位與改為按位異或即可，代碼如下：
//?從左往右，依次為?create,?update,?read,?delete?所對(duì)應(yīng)的值
const?permissionBinary?=?0b0010
//?由于?update?位于右數(shù)第三位，因此只需要讓掩碼向左移動(dòng)2位即可
const?mask?=?0b1?<
const?result?=?permissionBinary?^?mask
parseInt(result).toString(2)?//?0b0110
經(jīng)過(guò)上面的內(nèi)容，相信你已經(jīng)基本掌握了位掩碼的知識(shí)，同時(shí)你肯定還有很多問(wèn)號(hào)，比如說(shuō)這么復(fù)雜又不好閱讀的代碼，真的有意義嗎？
臟數(shù)據(jù)記錄
前文例子中的權(quán)限系統(tǒng)僅有區(qū)區(qū)4個(gè)數(shù)據(jù)的處理，位掩碼技術(shù)顯得復(fù)雜又小題大做。那么有沒(méi)有什么場(chǎng)景是真的適合使用位掩碼的呢？臟數(shù)據(jù)記錄就是其中一個(gè)。
假設(shè)我們存在著一份原始數(shù)據(jù)，其值如下：
let?A?=?'a'
let?B?=?'b'
let?C?=?'c'
let?D?=?'d'
給定一個(gè)二進(jìn)制數(shù)，從左往右分別對(duì)應(yīng)著 A/B/C/D 的狀態(tài)：
let?O?=?0b0000?//?十進(jìn)制?0
則數(shù)據(jù)一旦發(fā)生了修改，都可以用對(duì)應(yīng)的比特位來(lái)表示
//?當(dāng)且僅當(dāng)?A?發(fā)生了修改
O?=?0b1000?//?十進(jìn)制?8
//?當(dāng)且僅當(dāng)?B?發(fā)生了修改
O?=?0b0100?//?十進(jìn)制?4
//?當(dāng)且僅當(dāng)?C?發(fā)生了修改
O?=?0b0010?//?十進(jìn)制?2
//?當(dāng)且僅當(dāng)?D?發(fā)生了修改
O?=?0b0001?//?十進(jìn)制?1
同理，當(dāng)多個(gè)數(shù)據(jù)發(fā)生了修改時(shí)，則可以同時(shí)表示
//?當(dāng)?A?和?B?發(fā)生了修改
O?=?0b1100?//?十進(jìn)制?12
//?當(dāng)?A/B/C?都發(fā)生了修改
O?=?0b1110?//?十進(jìn)制?14
通過(guò)這個(gè)思路，應(yīng)用排列組合的思想，可以很快知道只需要僅僅 4 個(gè)比特位，就可以表達(dá) 16 種數(shù)據(jù)變化的情況。由于二進(jìn)制和十進(jìn)制可以相互轉(zhuǎn)化，因此只需要區(qū)區(qū) 16 個(gè)十進(jìn)制數(shù)，就可以完整地表達(dá) A/B/C/D 這四個(gè)數(shù)據(jù)的變化情況，也就是臟數(shù)據(jù)追蹤。舉個(gè)例子，給定一個(gè)臟數(shù)據(jù)記錄 14，二進(jìn)制轉(zhuǎn)換為?0b1110，因此表示 A/B/C 的數(shù)據(jù)被修改了。
Svelte 這個(gè)框架，就是通過(guò)這個(gè)思路來(lái)實(shí)現(xiàn)響應(yīng)式的：
if?(?A?數(shù)據(jù)變了?)?{
??更新A對(duì)應(yīng)的DOM節(jié)點(diǎn)
}
if?(?B?數(shù)據(jù)變了?)?{
??更新B對(duì)應(yīng)的DOM節(jié)點(diǎn)
}
/**?轉(zhuǎn)化成偽代碼?**/
if?(?dirty?&?8?)?{?//?8?===?0b1000
??更新A對(duì)應(yīng)的DOM節(jié)點(diǎn)
}
if?(?dirty?&?4?)?{?//?4?===?0b0100
??更新B對(duì)應(yīng)的DOM節(jié)點(diǎn)
}
更多具體的介紹可以查看《新興前端框架 Svelte 從入門到原理》。
https://zhuanlan.zhihu.com/p/350507037
老鼠喝毒藥
除了用來(lái)做臟數(shù)據(jù)記錄以外，位掩碼也能夠用來(lái)處理經(jīng)典的”老鼠喝毒藥“的問(wèn)題。
有 1000 瓶水，其中有一瓶有毒，小白鼠只要嘗一點(diǎn)帶毒的水24小時(shí)后就會(huì)死亡，問(wèn)至少要多少只小白鼠才能在24小時(shí)內(nèi)鑒別出哪瓶水有毒？
我們簡(jiǎn)化一下問(wèn)題，假設(shè)只有 8 瓶水，其編號(hào)用二進(jìn)制表示：
接著按照?qǐng)D示的方式對(duì)水瓶的水進(jìn)行混合，得到樣品 A/B/C/D，取4只老鼠編號(hào)為 a/b/c/d 分別喝下對(duì)應(yīng)的水，得到如下的表格：
在 24 小時(shí)候，統(tǒng)計(jì)老鼠的死亡情況，匯總后可以得到表格和結(jié)果：
答案呼之欲出，由于 8 瓶水可以兌出 4 份樣品，因此只需要 4 只老鼠即可在 24 小時(shí)后確定到底哪一瓶水是有毒的?；氐筋}目，如果是 1000 瓶水，只需要知道第 1000 號(hào)的二進(jìn)制數(shù)?0b1111101000即可。該二進(jìn)制數(shù)一共有 10 個(gè)比特位，意味著 1000 瓶水可以兌出 10 份樣品，也就是說(shuō)只需要 10 只老鼠，就可以完成測(cè)試任務(wù)。
尾聲
關(guān)于位掩碼技術(shù)的探索就到這里。相信在認(rèn)真讀完這篇文章以后，大家心里已經(jīng)建立起對(duì)位掩碼技術(shù)的概念。這是一種非常特別的問(wèn)題解決思路，也許在未來(lái)的某一天你真的會(huì)用上它。
