奇怪的知識——位掩碼

來源：https://tinyurl.com/ygc5ay7y

在春節假期無聊刷手機的時候，偶然間看到了一篇關於 “位掩碼” 的文章，本身就是奇怪知識的它可以用來解決一些奇怪的問題，實在是非常有趣。

位運算符

在瞭解 “位掩碼” 之前，首先要學會位運算符。

我們知道，在計算機中數據其實都是以二進制的形式所儲存的，而位運算符則可以對二進制數據進行操作。舉個簡單的例子，給定兩個二進制數據（其中 0b 是二進制數據的前綴）：

const A = 0b1010
const B = 0b1111

1、按位非運算符 ~

對每一位執行**非（NOT）**操作，也可以理解爲取反碼。

2、按位與運算符 &

對每一位執行**與（AND）**操作，只要對應位置均爲 1 時，結果才爲 1，否則爲 0。

對每一位執行**或（OR）**操作，只要對應位置有一個 1 時，結果就爲 1。

對每一位執行**異或（XOR）**操作，當對應位置有且只有一個 1 時，結果就爲 1，否則爲 0。

5、左移運算符 <<

將數據向左移動一定的位（<32），右邊用 0 填充。

將數據向右移動一定的位（<32），遺棄被丟出的位。

在學習完了位運算符以後，肯定有人會說，道理都明白了，那麼這些位運算符有什麼用呢？應該在什麼場合使用呢？平時的業務開發中也沒見過，是不是其實學了也沒什麼用？

對於這個問題，答案確實是 “是的，這個知識其實沒什麼用“。但是呢，秉承着探索的精神，我們也許可以用這個” 沒什麼用的知識“去解決一些已知的問題。當然，在後續的例子中，你可能會覺得我在小題大做。不過沒關係，學習本來就是枯燥的事情，能夠找到些有趣的方式去學習枯燥的知識，也是很快樂的。

權限系統

假設我們有一個權限系統，它通過 JSON 的方式記錄了某個用戶的權限開通情況（姑且假設權限集是 CURD)：

const permission = {
  create: false,
  update: false,
  read: true,
  delete: false,
}

如果我們把 false 寫成 0，true 寫成 1，那麼這個 permisson 對象可以簡寫爲 0b0010。

const permission = {
  create: false,
  update: false,
  read: true,
  delete: false,
}

// 從左往右，依次爲 create, update, read, delete 所對應的值
const permissionBinary = 0b0010

對於 JSON 對象的權限集，如果我們要查看或者修改該用戶的某些權限，只需要通過形如 permission.craete 的普通對象操作即可。那麼如果對於二進制形式的權限集，我們又應該如何進行查看或者修改的操作呢？接下來我們就開始使用奇怪的知識——位掩碼來進行了。

位掩碼

首先進行名詞解釋，什麼是” 位掩碼 “。

位掩碼（BitMask），是”位（Bit）“和”掩碼（Mask）“的組合詞。”位 “指代着二進制數據當中的二進制位，而” 掩碼 “指的是一串用於與目標數據進行按位操作的二進制數字。組合起來，就是” 用一串二進制數字（掩碼）去操作另一串二進制數字“的意思。

明白了位掩碼的作用以後，我們就可以通過它來對權限集二進制數進行操作了。

1、查詢用戶是否擁有某個權限

已知用戶權限集二進制數爲 permissionBinary = 0b0010。如果我想知道該用戶是否存在 update 這個權限，可以先給定一個位掩碼 mask = 0b1。

由於 update 位於右數第三項，所以只需要把位掩碼向左移動兩位，剩餘位置補 0。最後和權限集二進制數進行按位與運算即可得到結果。

最後算出來的 result 爲 0b0000，使用 Boolean() 函數處理之即可得到 false 的結果，也就是說該用戶的 update 權限爲 false。

// 從左往右，依次爲 create, update, read, delete 所對應的值
const permissionBinary = 0b0010

// 由於 update 位於右數第三位，因此只需要讓掩碼向左移動2位即可
const mask = 0b1 << 2

const result = permissionBinary & mask

Boolean(result) // false

當我們明白瞭如何用位掩碼來查詢權限後，要修改對應的權限也就手到擒來了，無非就是換一種位運算。假設還是 update 權限，如果我想把它修改成 true，我們可以這麼幹：

只需要把按位與改爲按位異或即可，代碼如下：

// 從左往右，依次爲 create, update, read, delete 所對應的值
const permissionBinary = 0b0010

// 由於 update 位於右數第三位，因此只需要讓掩碼向左移動2位即可
const mask = 0b1 << 2

const result = permissionBinary ^ mask

parseInt(result).toString(2) // 0b0110

經過上面的內容，相信你已經基本掌握了位掩碼的知識，同時你肯定還有很多問號，比如說這麼複雜又不好閱讀的代碼，真的有意義嗎？

髒數據記錄

前文例子中的權限系統僅有區區 4 個數據的處理，位掩碼技術顯得複雜又小題大做。那麼有沒有什麼場景是真的適合使用位掩碼的呢？髒數據記錄就是其中一個。

假設我們存在着一份原始數據，其值如下：

let A = 'a'
let B = 'b'
let C = 'c'
let D = 'd'

給定一個二進制數，從左往右分別對應着 A/B/C/D 的狀態：

let O = 0b0000 // 十進制 0

則數據一旦發生了修改，都可以用對應的比特位來表示

// 當且僅當 A 發生了修改
O = 0b1000 // 十進制 8

// 當且僅當 B 發生了修改
O = 0b0100 // 十進制 4

// 當且僅當 C 發生了修改
O = 0b0010 // 十進制 2

// 當且僅當 D 發生了修改
O = 0b0001 // 十進制 1

同理，當多個數據發生了修改時，則可以同時表示

// 當 A 和 B 發生了修改
O = 0b1100 // 十進制 12

// 當 A/B/C 都發生了修改
O = 0b1110 // 十進制 14

通過這個思路，應用排列組合的思想，可以很快知道只需要僅僅 4 個比特位，就可以表達 16 種數據變化的情況。由於二進制和十進制可以相互轉化，因此只需要區區 16 個十進制數，就可以完整地表達 A/B/C/D 這四個數據的變化情況，也就是髒數據追蹤。舉個例子，給定一個髒數據記錄 14，二進制轉換爲 0b1110，因此表示 A/B/C 的數據被修改了。

Svelte 這個框架，就是通過這個思路來實現響應式的：

if ( A 數據變了 ) {
  更新A對應的DOM節點
}
if ( B 數據變了 ) {
  更新B對應的DOM節點
}

/** 轉化成僞代碼 **/

if ( dirty & 8 ) { // 8 === 0b1000
  更新A對應的DOM節點
}
if ( dirty & 4 ) { // 4 === 0b0100
  更新B對應的DOM節點
}

更多具體的介紹可以查看《新興前端框架 Svelte 從入門到原理》。

老鼠喝毒藥

除了用來做髒數據記錄以外，位掩碼也能夠用來處理經典的” 老鼠喝毒藥 “的問題。

有 1000 瓶水，其中有一瓶有毒，小白鼠只要嘗一點帶毒的水 24 小時後就會死亡，問至少要多少隻小白鼠才能在 24 小時內鑑別出哪瓶水有毒？

我們簡化一下問題，假設只有 8 瓶水，其編號用二進制表示：

接着按照圖示的方式對水瓶的水進行混合，得到樣品 A/B/C/D，取 4 只老鼠編號爲 a/b/c/d 分別喝下對應的水，得到如下的表格：

在 24 小時候，統計老鼠的死亡情況，彙總後可以得到表格和結果：

答案呼之欲出，由於 8 瓶水可以兌出 4 份樣品，因此只需要 4 只老鼠即可在 24 小時後確定到底哪一瓶水是有毒的。回到題目，如果是 1000 瓶水，只需要知道第 1000 號的二進制數 0b1111101000即可。該二進制數一共有 10 個比特位，意味着 1000 瓶水可以兌出 10 份樣品，也就是說只需要 10 只老鼠，就可以完成測試任務。

尾聲

關於位掩碼技術的探索就到這裏。相信在認真讀完這篇文章以後，大家心裏已經建立起對位掩碼技術的概念。這是一種非常特別的問題解決思路，也許在未來的某一天你真的會用上它。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/gq0SOnevJAv-gUIVOkQJgQ

猜你喜歡