强大的JS位运算

站长

2022年12月16日 19:40 · 阅读数 15

从常见的加减乘除，到平方开根......现代的高级语言都提供了完备的数学运算能力，简单的直接使用运算符或者调用库函数即可使用，无需关心内部细节。如果我们深入一下，就会发现计算机内部的各种数学运算其实是在进行二进制的位运算。

为什么是二进制？

计算机中之所以使用二进制，而不是日常生活中的十进制。这和现代的计算机的硬件有关，在逻辑电路中，最简单直接的两种状态就是开和关，断开通常使用 0 表示，而连通则使用 1 表示。大量的电路通过与或非等电路门组合就能完成异常复杂的逻辑处理。这样简单的电路即使受到一些干扰也不易出错。

如果要想实现十进制，就需要 10 种电路状态，情况会变得复杂，容错性会大大的降低。

日常的十进制计数法是以 10 作为基数，十进制的百位，千位都是以 10n10^n10n 的形式为基底，然后乘以一个乘数，乘数是 0…90\ldots90…9，个数位的幂从 0 开始。比如：

（4231)10=4∗103+2∗102+3∗101+1∗100（4231)_{10} = 4*10^3+2*10^2+3*10^1+1*10^0（4231)10=4∗103+2∗102+3∗101+1∗100

类比到二进制，就是以 2 作为基数，数位的形式就是 2n2^n2n，乘数是 0，10，10，1。比如：

(25)10=16+8+1=1∗24+1∗23+0∗22+0∗21+1∗20=(11001)2(25)_{10} = 16+8+1 = 1*2^4+1*2^3+0*2^2+0*2^1+1*2^0 =(11001)_2\\(25)10=16+8+1=1∗24+1∗23+0∗22+0∗21+1∗20=(11001)2

原码，反码，补码

下文内容出于简化目的，都假设计算机使用 8 bit 来存储数据

数学里的数值有正负之分。为了做区分，计算机使用了二进制的最高位作为符号位，1 表示负数，0 表示正数，这种表示法被称为原码，即：最高位表示符号位，其他位存放的是该数的绝对值。，那么上面例子中的 25 的完整二进制是 (00011001)2(0001 1001)_2(00011001)2，而 −25-25−25 则是 (10011001)2(1001 1001)_2(10011001)2 。原码表示很简单，也最易读。

但原码在异号数之间的加法往往得不到正确的结果，以 5+(−2)5+(-2)5+(−2) 为例：

强大的JS位运算

计算机中只有加法电路，没有减法电路，所以减去一个数，会被处理为加上其相反数

为了应对这种情况，反码和补码被设计了出来，补码运用的是取模的思想，并利用数据溢出，让符号位也参与到运算中，而后计算机中的运算都基于补码进行。

补充一下自然数取模的概念：如果 a 和 d 是两个自然数，d 非零，可以证明存在两个唯一的整数 q 和 r，满足 a = qd + r 且 0 ≤ r < d。其中，q 被称为商，r 被称为余数。

正数取模很常见，我们重点来看看正负数之间取模，即 (−7)mod 3(-7) \mod 3(−7)mod3：

−7=(−3)∗3+2-7 = (-3)*3+2−7=(−3)∗3+2

所以商是 −3-3−3，余数是 222。可以简单记忆为：

(−7)mod 3=3−(7mod 3)(-7) \mod 3 = 3 - (7\mod 3)(−7)mod3=3−(7mod3)

用时钟来举例，如果现在是 2 点，那么怎么让时钟指向 8 点呢？

指针 向前拨 6 个小时，即 2+6=82+6=82+6=8
指针 向后拨 6 个小时，即 2−6=82-6=82−6=8

所以 +6+6+6 和 −6-6−6 最终的效果是等效的，只是从逻辑上来说，−6-6−6 相当于是进入了上个周期的 8 点（而“上个周期”这种区间不能被存储下来，所以被舍弃掉了，类似于计算机的溢出）。由于时钟只能表示 0…120\ldots120…12 之间的时间，所以它的模是 12，而 −6-6−6 和 666 对 12 取模的余数都是 6，所有 −6-6−6 和 666 互为同余数。

强大的JS位运算

在时钟的场景中，可以看出：减去一个数，等于加上其同余数。而只要这个数在区间范围内，它的同余数等于模减去该数。

计算机的场景也类似，同样以 8 bit 存储二进制举例，8 bit 的容量为 28=(100000000)22^8=(100000000)_228=(100000000)2，那么上面的 5+(−2)5+(-2)5+(−2) 变成了：

强大的JS位运算

最终的结果有 9 位，溢出了。去掉最高位以后，剩下 (00000011)2=(3)10(00000011)_2=(3)_{10}(00000011)2=(3)10 。刚好是正确的结果。

将其推广的一般情况：

强大的JS位运算

而其中 2n−12^n-12n−1 的结果为 111…111n111\ldots111_n111…111n 的二进制数，所有 2n−1−j2^n-1-j2n−1−j 的计算结果相当于 −j-j−j 来说，除了符号位不变外，其他部分按位取反。我们将 2n−1−j2^n-1-j2n−1−j 称之为 −j-j−j 的反码，上面公式变成：

强大的JS位运算

反码，补码主要用来处理负数的表示，正数不需要这样的变换，所以正数的原码，反码，补码三码合一。

用表格总结一下三种码的计算方式：

类型	计算方式	示例
原码	最高位表示符号位，其他位存放的是该数的绝对值	5 的原码：(00000101)2(00000101)_2(00000101)2 -5 的原码：(10000101)2(10000101)_2(10000101)2
反码	正数反码与原码相同，负数在原码的基础上，除了符号位不变外，其他部分按位取反	5 的反码：(00000101)2(00000101)_2(00000101)2 -5 的反码：(11111010)2(11111010)_2(11111010)2
补码	正数反码与原码相同，负数在反码的基础上，+1	5 的补码：(00000101)2(00000101)_2(00000101)2 -5 的补码：(11111011)2(11111011)_2(11111011)2

为什么 c++ 中 int 的范围是 −231…(231−1)-2^{31}\ldots(2^{31}-1)−231…(231−1)?

在原码和反码中，0 都有两种表示方法，即：

	原码	反码
+0	(00000000)2(00000000)_2(00000000)2	(00000000)2(00000000)_2(00000000)2
-0	(10000000)2(10000000)_2(10000000)2	(11111111)2(11111111)_2(11111111)2

但在补码中，0 只有一种方式，即 +0+0+0，而 −0-0−0 被人为的指定为 −2n−1-2^{n-1}−2n−1。这是因为补码是基于取模的思想和溢出的特性设计的，而取模需要数据具有连续性和唯一性。

比如，对时钟取模，1mod 12=11\mod 12 = 11mod12=1，2mod 12=22 \mod 12 =22mod12=2...11mod 12=1111 \mod 12 =1111mod12=11，12mod 12=012 \mod 12 =012mod12=0 。随着时间的递增，超过了上限，上溢出的结果是 0；如果反过来，时间低于了下限，下溢出又会变成最大值，即 (−1)mod 12=11(-1) \mod 12 =11(−1)mod12=11，如此循环反复。

所以我们需要补码也具有这样的特性，二进制能表示的最小数再减去 1，溢出后结果是最大值；最大数再加上 1，溢出后结果是最小值。而最大值加 1 有以下的结果：

强大的JS位运算

计算结果符号位为 1，表示是负数的补码，对应原码 100000001000000010000000，刚好是 −0-0−0 。但这显然破坏了数据连续性和唯一性，所以在补码中，人为指定 −0-0−0 为 −2n−1-2^{n-1}−2n−1，这样最大值加 1 刚好就变成了最小值。同理最小值减一也刚好变成最大值。

在计算机数学小书 1-原码，反码和补码一文中，对于连续性和唯一性有更详细的解释，下面贴图同样来自该文章

强大的JS位运算

好了，现在让我们回到问题：为什么 c++ 中 int 的范围是 −231…(231−1)-2^{31}\ldots(2^{31}-1)−231…(231−1)?

c++ int 占用 4 个字节，即 32 位，除去最高位的符号位，还有 31 位，那么正数的所有情况是 2312^{31}231 种，正数是从 0 开始，所以正数的范围是 0…231−10\ldots2^{31}-10…231−1，而负数这边同样是 2312^{31}231 种，但是由于人为指定 −0-0−0 被人为的指定为 −231-2^{31}−231，所以负数的范围是 (−1)…(−231)(-1)\ldots(-2^{31})(−1)…(−231) ，合在一起的范围就是 −231…(231−1)-2^{31}\ldots(2^{31}-1)−231…(231−1)。

Why 位运算？

为什么要使用位运算呢？答案是快，上面说的计算机的底层运算就是位运算，所以直接用位运算的执行效率非常快，以下面代码为例：

console.time("常规判断");
for (let i = 0; i < 100000; i++) {
  i % 2 === 0;
}
console.timeEnd("常规判断"); // 10.842ms

console.time("位运算判断");
for (let i = 0; i < 100000; i++) {
  (i & 1) === 0;
}
console.timeEnd("位运算判断"); // 0.968ms

可以看到，就是如此简单的 判断一个数是否是偶数 的场景，两者之间的性能就大致差了 10 倍，足见位运算的强大。

JS 位运算

JS 不区分浮点数和整数，所有数值都以 IEEE-754 64 位格式来存储，但位操作符并不直接操作 64 位的值，而是先将 64 位的值转换为 32 位的整数，再执行操作，最后再将结果转换为 64 位。因此过大过小的数，浮点数会出现精度损失，需要特别注意。

与（And &）

与运算即：操作的两个数，同一位必须全都是 1，那么最终结果才是 1，否则就为 0：

强大的JS位运算

现在再回去看上面判断一个数奇偶性的例子应该就没有问题了：如果一个数是奇数，那么最后二进制的最后一位必然是 1，否则是 0。所有当前数和 1 求与的结果如果为 0，则说明该数是偶数，否则为奇数。

或（OR |）

或运算即：操作的两个数，同一位只要有一个位是 1，那么最终结果就是 1：

强大的JS位运算

异或（XOR ^）

异或运算和或运算有所不同，可以理解为是 更严格的或，即操作的两个数，同一位必须不相同，最终结果才是 1，否则是 0：

强大的JS位运算

异或功能十分的强大，有以下常用的特性（证明过程画个图就明白了，不再展开）：

归零律，即一个数和自身的异或结果总是等于 0，a⊕a=0a \oplus a = 0a⊕a=0
恒等律，即一个数与 0 的异或结果总是等于其本身，a⊕0=a a \oplus 0 = aa⊕0=a
交换律，即a⊕b=b⊕aa \oplus b = b \oplus aa⊕b=b⊕a
结合律，即a⊕(b⊕c)=(a⊕b)⊕ca \oplus (b \oplus c)=(a \oplus b) \oplus ca⊕(b⊕c)=(a⊕b)⊕c
自反，结合归零律和恒等律，可得出a⊕b⊕a=ba \oplus b \oplus a = b a⊕b⊕a=b
对于任意整数 iii ，有 4i⊕(4i+1)⊕(4i+2)⊕(4i+3)=04i\oplus(4i+1)\oplus(4i+2)\oplus(4i+3)= 04i⊕(4i+1)⊕(4i+2)⊕(4i+3)=0

通过异或运算，甚至可以做到，在不使用第三个临时变量的情况下互换两个数：

let a = 10;
let b = 20;

a = a ^ b;
b = b ^ a;
a = a ^ b;

console.log(a, b); // a = 20, b = 10

非（NOT ~）

非运算会反转操作数的每一位，1 变成 0，0 变成 1：

强大的JS位运算

在数组的 findIndex 运算中，常常通过结果是否等于 −1-1−1 判断是否存在符合期望的子项，这也能通过非运算来简写：

const a = [1, 2, 3, 4];
const idx = a.findIndex((i) => i === 2);
// 通常的写法
// if(idx!== 1){
//
// }
// 非运算
if (~idx) {
}

原因很简单，一个数非运算的结果和原本的数刚好每位相反，两者相加的二进制结果就是 32 位 1，刚好是 −1-1−1 的补码，可以简单记忆：a+¬a=−1 a+ \neg a=-1a+¬a=−1。所以当 idx 为 −1-1−1 是，其非运算结果刚好为 0。

向左移位（<<）

向左移动 n 位，表示末尾添加 n 个 0，且最高的 n 位会溢出被舍弃掉：

强大的JS位运算

由于是 JS 位运算是使用 32 位长度。所以，左右移动的实际位数是 入参位数对 32 取模的余数，因此 a<<0=a<<32a<<0=a<<32a<<0=a<<32。

在有些文章中会总结说，左移 n 位相当于扩大了 2n2^n2n 倍，在某些情况下确实如此，比如 4<<2=164<<2=164<<2=16 。但一旦高位溢出部分包含了 1 ，这个结论就不成立了，比如 (231−1)<<1=−2(2^{31}-1)<<1=-2(231−1)<<1=−2。所以抓住本质即可，不必硬记结论。

无符号向右移位（>>>）

和左移不同的是，右边最高位是符号位，所以向右移动就分为了两种情况，无符号右移（也叫逻辑右移）则是不管符号位是啥，都无条件的在开头补 0，且最低的 n 位会溢出舍弃掉：

强大的JS位运算

有符号向右移位（>>）

有符号向右移位（也叫算术右移），则要考虑符号位，如果符号位是 1 则补 1，否则补 0：

强大的JS位运算

无符号右移，和有符号左移、左移的最大区别在于：无符号右移将 64 位的值转换为 32 位的整数时，进行的是 ToUint32 转换，可以类比成 c++ 的 unsigned int 等，32 位的最高位不再是符号位，所以无符号右移的结果总是这个正数，即使是右移 0 位。

比如 −231>>>0=231-2^{31}>>>0=2^{31}−231>>>0=231，−231-2^{31}−231 符号位是 1，其余部分都是 0，当时右移 0 位后，1 不再是符号位，和其他位没有区别，就会变了 2312^{31}231。

有符号左移、左移在转换时则进行的是 ToInt32。

stackoverflow 上 What is the JavaScript >>> operator and how do you use it? 也有更详细的解释，也可以查看 ECMA ApplyStringOrNumericBinaryOperator 规范查看详细的转换流程

花式取整

位运算只作用于 number，所以在操作其他类型时，都会进行 ToNumber，ToInt32 等隐式类型转换，浮点数的小数部分会被直接舍弃掉，然后 NaN、Infinity 等特殊的数值类型在位运算中会被当做 0 来处理。因此你可以使用任意的位运算进行取整操作。比如：

234.234∣0=234234.234 \mid 0 = 234234.234∣0=234
234.234⊕0=234234.234 \oplus 0 = 234234.234⊕0=234
234.234>>>0=234234.234 >>> 0 = 234234.234>>>0=234
234.234<<0=234234.234 << 0 = 234234.234<<0=234

需要保证操作的数在 −231…(231−1)-2^{31}\ldots(2^{31}-1)−231…(231−1) 范围内，否则会出现精度损失。

框架中的位运算实践

React18

React 也使用了在很多场景中使用了位运算进行性能和代码上的优化，比如在组件调用 setState 等方法更新状态后，内部会根据优先级执行更新操作，而这些更新优先级使用了二进制的掩码做处理。

源码位置：ReactFiberLane.js

强大的JS位运算

Lanes 使用了 31 位长度的二进制码表示优先级（上文已经说过，最高位 32 位是符号位），且 1 的位置越低（即数值越小）表示优先级越高。

在更新时，会有一个 wipLane 记录当前更新的优先级。判断 wipLane 中具体有哪些更新等级也非常简单，直接使用 与运算 即可：

强大的JS位运算

React 的更新策略是优先处理高优的更新，所有需要从 wipLane 中挑出最高等级的更新，会用到如下的方法：

export function getHighestPriorityLane(lanes: Lanes): Lane {
  return lanes & -lanes;
}

比如说当前的 lanes 是 (…0101)2(\ldots 0101)_2(…0101)2，既有 SyncLane 也有 InputContinuousLane，那么 getHighestPriorityLane 需要获取其中的 SyncLane 部分，即 (…0001)2(\ldots 0001)_2(…0001)2，运算过程如下：