← 首页 / Bitmask 的三副面孔 · 一个 bit 能当什么用 待审核
bitset · popcount / n & -n

Bitmask 的三副面孔 · 一个 bit 能当什么用

一个整数的二进制位，在不同场景里被赋予完全不同的含义，但底层都是同一个直觉——用位运算代替遍历。本页把同一个 bit 摊成三副面孔：bit 作集合成员（AND/OR/XOR 算集合）、bit 作 entry（整串 mask 当身份给 module 分 chunk,Rolldown 的做法）、bit 作 lane 占用(n & -n 一步选最高优先级，@vega/job 调度器与 Linux O(1) scheduler 的做法)。每个 demo 能点开关 / 单步，看二进制位实时变化、看那条位运算到底省下了什么。三面：bit = 集合成员 · bit = entry,mask 当身份 · bit = lane 占用，n & -n。

1 · 第一副面孔：一个整数装下一个集合

warm-up · bit = 集合成员

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

源自一道经典题 Find the Prefix Common Array：问两个数组在每个前缀里有几个共同元素。把「见过哪些数」各塞进一个 bitmask，答案就是 (a & b).bit_count()——用硬件指令一步算出交集大小。下面两个集合都从 {0..7} 里挑，点数字开关。

把上面的「数字」换成「entry」，这张 bitmask 就成了 Rolldown 给每个 module 算的可达性指纹——A & B 的 popcount 就是「两个 module 共享了几个 entry」。Rolldown 的可达性指纹一节说明它如何靠「bits 相等」把 module 分进同一个 chunk。

counting · 一个 bitmask = 一个子集

1.1 · 顺带一题：6 个人能拉多少个微信群？

既然「第 i 位为 1 ↔ 第 i 个元素在集合里」，那么一个 n 位的整数就恰好对应一个子集：每个人独立地有「在群 / 不在群」两种状态，枚举 0..2n−1{0 .. 2^n-1} 就走遍了全部子集，共 2ⁿ 个。女生宿舍 6 位同学、且允许 1 人单独建群，可能的微信群数目就是非空子集个数——去掉 0（谁都不在的空群）即 2ⁿ − 1。下面拖人数、点 ▶ 逐个枚举验证。

枚举到这里能看清两件事：其一，子集总数 = 2ⁿ 不是巧合，而是「n 个独立的 0/1 选择」的乘积 2×2×⋯×2{2\times 2\times \dots \times 2}；其二，按人数分组求和 ΣC(n,k)=2nΣ C(n,k) = 2^n（二项式定理在 x = 1 处的取值）。所以 6 人的答案是 26−1=63{2^6 - 1 = 63}——这正是「一个整数装下一个集合」最朴素的计数推论。

2 · 第二副面孔：整个 bitmask 当一个「身份」

Rolldown · bit = entry,整个 mask 当身份

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

关键一步：bits 完全相同的 module，放进同一个 chunk。Rolldown 直接拿整个 bitset 当 HashMap<BitSet, ChunkId> 的 key——这不是数交集（set-ops 那副面孔的 AND），而是把整串 mask 当一个身份做相等聚类。下面 3 个 entry(A=bit0⋅B=bit1⋅C=bit2A=bit0 \cdot B=bit1 \cdot C=bit2)，单步观察 bits 如何累积、最后如何分组。留意 core 与 util：二者都被三个 entry 可达 (111)，因此合进同一个 shared chunk。

数一下：6 个 module → 5 个 chunk。指纹各异的 001/011/110/100 各成一块，而 core 和 util 指纹都是 111 → 同一个 shared chunk。这就是「bits 相等即同 chunk」节省的开销：无需两两比较 module,一次 HashMap 查表就完成分组。

和调度器的对照：这里 bit 是数据（哪个 entry 可达），整串 mask 是身份；运算是 OR 传播 + 相等聚类。n & -n 选优先级那副面孔里的 @vega/job 调度器，bit 变成控制位（哪条 lane 有任务），运算变成 n & -n 选最高优先级——同一个「用位避免扫描」的思路，两种完全不同的应用方式。

3 · 第三副面孔：用一个 6 位整数选「先跑谁」

@vega/job · bit = lane 占用,n & -n 选最高优先级

@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)O(1)，不用扫。

为什么 n & -n 留下最低的 1？补码 -n = ~n + 1：取反把最低 1 右边的 0 全变 1、最低的 1 变 0，再 +1 进位回来，恰好让最低那个 1 的位置两边对齐、其余位互补——AND 一下只剩它。再用 31−clz32(bit){31 - clz32(bit)}（数前导零）把这个单 bit 还原成 lane 索引。见 packages/job/src/engine/scheduler/level-queue.ts · priority.ts。

这正是 LevelQueue.shift() 所做的：bit = pendingLanes & -pendingLanes → idx=31−Math.clz32(bit)idx = 31 - Math.clz32(bit) → lanes[idx].shift()；某条 lane 空了就 pendingLanes &= ~bit 清掉它的位。push 是 pendingLanes |= 1<<i。取最高优先级、判空、加入，全是 O(1)O(1) 位操作，从不遍历 6 条 lane。

同一个 bit 直觉，三副面孔收束：set-ops 里 bit 是集合成员（AND/OR/XOR 算集合）;reachability 里 bit 是 entry、整串 mask 当身份做分组；这里 bit 是 lane 占用、用 n & -n 做优先级选择。最后这副和 Linux O(1) scheduler 的 bitmap、React 的 lane model 是同一脉——而不是 Rolldown 的 code-splitting。

缘起：有人问 @vega/job 调度器里那个 bitmask，是不是和 Rolldown code splitting 同一套做法。答案是「同一个 bit 直觉、两种完全不同的用法」——本页把这个对照展开：Rolldown 是 OR 传播 + 相等聚类（reachability 那副面孔），调度器是 n & -n 优先级选择（lowest-bit 那副面孔）。

相关链接