Bitset 和 boolean 数组有什么区别？为什么位图能节省空间？

简化版

boolean 数组通常一个元素存一个布尔值，Bitset 用一个 bit 表示一个状态。Bitset 能把空间压缩到约 1/8，但读写要通过位运算完成。

详细版

当只需要表示“是否存在”“是否访问过”“是否开启”时，Bitset 很适合。

boolean 数组表达简单，访问直观。
Bitset 把多个布尔状态打包到整数的不同 bit 上。
第 i 个状态通常位于 word = i / 32、bit = i % 32。
设置、清除、查询都依赖按位或、按位与、移位。
Bitset 节省空间，但代码可读性和边界处理更复杂。

完整版教学

一、为什么 boolean 数组可能浪费空间

从语义上看，布尔值只需要 0 或 1，一个 bit 就够。但很多语言里的 boolean 数组元素并不一定只占 1 bit，可能按字节甚至更大的单位存储，方便 CPU 访问和对象布局。假设要表示 1 亿个用户是否在线，boolean 数组如果按 1 字节算约 100MB；Bitset 用 1 bit 表示一个用户，约 12.5MB。这个空间差距非常明显。

100,000,000 个状态
boolean 按 1B：约 100MB
bitset 按 1bit：约 12.5MB

记忆钩子：boolean 数组是一人一间房，Bitset 是八个人合住一个字节。

二、Bitset 如何定位第 i 个 bit

Bitset 通常用整数数组作为底层存储。以 32 位整数为例，第 i 个状态在第 i / 32 个整数里，具体是第 i % 32 位。查询时构造掩码 1 << bit，再和对应整数做按位与。设置时做按位或，清除时做按位与非。这就是用数组下标定位 word，再用 bit 位定位状态。

const words = new Uint32Array(Math.ceil(n / 32));
function set(i) {
  words[i >> 5] |= (1 << (i & 31));
}
function has(i) {
  return (words[i >> 5] & (1 << (i & 31))) !== 0;
}

三、常见操作的位运算原理

设置某一位为 1，用 OR，因为 x | 1 = 1，其他位保持不变。查询某一位，用 AND，因为只有目标位同时为 1 时结果才非零。清除某一位，用 & ~mask，目标位变 0，其他位不变。理解这三种操作，就能读懂大部分 Bitset 代码。

操作	表达式	含义
设置	`word	= mask`
查询	`word & mask`	判断目标位
清除	`word &= ~mask`	目标位置 0
翻转	`word ^= mask`	目标位取反

四、带数字算一个定位例子

假设使用 32 位 word，要访问第 70 个状态。70 / 32 = 2 余 6，所以它在 words[2] 的第 6 位。mask 是 1 << 6，也就是 64。如果 words[2] & 64 非零，说明第 70 个状态为真。这个例子能帮助你把“数组 + 位”两层定位关系具象化。

i = 70
wordIndex = floor(70 / 32) = 2
bitIndex = 70 % 32 = 6
mask = 1 << 6 = 64

五、Bitset 的优势不只是省空间

Bitset 还有一个优势是可以批量位运算。例如两个集合求交集，可以对底层 word 数组逐个做 AND，一次处理 32 或 64 个状态。权限集合、标签过滤、布隆过滤器、访问标记都可能用到这个特性。CPU 对位运算非常擅长，数据又更紧凑，缓存命中也更好。

A: 10110100
B: 00111100
A & B = 00110100

六、Bitset 的代价和边界

Bitset 可读性比 boolean 数组差，越界、移位、符号位、word 大小都要小心。它适合状态数量巨大、状态值简单的场景；如果每个元素还要存多种信息，就不适合强行塞 bit。还有些语言的标准库已经提供 BitSet 或 bitmap，不必手写底层位运算。工程里要在空间、性能和可维护性之间取舍。

适合：是否访问、是否存在、权限开关、大规模标记
不适合：每个元素需要复杂对象、多字段状态

七、常见误区与追问

误区：boolean 一定只占 1 bit。 很多语言为了访问效率和内存布局，不会逐 bit 存 boolean 数组。
误区：Bitset 只能省空间。 它还能用批量位运算加速集合交并差。
误区：位运算一定比普通数组更好。 数据量小或可读性更重要时，boolean 数组更直接。
追问：第 i 位怎么定位？ 先找 i / wordSize 的 word，再找 i % wordSize 的 bit。
追问：如何清除某一位？ 用 word &= ~mask，只把目标位变 0。

八、加强记忆

Bitset 可以记成“把布尔数组压成二进制纸带”。数组负责找第几个 word，位运算负责找 word 里的第几个格子。回答时讲出空间节省、定位公式、四种位操作和可维护性边界，就能把这题答得既底层又实际。

简化版

详细版