Bitmask 的三副面孔

一个整数的二进制位在不同场景里被赋予完全不同的含义，底层却是同一个直觉：用位运算代替遍历。本页把同一个 bit 摊成三副面孔。§1 把 bit 当集合成员，用 AND、OR、XOR 直接算集合；§2 把整串 mask 当身份，这是 Rolldown 给 module 分 chunk 的做法；§3 把 bit 当 lane 占用，用 n & -n 一步选出最高优先级，这是 @vega/job 调度器与 Linux O(1) scheduler 的做法。

1 · bit 作集合成员

一个整数的二进制位可以当成一个集合：第 $i$ 位为 1 等价于元素 $i$ 在集合里。于是集合运算全部落到一条 CPU 指令上，交集是 AND、并集是 OR、对称差是 XOR，再用 popcount（数 1 的个数）就知道结果集合有多大。这是 bitset 的底层直觉，后两副面孔都由此延伸。

这一副面孔的典型题是 Find the Prefix Common Array，问两个数组在每个前缀里有几个共同元素。把「见过哪些数」各塞进一个 bitmask，答案就是 (a & b).bit_count()，用一条硬件指令算出交集大小，无需逐元素比对。把上面的数字换成 entry，同一张 bitmask 就成了 §2 的可达性指纹。

1.1 · 子集计数

既然第 $i$ 位为 1 等价于第 $i$ 个元素在集合里，那么一个 $n$ 位的整数就恰好对应一个子集：每个元素独立地有「在」与「不在」两种状态，枚举 $0$ 到 $2^n - 1$ 即走遍全部子集，共 $2^n$ 个。若要求集合非空，去掉全零的那一个，得 $2^n - 1$。

枚举到这一步能看清两件事。其一，子集总数 $2^n$ 不是巧合，而是 $n$ 个独立的二选一之积。其二，按元素个数分组求和有 $\sum_{k=0}^{n} \binom{n}{k} = 2^n$，即二项式定理在 $x = 1$ 处的取值。$n = 6$ 时两条都给出 64，非空子集因而是 63。

2 · 整串 mask 作身份

打包器要把大量 module 切成若干 chunk。Rolldown 与 esbuild 的做法是给每个 entry 分配一个 bit 位，然后从每个 entry 出发做 BFS，把这个 entry 的 bit 用 OR 并进它能到达的每个 module。于是每个 module 累积出一串 bits，即「哪些 entry 能到我」的可达性指纹。

关键的下一步是：bits 完全相同的 module 放进同一个 chunk。Rolldown 直接拿整个 bitset 当哈希表的 key。这不是 §1 那种数交集的用法，而是把整串 mask 当一个身份做相等聚类。

图 2-1 里 6 个 module 分成 5 个 chunk：指纹各异的 001、011、110、100 各成一块，指纹同为 111 的 core 与 util 合成一个 shared chunk。相等聚类省下的是两两比较，一次哈希查表即完成分组。

3 · bit 作 lane 占用

@vega/job 的调度器有 6 条优先级 lane，数值越小越紧急。同 lane 内严格 FIFO，跨 lane 永远先跑数值小的。每次取下一个任务要找最高优先级的非空 lane，朴素做法是从 lane 0 扫到 lane 5。它改用位技巧：把哪条 lane 非空压成一个 6 位整数 pendingLanes，第 $i$ 位为 1 等价于 lane $i$ 有活，然后 pendingLanes & -pendingLanes 一步拿到最低置位 bit，即最高优先级的非空 lane，代价 $O(1)$。

n & -n 能留下最低的 1，是补码 $-n = \lnot n + 1$ 的直接后果。设 $n$ 的最低置位在第 $k$ 位，则第 $k$ 位右侧全是 0。取反后第 $k$ 位变 0、其右侧全变 1；再加 1 时这串 1 全部进位，结果第 $k$ 位重新变回 1、其右侧归零，而第 $k$ 位左侧的每一位都与 $n$ 相反。两者按位与，左侧因互补而全灭、右侧本就是 0，只剩第 $k$ 位。取到这个单 bit 之后，用 31 - Math.clz32(bit)（数前导零）还原成 lane 索引。

三副面孔到此收束：§1 里 bit 是集合成员，用 AND、OR、XOR 算集合；§2 里 bit 是 entry、整串 mask 当身份做分组；§3 里 bit 是 lane 占用，用 n & -n 做优先级选择。最后一副与 Linux O(1) scheduler 的优先级 bitmap、React 的 lane model 同源，而与 Rolldown 的 code splitting 只是共用了位运算这层直觉。