[TOC] > 查看《編程基礎》- 二進制基礎 # JavaScript 位運算 JavaScript 將數字存儲為 64 位浮點數，但**所有按位運算都以 32 位整型二進制數執行**。JavaScript 的浮點數遵循IEEE 754 規范。 在 ECMAScript 中，所有整數字面量默認都是有符號整數。 位運算只對整數起作用，如果一個運算子不是整數，會自動轉為整數后再運行。雖然在 JavaScript 內部，數值都是以64位浮點數的形式儲存，但是做位運算的時候，只能使用?31?位（0~2147483647），開發者是不能訪問最高位的。 并且返回值也是一個32位帶符號的整數。 下圖展示的是數 18 的表示法：  1. 位運算只發生在整數上，因此一個非浮點數參與位運算之前會被向下取整，在控制臺輸入下面的代碼： ~~~js 2.1 | 0 // 或運算 >>> 2 ~~~ 2. 為了避免訪問符號位，?javascript?在現實?負數的?二進制時，轉換為?符號加上其絕對值的二進制，如： ~~~ (-123).toString(2); // "-1111011"，即?- 和 123 的二進制 ~~~ JavaScript 中的這種整型是區分正負數的，根據上面的知識推斷 js 中的整數的表示范圍是： ~~~ -Math.pow(2,31) ~ Math.pow(2,31)-1 // [-2^31, +2^31-1] 即 [-2147483648, +2147483647] ~~~ 在控制臺輸出下面的代碼來驗證我們的推斷。 ~~~js -2147483648 | 0 >>> -2147483648 -2147483649 | 0 >>> 2147483647 2147483647 | 0 >>> 2147483647 2147483648 | 0 >>> -2147483648 ~~~ 可以看出，如果一個超過 `2^31-1` 的整數參與位運算的時候就需要注意，其二進制溢出了，截取32位后，如果第 32 位是 1 將被解讀為負數（補碼）。 所以：大于和小于最低和最高的值再去進行轉換時都將改變正負號。 ## 運算符 | 運算符 | 名稱 | 描述 | | --- | --- | --- | | `&` | AND（與） | 兩位都是 1 則設置每位為 1 | | `| `| OR（或） | 兩位中有一個為 1 則設置每位為 1 | | `^` | XOR（異或） | 兩位只有一位為 1 則設置每位為 1 | | `~` | NOT（非） | 反轉所有位 | | `<<` | 左移 | 通過從右填充 0 向左位移，并使最左邊的位移出 | | `>>` | 有符號右位移 | 通過從左填充最左位的拷貝來向右位移，并使最右邊的位移出 | | `>>>` | 無符號右移 | 通過從左填充 0 來向右位移，并使最右邊的位移出 | 由于 JavaScript 使用 32 位有符號整數，`~ 5` 將返回 `-6`。 ```js 00000000000000000000000000000101 // 5 11111111111111111111111111111011 // -5 （負數是正數的二進制補碼加 1） 11111111111111111111111111111010 // ~5 = -6 ``` 1. 在執行位運算之前，JavaScript 將數字轉換為 32 位有符號整數。 2. 執行按位操作后，結果將轉換回 64 位 JavaScript 數。 ## 演示 > 使用 4 位無符號二進制數進行演示 | 操作 | 結果 | 等同于 | 結果 | | --- | --- | --- | --- | | `5 & 1` | 1 | 0101 & 0001 | 0001 | | `5 | 1` | 5 | 0101 | 0001 | 0101 | | `5 ^ 1` | 4 | 0101 ^ 0001 | 0100 | | `~ 5` | 10 | ~0101 | 1010 | | `5 << 1` | 10 | 0101 << 1 | 1010 | | `5 >> 1` | 2 | 0101 >> 1 | 0010 | | `5 >>> 1` | 2 | 0101 >>> 1 | 0010 | 上面的例子使用 4 位無符號二進制數。所以 `~ 5` 返回 10。 下面舉例子來說明每個運算符的作用，開始之前先來介紹幾個會用到的知識點 # 原生二進制字面量 ES6 中引入了原生二進制字面量，二進制數的語法是`0b`開頭，我們將會用到這個新功能，chrome 最新版已經支持。 ~~~ 0b111 // 7 0b001 // 1 (0b1100).toString(10) // 0b1100 === 12 ~~~ js 中二進制和十進制如何轉換呢？ ~~~ // 十進制 => 二進制 let num = 10; console.log(num.toString(2)); // 二進制 => 十進制 let num1 = 1001; console.log(parseInt(num1, 2)); ~~~ ## `Number.prototype.toString` 先來介紹下下面會用到的一個方法——`Number.prototype.toString`方法可以講數字轉化為字符串，有一個可選的參數，用來決定將數字顯示為指定的進制，下面可以查看3的二進制表示 ~~~ 3..toString(2) >> 11 ~~~ ## `& 與` &按位與會將操作數和被操作數的相同為進行與運算，如果都為1則為1，如果有一個為0則為0 ~~~ 101 011 --- 001 ~~~ 101 和 011與完的結果就是 001，下面在js中進行驗證 ~~~ (0b101 & 0b011).toString(2) >>> "1" ~~~ ## `| 或` |按位或是相同的位置上只要有一個為1就是1，兩個都為0則為0 ~~~ 101 001 --- 101 ~~~ 101 和 001或完的結果是101，下面在js中進行驗證 ~~~ (0b101 | 0b001).toString(2) >>> "101" ~~~ ## `~ 非` `~`操作符會將操作數的每一位取反，如果是1則變為0，如果是0則邊為1 ~~~js 101 --- 010 ~~~ 101按位非的結果是010，下面在js中驗證 ~~~js (~0b101).toString(2) >>> "-110" ~~~ 啊呀，怎么結果不對呢！！！上面提到了 js 中的數字是有符號的，我們忘記了最高位的符號了，為了簡化我們將32位簡化為8位，注意最高位是符號位 ``` > 0 0000101 > > 1 1111010 // 求非 > > 1 0000101 // 求反 > > 1 0000110 // 求補 ``` `1 1111010`明顯是一個負數，而且是負數的補碼表示，我們的求它的原碼，也就是再對它求補`1 0000110`就是這個數的真值，也就是結果顯示`-110`，這下總算自圓其說了，O(∩_∩)O 哈哈~ 其實上面的與和或也都是會操作符號位的，不信你試試下面這兩個，可以看到符號位都參與了運算 ~~~js (0b1&-0b1) >>> 1 (0b1|-0b1) >>> -1 ~~~ ## `^ 異或` 參與運算的兩個值，如果兩個相應 bit 位相同，結果為0，否則為1： 按位異或的3個特點： 1） `0^0=0，0^1=1` 0異或任何數＝任何數 2） `1^0=1，1^1=0` 1異或任何數－任何數取反 3） 任何數 異或 自己 ＝ 把自己置 0 ~~~js 101 001 --- 100 ~~~ 101 和 001異或的結果是 100，js中驗證 ~~~js (0b101^0b001).toString(2) >>> "100" ~~~ ### 常見用途 1. 判斷兩個整數a，b是否相等，則可通過下列語句實現： ``` (a ^ b) === 0 ``` 2. 使某些特定的位翻轉 例如：對數10100001的第2位和第3位翻轉，則可以將該數與00000110進行按位異或運算。 ``` 10100001 ^ 00000110 = 10100111 ``` 3. 實現兩個值的交換，而不必使用臨時變量。 例如交換兩個整數 a=10100001，b=00000110 的值，可通過下列語句實現： ``` a = a ^ b； 　　// a=10100111 b = b ^ a； 　　// b=10100001 a = a ^ b； 　　// a=00000110 ``` 4. 記錄多個信息 利用位的異或運算使用一個數字記錄多個信息： 有幾個狀態值分別是?1、2、4、8、16?..... | 二進制表示 | 十進制值 | | --- | --- | | 00000000000000000000000000000001 | 1 | | 00000000000000000000000000000010 | 2 | | 00000000000000000000000000000100 | 4 | | 00000000000000000000000000001000 | 8 | | 00000000000000000000000000010000 | 16 | | 00000000000000000000000000100000 | 32 | | 00000000000000000000000001000000 | 64 | 這些值的規律是，他們的二進制只有一位是?1?，其余都是?0，?因此知道它們任意幾個的按位異或運算的結果，就知道是哪幾個數的組合，這樣可以用一個數字記錄多個信息。 ```js 1^2^4?=?7??//?"00000111" ``` 因此，如果我們知道結果是?7?，就知道它們是由?1?、2、4?組合而成。 5. 被用在一些加密算法中 ## `<< 左移` 左移的規則將操作數向左移動指定的位數，右側用 0 補充，其效果相當于 ×2，其實計算機就是用移位操作來計算乘法的 ~~~js 010 --- 0100 ~~~ 010左移一位就會變為100，下面在js中驗證 ~~~ (0b010<<1).toString(2) >>> "100" ~~~ ## `>> 有符號右移` 該操作符會將第一個操作數向右移動指定的位數。向右被移出的位被丟棄，拷貝最左側的位以填充左側。由于新的最左側的位總是和以前相同，符號位沒有被改變。所以被稱作“符號傳播”。 > 對任一數值 x 進行右移n, 相當于十進制里的除以10的倍數，在這里是指除以數之后取整。 > ~~~js > x / 2^n > ~~~ ~~~js (0b111>>1).toString(2) >>> "11" (-0b111>>1).toString(2) >>> "-100" ~~~ 負數的結果好像不太對勁，我們來看看是怎么回事 ``` > -111 // 真值 > 1 0000111 // 原碼 > 1 1111001 // 補碼 > 1 1111100 // 算數右移 > 1 0000100 // 移位后的原碼 > -100 // 移位后的真值 ``` ## `>>> 無符號右移` 該操作符會將第一個操作數向右移動指定的位數。向右被移出的位被丟棄，左側用0 填充。因為符號位變成了 0，所以結果總是非負的。對于整數和 `>>` 沒有區別。（譯注：即便右移 0 個比特，結果也是非負的。） ~~~ (0b111>>>1).toString(2) >>> "11" ~~~ 對于負數則就不同了,右移后會變為正數 ~~~ (-0b111>>>1).toString(2) >>> "1111111111111111111111111111100" ~~~ ## 要注意的地方 如果運算元不是可用的整數，將取?0?作為運算元： ```js ~NaN; // 將執行 ~0 ,結果為 -1 ~'x'; // -1 'hello'|0; // 0 ({})|0 ; //0 ~Infinity; //-1 同 ~0 ``` 位移運算不能移動超過31位，如果試圖移動超過31位，將 位數?對32取模后再移位 ```js 123 >> 32 //實際是 123>>0 (32%32 = 0) 123 >> 33 //實際是 123>>1 ``` # 關于開頭的問題 關于二進制數就說這么多吧，再來說說開頭的問題，開頭的問題其實可以分解為下面的問題因為search會返回-1 和找到位置的索引，也就成了下面的問題 ~~~ !~-1 >>> ture !~0 >>> false !~1 >>> false ~~~ 非運算對于數字的結果相當于改變符號，并對其值的絕對值-1 ~~~ ~-1 >>> 0 ~0 >>> -1 ~1 >>> -2 ~~~ 其實可以看出!~x的邏輯就是判斷x是否為-1，my god這邏輯真是逆天了，我還是勸大家直接寫成 x === -1多好啊> > [聊聊JavaScript中的二進制數](https://yanhaijing.com/javascript/2016/07/20/binary-in-js/) # 參考 [w3school -JavaScript 位運算符](https://www.w3school.com.cn/js/js_bitwise.asp) [Javascript 中的二進制運算](https://www.cnblogs.com/ecalf/archive/2012/11/26/2789870.html)