一文读懂 Vue 及 React 源码中的位运算

站长

2024年06月08日 20:52 · 阅读数 57

关于位运算的认识

二进制的位运算是非常底层的运算，直接操作二进制位，比起使用对象或数组，省略了中间的转换操作，运算速度快，而且也节省了运行内存，因为各个状态只需要数字（number）就能存储，比起使用对象或数组，空间复杂度由 O(n) 降到 O(1)。因此，使用位运算的优点是性能高，而缺点则是不够直观，代码可读性较差。

因此，在实际的开发中，是否使用位运算需要具体的权衡。当然，对于 Vue 、React 这类底层的框架来说，牺牲一些可读性来优化性能，个人认为是值得的。

二进制的位运算总共有 7 种运算符，分别为

按位与（&）
按位或（|）
按位异或（^）
按位取反（~）
左移（<<）
右移（>>）
无符号右移（>>>）

按位与（`&`）

按位与（&）的运算规则为：两个二进制位都为 1 时结果才为 1 。

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

按位或（`|`）

按位或（|）的运算规则为：两个二进制位只要有 1 个为 1 结果就为 1

0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

按位异或（`^`）

按位异或（^）的运算规则为：两个二进制位相同时为 0 ，不同时为 1

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 0
1 ^ 1 = 0

按位取反（`~`）

按位取反（~）的运算规则为：二进制位中 0 变 1 ，1 变 0

~00 = 11
~01 = 10
~10 = 01
~11 = 00

左移（`<<`）

左移（<<）的运算规则为：二进制数所有位都左移指定次数，高位丢弃，低位补 0

0001 << 1 = 0010

右移（`>>`）

右移（>>）的运算规则为：二进制所有位都右移指定次数，低位丢弃，高位补符号位（正数的符号位为 0，负数的符号位为 1）

0100 >> 1 = 0010
1100 >> 1 = 1110

无符号右移（`>>>`）

无符号右移（>>>）的运算规则为：二进制所有位都右移指定次数，低位丢弃，高位一律补 0 。因此，无符号右移（>>>）的运算结果一定是非负数。

0100 >>> 1 = 0010
1100 >>> 1 = 0110

借助位运算设计权限系统

我们可以利用二进制数某一位来标识系统的权限，该位的数为 1 则表示有权限，0 则表示没有权限，就像是开关一样。

比如，我们可以假设系统的用户有 增删改查 这4个权限。因为只有 4 个权限，则可以用 4 位的二进制数来表示用户所有的权限情况。

这 4 位二进制数中：

如果第 1 位数为 1 ，则表示拥有增加数据的权限；
如果第 2 位数为 1 ，则表示拥有删除数据的权限；
如果第 3 位数为 1 ，则表示拥有修改数据的权限；
如果第 4 位数为 1，则表示拥有查询数据的权限。

接下来定义一个枚举来标识这四个权限。定义好标识权限的权限码后就可以利用位运算来实现权限的添加、删除和校验了。

const enum PermFlags {
  CREATE = 1,
  DELETE = 1 << 1,
  UPDATE = 1 << 2,
  SELECT = 1 << 3
}

增加权限

要增加权限只需做一次与运算就可以了。

let permCode = 0

// 增加增加数据的权限
permCode |= PermFlags.CREATE
// 增加查询数据的权限
permCode |= PermFlags.SELECT

// 输出 1001，根据之前的定义，二进制数中，
// 第 1 位为 1 表示拥有增加数据的权限；
// 第 4 位为 1 表示拥有查询数据的权限；
console.log(permCode.toString(2))

删除权限

删除权限，只需将要删除的权限码取反，再执行与操作

let permCode = 0

permCode |= PermFlags.CREATE

permCode |= PermFlags.SELECT

// 删除增加数据的权限
permCode &= ~PermFlags.CREATE

// 输出 1000，根据之前的定义二进制数中，
// 第 4 位为 1 表示拥有查询数据的权限，
// 同时增加数据的权限被删除
console.log(permCode.toString(2))

校验权限

要校验权限只需执行与操作即可

let permCode = 0

permCode |= PermFlags.CREATE

permCode |= PermFlags.SELECT

if (permCode & PermFlags.CREATE) {
  // 1 -> true，正常输出
  console.log('拥有创建数据的权限')
}

优点与局限性

使用位运算设计权限系统的优点是性能极好，局限性则是一方面代码可读性较差，同时由于 JavaScript 的位运算操作符会将操作数当做 32 位的二进制数，同时最高位又是符号位，所以最多可以表示 31 种权限，可使用的权限数有限。

所以使用位运算设计权限系统的技术方案适合那种权限数较少，性能要求高的场景。

Vue 源码中的位运算

Vue 源码中大量运用了位运算。Vue 在虚拟 DOM （VNode）中定义了 shapeFlag 属性，Vue 借助 shapeFlag 属性和位运算，从而更加高效的区分虚拟 DOM 的类型，从而在更新的时候根据不同的虚拟 DOM 类型做不同的逻辑处理。

同时，在虚拟 DOM （VNode）中也定义了 patchFlag 属性，用于区分不同场景的 diff ，使 Vue 可以根据不同的 patchFlag 更有针对性的 diff ，从而提高 diff 的性能。

shapeFlag 属性与 patchFlag 属性的区别是他们的使用场景不同，一个用于更加精细的区分虚拟 DOM 的类型，另一个用于更加精细的区分不同的 diff 场景。当然，两者都有一个共同的目的，就是提升框架的性能。

// packages/shared/src/shapeFlags.ts

export const enum ShapeFlags {
  ELEMENT = 1,
  FUNCTIONAL_COMPONENT = 1 << 1,
  STATEFUL_COMPONENT = 1 << 2,
  TEXT_CHILDREN = 1 << 3,
  ARRAY_CHILDREN = 1 << 4,
  SLOTS_CHILDREN = 1 << 5,
  TELEPORT = 1 << 6,
  SUSPENSE = 1 << 7,
  COMPONENT_SHOULD_KEEP_ALIVE = 1 << 8,
  COMPONENT_KEPT_ALIVE = 1 << 9,
  COMPONENT = ShapeFlags.STATEFUL_COMPONENT | ShapeFlags.FUNCTIONAL_COMPONENT
}

Tips: 本文中的 Vue.js 源码均摘自 3.2.45 版本

ELEMENT ，普通的 HTML 元素
FUNCTIONAL_COMPONENT ，函数式组件
STATEFUL_COMPONENT，有状态组件
TEXT_CHILDREN，子节点是纯文本
ARRAY_CHILDREN，子节点是数组
SLOTS_CHILDREN，子节点是插槽
TELEPORT，该虚拟 DOM 使用传送门（teleport）的功能
SUSPENSE，该组件使用了 Suspense 特性
COMPONENT_SHOULD_KEEP_ALIVE，组件应该保持 KeepAlive 的状态，将组件虚拟 DOM 标记为 COMPONENT_SHOULD_KEEP_ALIVE 可以防止组件被卸载
COMPONENT_KEPT_ALIVE，组件需要被保持 KeepAlive 的状态，组件虚拟 DOM 标记为 COMPONENT_KEPT_ALIVE 可以防止组件走真正的挂载逻辑
COMPONENT，表示虚拟 DOM 是组件，可能是有状态组件，也可能是函数式组件

通过先取反（~），再与（&）操作删除 KeepAlive 相关的标识：

// packages/runtime-core/src/components/KeepAlive.ts

function resetShapeFlag(vnode: VNode) {
  vnode.shapeFlag &= ~ShapeFlags.COMPONENT_SHOULD_KEEP_ALIVE
  vnode.shapeFlag &= ~ShapeFlags.COMPONENT_KEPT_ALIVE
}

通过与（&）操作判断是否为有状态组件

// packages/runtime-core/src/component.ts

export function isStatefulComponent(instance: ComponentInternalInstance) {
  return instance.vnode.shapeFlag & ShapeFlags.STATEFUL_COMPONENT
}

在 patch 函数中，依据不同的 shapeFlag 执行不同的逻辑

// packages/runtime-core/src/renderer.ts

const patch: PatchFn = (
  n1,
  n2,
  container,
  anchor = null,
  parentComponent = null,
  parentSuspense = null,
  isSVG = false,
  slotScopeIds = null,
  optimized = __DEV__ && isHmrUpdating ? false : !!n2.dynamicChildren
) => {
  if (n1 === n2) {
    return
  }
  const { type, ref, shapeFlag } = n2
  switch (type) {
    case Text:
      // ...
      break
    case Comment:
      // ...
      break
    case Static:
      // ...
      break
    case Fragment:
      // ...
      break
    default:
      if (shapeFlag & ShapeFlags.ELEMENT) {
        // 执行 ELEMENT 相关逻辑
      } else if (shapeFlag & ShapeFlags.COMPONENT) {
        // 执行 COMPONENT 相关逻辑
      } else if (shapeFlag & ShapeFlags.TELEPORT) {
        // 执行 TELEPORT 相关逻辑
      } else if (__FEATURE_SUSPENSE__ && shapeFlag & ShapeFlags.SUSPENSE) {
        // 执行 SUSPENSE 相关逻辑
      } else if (__DEV__) {
        warn('Invalid VNode type:', type, `(${typeof type})`)
      }
  }
}

虚拟 DOM 中的 patchFlag 是由编译器生成的，当 diff 算法在处理动态子节点块时，会进入优化模式。我们知道虚拟 DOM 是运行编译器生成的渲染函数生成的，在优化模式下， diff 算法只会处理由 patchFlag 明确标记过的更新，从而不需要进行完整的 diff 流程，优化了 diff 算法的性能。

patchFlag 可以使用组合运算操作符（|）组合起来，并且可以使用与运算操作符（&）进行校验，例如：

const flag = TEXT | CLASS
if (flag & TEXT) {
  // ...
}

Vue 内部定义了枚举来统一管理 patchFlag

// packages/shared/src/patchFlags.ts

export const enum PatchFlags {
  TEXT = 1,
  CLASS = 1 << 1,
  STYLE = 1 << 2,
  PROPS = 1 << 3,
  FULL_PROPS = 1 << 4,
  HYDRATE_EVENTS = 1 << 5,
  STABLE_FRAGMENT = 1 << 6,
  KEYED_FRAGMENT = 1 << 7,
  UNKEYED_FRAGMENT = 1 << 8,
  NEED_PATCH = 1 << 9,
  DYNAMIC_SLOTS = 1 << 10,
  DEV_ROOT_FRAGMENT = 1 << 11,
  HOISTED = -1,
  BAIL = -2
}

TEXT，表示元素（虚拟 DOM）具有动态文本内容
CLASS，表示元素（虚拟 DOM）绑定了动态 class
STYLE，表示元素（虚拟 DOM）具有动态样式
PROPS，表示元素（虚拟 DOM）具有动态 prop / attr （没有显示在 props 中声明的属性，会被当做 attribute 来处理，当然 class 和 style 除外，class 和 style 是特殊的属性，会做另外的处理）
FULL_PROPS，表示元素具有动态 key 属性，当 key 改变时，需要进行完整的 diff 比较
HYDRATE_EVENTS，表示带有事件监听器的元素
STABLE_FRAGMENT，子节点顺序不会改变的 fragment
KEYED_FRAGMENT，带有 key 属或部分子节点有 key 的 fragment
UNKEYED_FRAGMENT，子节点没有 key 的 fragment
NEED_PATCH，非 props 比较，比如 ref 或指令
DYNAMIC_SLOTS，表示具有动态插槽的组件。带有此标识的组件总是会被强制更新
DEV_ROOT_FRAGMENT，用户在 Vue 模板的根级别放置了注释而创建的片段，这个标识只在开发时使用，因为在生产环境，注释会被删除，所以不会有这种只为注释存在的片段。
HOISTED 和 BAIL 是负数，都是特殊标识，他们不使用位运算的方式来校验，而是直接使用全等（===）运算符来校验。
- HOISTED 表示静态的虚拟 DOM ，可以跳过更新，因为静态内容是不变的
- BAIL 表示退出 diff 算法的优化模式，例如遇到非编译器生成的插槽（即手动编写渲染函数）等场景。

在 patchElement 函数中，根据不同的 patchFlag 执行不同的代码逻辑：

// packages/runtime-core/src/renderer.ts

const patchElement = (
  n1: VNode,
  n2: VNode,
  parentComponent: ComponentInternalInstance | null,
  parentSuspense: SuspenseBoundary | null,
  isSVG: boolean,
  slotScopeIds: string[] | null,
  optimized: boolean
) => {
  let { patchFlag, dynamicChildren, dirs } = n2
  patchFlag |= n1.patchFlag & PatchFlags.FULL_PROPS
  // ...
  // patchFlag 大于 0 会进入 diff 算法的优化模式
  if (patchFlag > 0) {
    if (patchFlag & PatchFlags.FULL_PROPS) {
      // 元素（虚拟 DOM）的 props 含有动态的 key 属性，需要进行完整的 diff
    } else {
      if (patchFlag & PatchFlags.CLASS) {
        // 元素（虚拟 DOM）绑定了动态 class
      }

      if (patchFlag & PatchFlags.STYLE) {
        // 元素（虚拟 DOM）绑定了动态样式
      }

      if (patchFlag & PatchFlags.PROPS) {
        // 元素（虚拟 DOM）绑定了动态的 prop/atrr
      }
    }
  } else if (!optimized && dynamicChildren == null) {
    // 非优化模式，进行完整的 diff
  }
}

React 源码中的位运算

说到 React 源码中的位运算，就不得不说 React 源码中的 lanes 模型，也叫车道模型。

lanes 模型与 React 的优先级机制相关，通过不同 lane 的位运算，确定更新任务的优先级，确保在性能有限的环境中仍能保持用户界面的流畅。

lanes 模型使用 31 位的二进制数表示。为啥是 31 位？因为在 JavaScript 中的二进制数中，第 32 位是符号位。可以想象 lanes 模型中 31 位的二进制数中的每 1 位都代表 1 个车道，在赛车的时候，内圈的车道的总路程会比较短，lanes 模型也借鉴了这个概念，占用了越低的“赛道”的值，优先级越高，即一个 lane 的值越小对应的优先级越高。

// packages/react-reconciler/src/ReactFiberLane.js

export const NoLanes: Lanes = /*                        */ 0b0000000000000000000000000000000;
export const NoLane: Lane = /*                          */ 0b0000000000000000000000000000000;

export const SyncLane: Lane = /*                        */ 0b0000000000000000000000000000001;
export const SyncBatchedLane: Lane = /*                 */ 0b0000000000000000000000000000010;

export const InputDiscreteHydrationLane: Lane = /*      */ 0b0000000000000000000000000000100;
const InputDiscreteLanes: Lanes = /*                    */ 0b0000000000000000000000000011000;

const InputContinuousHydrationLane: Lane = /*           */ 0b0000000000000000000000000100000;
const InputContinuousLanes: Lanes = /*                  */ 0b0000000000000000000000011000000;

export const DefaultHydrationLane: Lane = /*            */ 0b0000000000000000000000100000000;
export const DefaultLanes: Lanes = /*                   */ 0b0000000000000000000111000000000;

const TransitionHydrationLane: Lane = /*                */ 0b0000000000000000001000000000000;
const TransitionLanes: Lanes = /*                       */ 0b0000000001111111110000000000000;

const RetryLanes: Lanes = /*                            */ 0b0000011110000000000000000000000;

export const SomeRetryLane: Lanes = /*                  */ 0b0000010000000000000000000000000;

export const SelectiveHydrationLane: Lane = /*          */ 0b0000100000000000000000000000000;

const NonIdleLanes = /*                                 */ 0b0000111111111111111111111111111;

export const IdleHydrationLane: Lane = /*               */ 0b0001000000000000000000000000000;
const IdleLanes: Lanes = /*                             */ 0b0110000000000000000000000000000;

export const OffscreenLane: Lane = /*                   */ 0b1000000000000000000000000000000;

Tips: 本文中的 React 源码均摘自 17.0.2 版本

有些 lane 占用了多个二进制位，表示同时存在几个同优先级的更新，用复数的命名 lanes 来表示。React 对于同一时间发生的相同优先级的更新会合并到一批一起更新。在 lane 模型中，用占用多个相邻二进制位的方式来表示批的概念。

同时，可以发现优先级越低的 lanes 占用的位越多。比如 InputDiscreteLanes 占了 2 个位，TransitionLanes 占了 9 个位。

原因在于：越低优先级的更新越容易被打断，导致积压下来，所以需要更多的位。相反，最高优的同步更新的 SyncLane 只需占用 1 位。

const InputDiscreteLanes: Lanes = /*                    */ 0b0000000000000000000000000011000;
const InputContinuousLanes: Lanes = /*                  */ 0b0000000000000000000000011000000;

export const DefaultLanes: Lanes = /*                   */ 0b0000000000000000000111000000000;
const TransitionLanes: Lanes = /*                       */ 0b0000000001111111110000000000000;

由于 lane 是用二进制数表示的，自然会用位运算来进行优先级相关的计算。React 源码中也封装了一些位运算相关的函数。

includesSomeLane 函数用于计算 a 跟 b 是否存在交集：

// packages/react-reconciler/src/ReactFiberLane.js

export function includesSomeLane(a: Lanes | Lane, b: Lanes | Lane) {
  return (a & b) !== NoLanes;
}

isSubsetOfLanes 函数用于计算 subset 是否为 set 的子集：

// packages/react-reconciler/src/ReactFiberLane.js

export function isSubsetOfLanes(set: Lanes, subset: Lanes | Lane) {
  return (set & subset) === subset;
}

mergeLanes 函数用于将 a 跟 b 进行合并

// packages/react-reconciler/src/ReactFiberLane.js

export function mergeLanes(a: Lanes | Lane, b: Lanes | Lane): Lanes {
  return a | b;
}

removeLanes 函数用于从 set 中移除 subset

// packages/react-reconciler/src/ReactFiberLane.js

export function removeLanes(set: Lanes, subset: Lanes | Lane): Lanes {
  return set & ~subset;
}

getHighestPriorityLane 函数用于获取当前 lanes 中最高优先级的任务。所谓最高优先级的任务，其实就是传入的二进制数中最右边的那个 1 所代表的任务。因为按照 lane 模型的定义，lane 值越小，优先级越高。二进制数中，最右边的 1 代表的数是最小的。

// packages/react-reconciler/src/ReactFiberLane.js

/**
 * 在位运算中，若有负数，则使用该负数的补码参与运算，
 * 如 lanes = 5 = 101 源码
 * -lanes = -5 = 011 补码
 * lanes & -lanes = 101 & 011 = 1
 * 即最右边的 1 代表的那个数字
 */
function getHighestPriorityLane(lanes: Lanes) {
  return lanes & -lanes;
}

对于负数，反码加 1 即为补码。更多详情可见二进制的原码、反码、补码

再看一个例子，若 lanes 为 12（0b1100）：

lanes 为 12，二进制为 0b1100；
-lanes 为 -12，反码为 0b0011，补码（反码加 1 即为补码）为 0b0100（0b0011 + 1）；
lanes & -lanes，即 0b1100 & 0b0100，结果为 0b0100；

最后的结果为 0b0100，转为十进制的话就是 4

getHighestPriorityLane(12); // 4
getHighestPriorityLane(0b1100); // 4

getLowestPriorityLane 函数的功能与 getHighestPriorityLane 函数的功能相反，用于获取当前 lanes 中最低优先级的任务。即分离出二进制数中最左边的 1 。二进制数中，最左边的 1 代表的数是最大的，即优先级最低的任务。

// packages/react-reconciler/src/ReactFiberLane.js

function getLowestPriorityLane(lanes: Lanes): Lane {
  // This finds the most significant non-zero bit.
  const index = 31 - clz32(lanes);
  return index < 0 ? NoLanes : 1 << index;
}

const clz32 = Math.clz32 ? Math.clz32 : clz32Fallback;

Math.clz32 函数返回一个数字在转换成 32 位无符号整形数字的二进制形式后，开头的 0 的个数，比如 4 转换成 32 位无符号整形数字的二进制形式后是 0000 0000 0000 0000 0000 0000 0000 0100，开头的 0 的个数是 29 个，则 Math.clz32(4) 返回 29 。

clz32 其实是 CountLeadingZeros32 的缩写。更多可见 Math.clz32()

由于最高位是符号位，因此 31 - clz32(lanes) 可获得表示具体数字的位数 index。然后将 1 左移 index 位，可获得传入 lanes 最左边的 1 代表的数。

这么讲述会比较抽象，见具体的例子：

假设 lanes(InputDiscreteLanes) = 0b0000000000000000000000000011000
那么 clz32(lanes) = 27, 由于 InputDiscreteLanes 在源码中被书写成了 31 位, 虽然在字面上前导 0 是 26 个, 但是转成标准 32 位后是 27 个
index = 31 - clz32(lanes) = 4
最后 1 << index = 0b0000000000000000000000000010000
相比最初的 InputDiscreteLanes, 分离出来了最左边的 1
通过 lanes 的定义, 数字越小的优先级越高, 所以此方法可以获取最低优先级的任务。

如果当前的执行环境不支持原生的 Math.clz32() 函数，则会用 clz32Fallback 函数代替。clz32Fallback 函数的功能和原生的 Math.clz32() 函数的功能一样，都是返回一个数字在转换成 32 位无符号整形数字的二进制形式后，开头的 0 的个数。

// packages/react-reconciler/src/ReactFiberLane.js

// Count leading zeros. Only used on lanes, so assume input is an integer.
// Based on:
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/clz32
const log = Math.log;
const LN2 = Math.LN2;
function clz32Fallback(lanes: Lanes | Lane) {
  if (lanes === 0) {
    return 32;
  }
  return (31 - ((log(lanes) / LN2) | 0)) | 0;
}

要理解 clz32Fallback 函数需要掌握一点对数的数学知识。

Math.log 函数用于获取自然对数，具体可见 Math.log() 。

Math.LN2 ，一个常数，表示 2 的自然对数，约为 0.693 ，具体可见 Math.LN2。

如果传入的 lanes 为 0 ，则直接返回 32 。这很好理解，因为 0 转为 32 位无符号整形数字的二进制形式后就是 32 个 0 。

按位与（|）0 相当于对一个数进行向下取整，效率比 Math.floor 函数高，我们平时开发中也可以借鉴。

log(lanes) / LN2 用于计算传入的 lanes 开头的 0 的个数。由换底公式可知：

一文读懂 Vue 及 React 源码中的位运算

log(lanes) 就是 ln(lanes)，LN2 就是 ln2 。

log2(lanes) 的值就是真正代表值的最高位的位数。比如：

12 （二进制形式为 0b1100）
(log(12) / LN2 ) | 0 返回 3 ，代表值的最高位的位数为 3 ，即 1000 （从最右边算起，0 位为第 1 位，1 位为第 2 位，依次类推）。

因此 31 减去 log(lanes) / LN2 的值，即 31 减去 真正代表值的最高位的位数 就是一个数字在转换成 32 位无符号整形数字的二进制形式后，开头的 0 的个数 。

总结

Vue 及 React 源码中都大量用到了位运算，二进制数中的 0 、1 很方便地表示两种不同的状态，因此使用多位二进制数可以很方便地标记各种状态，然后通过判断不同的状态执行不同的代码逻辑，同时由于位运算的性能极好，很好地提升了框架的性能。

位运算虽然代码不够直观，但是优点也很明显：代码简洁，性能好。在对代码性能要求高的场景，经常会看到位运算的身影，因此是非常值得学习和掌握的。

参考

lane模型

React 算法之位运算

React18 源码解析之 lanes 模型中的位运算

二进制位运算符

转载自:https://juejin.cn/post/7365055798801940521

一文读懂 Vue 及 React 源码中的位运算

关于位运算的认识

按位与（&）

按位或（|）

按位异或（^）

按位取反（~）

左移（<<）

右移（>>）

无符号右移（>>>）

借助位运算设计权限系统

增加权限

删除权限

校验权限

优点与局限性

Vue 源码中的位运算

React 源码中的位运算

总结

参考

按位与（`&`）

按位或（`|`）

按位异或（`^`）

按位取反（`~`）

左移（`<<`）

右移（`>>`）

无符号右移（`>>>`）