頭圖

奇怪的知識——位掩碼

jrainlau

108588108-64e3c400-7392-11eb-8275-ed7a7d4a3ebd.png

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

位運算符

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

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

const A = 0b1010
const B = 0b1111

image.png

1、按位非運算符 ~

對每一位執行非(NOT)操作,也可以理解為取反碼。
image.png

2、按位與運算符 &

對每一位執行與(AND)操作,只要對應位置均為 1 時,結果才為 1,否則為 0。
image.png

3、按位或運算符 |

對每一位執行或(OR)操作,只要對應位置有一個 1 時,結果就為 1。
image.png

4、按位異或運算符 ^

對每一位執行異或(XOR)操作,當對應位置有且只有一個 1 時,結果就為 1,否則為 0。
image.png

5、左移運算符 <<

將數據向左移動一定的位(<32),右邊用 0 填充。
image.png

6、右移運算符 >>

將數據向右移動一定的位(<32),遺棄被丟出的位。
image.png


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

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

權限系統

假設我們有一個權限系統,它通過 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)“的組合詞?!蔽弧爸复M制數據當中的二進制位,而”掩碼“指的是一串用于與目標數據進行按位操作的二進制數字。組合起來,就是”用一串二進制數字(掩碼)去操作另一串二進制數字“的意思。

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

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

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

image.png

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

最后算出來的 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

2、修改用戶的某個權限

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

image.png

只需要把按位與改為按位異或即可,代碼如下:

// 從左往右,依次為 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 瓶水,其編號用二進制表示:

image.png

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

image.png

在 24 小時候,統計老鼠的死亡情況,匯總后可以得到表格和結果:

image.png

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

尾聲

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

閱讀 2.6k

Jrain-前端玩具盆
記錄一路以來的各種折騰。

Hiphop dancer,

12.3k 聲望
3.9k 粉絲
0 條評論

Hiphop dancer,

12.3k 聲望
3.9k 粉絲
宣傳欄
一本到在线是免费观看_亚洲2020天天堂在线观看_国产欧美亚洲精品第一页_最好看的2018中文字幕 <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>