您現在的位置是:首頁 > 動漫首頁動漫
來自小姐姐的靈魂拷問:位運算是什麼?
4的對應數是什麼
「來源: |React ID:react_native」
前兩天上班,突然小葉給我發訊息:哥哥,你看這兩段程式碼是什麼意思啊?
乍一看,感覺這程式碼既熟悉又陌生。好像在哪裡見過,但平時好像又很少用到。
我喝口水,冷靜的想了 3s:咦,這個不就是那個位運算子嗎?之前大學就學過,前一段看react原始碼也有看到過啊!
小葉:哥哥,那你能不能給我講一下這是什麼呢?
我:沒問題,等我整理一下~
什麼是位運算?
位運算簡單來說就是基於整數的二進位制表示進行的運算。它直接處理每一個位元位,是非常底層的運算,好處是速度極快,缺點是不太直觀。
你這會可能會問:二進位制是什麼?
哈哈,其實如果不是科班出身的同學,對二進位制有點陌生也正常了。下面我就簡短的介紹一下二進位制。
二進位制
我們常用的 2、8、16 等數字是十進位制表示,而位運算的基礎是二進位制。即人類採用十進位制,機器採用的是二進位制,要深入瞭解位運算,就需要了解十進位制和二進位制的轉換方法和對應關係。
十進位制轉二進位制
十進位制整數轉換為二進位制整數採用除2取餘,逆序排列法。具體做法是:用 2 整除十進位制整數,可以得到一個商和餘數;再用 2 去除商,又會得到一個商和餘數,如此進行,直到商為小於 1 時為止,然後把先得到的餘數作為二進位制數的低位有效位,後得到的餘數作為二進位制數的高位有效位,依次排列起來。
這裡以十進位制數 156 為例:
二進位制轉十進位制
小數點前或者整數要從右到左用二進位制的每個數去乘以 2 的相應次方並遞增,小數點後則是從左往右乘以二的相應負次方並遞減。
這裡以 1011。01 為例:
介紹完了二進位制和十進位制的相互轉換,下面我們就來看下在js中經常用到的幾個位運算子吧。
JS 中常用的 7 個位運算子
基本的位運算共 7 種,分別為
按位與(AND) &
按位或(OR) |
按位異或(XOR) ^
按位非(NOT) ~
左移(Left shift)<<
有符號右移>>
無符號右移>>>
這裡用一個表格來彙總下以上 7 種運算子的簡介:
按位與(AND) &
&運算子(位與)用於對兩個二進位制運算元逐位進行比較。如果對應的位都為 1,那麼結果就是 1, 如果任意一個位是 0 則結果就是 0。
按位或(OR) |
|運算子(位或)用於對兩個二進位制運算元逐位進行比較。只要兩個對應位中有一個 1 時就為 1,否則為 0。
按位異或(XOR) ^
^運算子(位異或)用於對兩個二進位制運算元逐位進行比較。只有兩個對應位不同時才為 1。
按位非(NOT) ~
~運算子(位非)用於對兩個二進位制運算元逐位進行比較。對位求反,1 變 0, 0 變 1。
這裡稍微有些麻煩,做下解釋:1 反碼二進位制表示: 11111111 11111111 11111111 11111110。由於第一位(符號位)是 1,所以這個數是一個負數。JavaScript 內部採用補碼形式表示負數,即需要將這個數減去 1,再取一次反,然後加上負號,才能得到這個負數對應的 10 進位制值。
1 的反碼減 1 為:11111111 11111111 11111111 11111101。
反碼取反:00000000 00000000 00000000 00000010。再加上符號位-。最終得到 1 的按位非為-2。
二進位制數的負數是取該二進位制數的補碼,然後+1。二進位制數,最高位為 0 表示正數,最高位為 1 表示負數。~按位非操作其實就是取補碼的過程,也就是上述求該值負數的逆過程,所以可以簡單的理解為該值取負值後減 1。
這裡其實是有一個小技巧的:一個數與自身的取反值相加等於-1。
左移(Left shift)<<
<<運算子(左移)表示將指定的二進位制向左移動指定的位數。
有符號右移>>
>>運算子(右移)表示將指定的二進位制向右移動指定的位數。
在MDN上你可以看到:
這句話最後一句提到了“sign-propagating”,中文翻譯過來就是符號傳播的意思,為什麼這樣說呢:我們知道,計算機中以二進位制儲存數字,二進位制中最左邊的第一位,叫符號位,所以這就很明顯了,右移 2 位後,最左邊缺少 2 位數字,那就應該填充數字,那填充什麼呢?符號位是什麼,我就填什麼。由於新的最左側的位總是和以前相同,符號位沒有被改變。所以被稱作“符號傳播”。
無符號右移>>>
很多同學可能會對>>>和>>的區別很好奇,同樣我們來看MDN上對無符號右移>>>的解釋:
同樣,有一個核心詞語:zero-fill right shift。翻譯過來就是零-填充,這個就更明顯了,右移後空位不管你符號位是什麼,我都只填 0。
這裡就可以得到一個結論:對於非負數,有符號右移和無符號右移總是返回相同的結果。
到這裡,JS 中常用的 7 個位運算子的介紹就差不多了。下面讓我們來看下React中對於按位運算子的使用場景。(畢竟這是我第一次在實際的業務場景中看到有人用按位運算子的)
React 當中的使用場景
EffectTag
我們知道每一個 React元素對應一個 fiber物件,一個 fiber 物件通常是表徵 work的一個基本單元:
// packages/react-reconciler/src/ReactFiber。js
// A Fiber is work on a Component that needs to be done or was done。 There can
// be more than one per component。
export type Fiber = {
// 標識 fiber 型別的標籤
tag: WorkTag,
// 指向父節點
return: Fiber | null,
// 指向子節點
child: Fiber | null,
// 指向兄弟節點
sibling: Fiber | null,
// 在開始執行時設定 props 值
pendingProps: any,
// 在結束時設定的 props 值
memoizedProps: any,
// 當前 state
memoizedState: any,
// Effect 型別,詳情檢視以下 effectTag
effectTag: SideEffectTag,
// effect 節點指標,指向下一個 effect
nextEffect: Fiber | null,
// effect list 是單向連結串列,第一個 effect
firstEffect: Fiber | null,
// effect list 是單向連結串列,最後一個 effect
lastEffect: Fiber | null,
// work 的過期時間,可用於標識一個 work 優先順序順序
expirationTime: ExpirationTime,
};
每一個fiber節點都有一個和它相關聯的 effectTag值。我們把不能在 render 階段完成的一些 work 稱之為副作用,React羅列了可能存在的各類副作用,如下所示:
// packages/shared/ReactSideEffectTags。js
export type SideEffectTag = number;
// Don‘t change these two values。 They’re used by React Dev Tools。
exportconst NoEffect = /* */0b000000000000;
exportconst PerformedWork = /* */0b000000000001;
// You can change the rest (and add more)。
exportconst Placement = /* */0b000000000010;
exportconst Update = /* */0b000000000100;
exportconst PlacementAndUpdate = /* */0b000000000110;
exportconst Deletion = /* */0b000000001000;
exportconst ContentReset = /* */0b000000010000;
exportconst Callback = /* */0b000000100000;
exportconst DidCapture = /* */0b000001000000;
exportconst Ref = /* */0b000010000000;
exportconst Snapshot = /* */0b000100000000;
exportconst Passive = /* */0b001000000000;
// Passive & Update & Callback & Ref & Snapshot
exportconst LifecycleEffectMask = /* */0b001110100100;
// Union of all host effects
exportconst HostEffectMask = /* */0b001111111111;
exportconst Incomplete = /* */0b010000000000;
exportconst ShouldCapture = /* */0b100000000000;
可以看到大部分的值都只有一位是 1,其他位都是 0。
0bxxx是原生二進位制字面量的表示方法
這裡列舉一個用到effectTag的場景:
(workInProgress。effectTag & DidCapture) !== NoEffect
這裡其實是對二進位制做與運算:我們拿Update和DidCapture來進行&操作,那麼得到的結果就很明顯了,所有位都是 0。
所以這裡的&操作就是用來判斷在某個變數中是否含有某個屬性的。比如這裡就是判斷workInProgress。effectTag中是否含有DidCapture這個屬性。
相應的位運算場景在 react 原始碼中還有很多很多,這裡就不一一說明了。下面來看下在實際的業務開發中,位運算比較常用的場景。
位運算子在 JS 中的妙用
切換變數 0 或 1
平時我們做一些變數狀態的切換,多半會這樣去寫:
if (flag) {
flag = 0;
} else {
flag = 1;
}
或者簡寫為:
flag = flag ? 0 : 1;
如果用位運算來實現的話:
toggle ^= 1;
有沒有感覺很簡單~
使用&運算子判斷一個數的奇偶
相比與 2 取餘的方式,這種方式也比較簡潔:
// 偶數 & 1 = 0
// 奇數 & 1 = 1
console。log(2 & 1) // 0
console。log(3 & 1) // 1
交換兩個數(不能使用額外的變數)
交換兩個整數的值,最直觀的做法是藉助一個臨時變數:
let a = 5,
b = 6
// 交換a, b的值
let c = a
a = b
b = c
現在要求不能使用額外的變數或內容空間來交換兩個整數的值。這個時候就得藉助位運算,使用異或可以達到這個目的:
let a = 5,
b = 6;
a = a ^ b; // 3
b = a ^ b; // 5
a = a ^ b; // 6
如果你沒看明白,那我們分開來分析一下。
首先:a = a ^ b,即a = 0101 ^ 0110 = 0011 = 3;
第二步:b = a ^ b,即b = 0011 ^ 0110 = 0101 = 5;
最後:a = a ^ b,即a = 0011 ^ 0101 = 0110 = 6。
至此,沒有使用額外的變數完成了兩個整數值的交換。
有關 2 的冪的應用
這塊我在刷leetcode時深有體會下面一起來看下吧:
2 的冪
比較常規的,就是不斷除以 2,判斷最終結果是否為 1,也就是採用遞迴的方法。
/**
* @param {number}n
* @return {boolean}
*/
var isPowerOfTwo = function(n) {
if (n < 1){
returnfalse;
}
if (n == 1) {
returntrue;
}
if (n % 2 > 0) {
returnfalse;
}
return isPowerOfTwo(n / 2);
};
我們考慮一下有沒有更快的解決方式:觀察 2^0、2^1、2^2……2^n,它們的二進位制表示為 1、10、100、1000、10000……
判斷一個數是否是 2 的 n 次冪,也就是判斷二進位制表示中是否只有一位是 1 且在最前面那位的位置。例如 n=00010000,那 n-1=00001111,即n&(n-1)==0
由此就可以判斷啦!
/**
* @param {number}n
* @return {boolean}
*/
var isPowerOfTwo = function(n) {
return n > 0 && (n & (n-1)) === 0
};
位 1 的個數
這裡有一個小技巧, 可以輕鬆求出。就是
n & (n - 1) 可以消除 n 最後的一個 1
。
如果對位運算比較瞭解的話,那麼相信你一定對上述這條skill很熟悉
這樣我們可以不斷進行n = n & (n - 1)直到n === 0 , 說明沒有一個 1 了。透過count去計數即可~
/**
* @param {number}n - a positive integer
* @return {number}
*/
var hammingWeight = function(n) {
let count = 0;
while (n !== 0) {
// n & (n - 1) 可以消除 n 最後的一個1
n = n & (n-1)
count++
}
return count
};
許可權系統設計
後臺管理系統中控制不同使用者的操作許可權是一種很常見的行為。通常我們會採用陣列的方式來表示某種使用者所擁有的操作許可權:
roles: [“admin”, “editor”],
設想如果我們採用位運算來設計這個許可權系統:
管理員(一級許可權):0b100
開發(二級許可權):0b010
運營(三級許可權):0b001
如果 A 操作只能由管理員和開發操作,那麼這個許可權值表示為6 = 0b110,它和管理員許可權&一下:6 & 4 = 0b110 & 0b100 = 4,得到的值不為 0,所以認為有許可權。同理和開發許可權&一下6 & 2 = 2也不為 0,而與運營許可權&一下6 & 1 = 0,所以運營沒有許可權。
這樣的好處在於,我們可以用一個數字,而不是一個數組來表示某個操作的許可權集,同時在進行許可權判斷的時候也很方便。
總結
本篇對位運算做了一個較為系統的說明。其實在實際的開發中,不瞭解位元算的同學也不少。但是在某些場景下能合理的運用位運算也是可以解決很多實際問題的。