BigInt位向量通过分块（每块64位）+Map<bigint,bigint>存储非空块，突破Number精度限制，支持百亿级稀疏整数标记，内存仅按需分配。
用 BigInt 实现位向量（Bitset），核心在于绕过 JavaScript 原生 Number 的 53 位安全整数限制，支持超大索引（比如百亿级整数标记），同时保持单比特操作的常数时间复杂度。它特别适合标记海量、稀疏、无重复的整数存在性，比如判断某 ID 是否在 40 亿用户集合中。
为什么 BigInt 比普通数组或 Uint32Array 更适合海量位标记
普通数组（如 boolean[]）每个元素至少占 1 字节，标记 40 亿个数需 4 GB 内存；Uint32Array 虽紧凑，但最大长度受限于 2^32−1（约 42.9 亿），且索引仍是 Number 类型，无法安全表示大于 2^53−1 的位偏移。而 BigInt 支持任意精度整数索引，配合位运算可构建逻辑上无限长的位向量，内存仅按需分配——实际只存“被置 1”的块，稀疏时极省空间。
关键设计：分块 + BigInt 位操作
不把整个位向量拉成一长串 BigInt（不可行），而是采用分块策略，每块用一个 BigInt 表示 64 位（或 32/128 位，64 是常见平衡点）：
- 给定整数
x，计算所在块号：const blockIdx = x / 64n（BigInt 除法） - 计算块内偏移：
const bitPos = x % 64n - 用
1n << bitPos构造掩码，再用|、&、& ~完成 set / test / reset - 用
Map<bigint, bigint>存储非空块（key=blockIdx，value=该块的位图值），避免为全零块分配内存
基础操作实现示例（TypeScript 风格）
以下为精简可运行逻辑（不含边界校验）：
class BigIntBitset {
private blocks = new Map<bigint, bigint>();
set(x: bigint): void {
const blockIdx = x / 64n;
const bitPos = x % 64n;
const mask = 1n << bitPos;
const current = this.blocks.get(blockIdx) ?? 0n;
this.blocks.set(blockIdx, current | mask);
}
test(x: bigint): boolean {
const blockIdx = x / 64n;
const bitPos = x % 64n;
const current = this.blocks.get(blockIdx);
if (current === undefined) return false;
return (current & (1n << bitPos)) !== 0n;
}
reset(x: bigint): void {
const blockIdx = x / 64n;
const bitPos = x % 64n;
const mask = ~(1n << bitPos);
const current = this.blocks.get(blockIdx);
if (current !== undefined) {
this.blocks.set(blockIdx, current & mask);
if (current & mask === 0n) this.blocks.delete(blockIdx); // 清空后删除空块
}
}
}
适用场景与注意事项
- 适用于标记范围极大（如
0到10^12）、但实际数据稀疏（仅百万/千万级活跃 ID）的场景 - 不适用于频繁全量遍历——因为块是稀疏存储的，要遍历所有置 1 位需扫描全部非空块并检查每个 bit
- 注意 V8 引擎对 BigInt 位运算的性能：现代 Chrome/Firefox 中
<<、&已高度优化，但远超 64 位的大整数运算仍慢于原生整数，所以坚持“每块 ≤ 64 位”很关键 - 若需持久化，可序列化为
{ "blocks": [[blockIdx1, value1], [blockIdx2, value2]] }，用BigInt.toString(16)存十六进制字符串节省体积
