BigInt构建高性能位向量方法

本文介绍了一种基于 BigInt 的高性能位向量实现方案，通过“分块（每块64位）+ Map按需存储非空块”的巧妙设计，成功突破 JavaScript 中 Number 类型的53位精度限制，支持百亿级超大整数索引的稀疏标记场景——既保证单比特操作的O(1)时间复杂度，又将内存消耗压缩至仅与实际置位数量成正比，远优于布尔数组（4GB起步）或 Uint32Array（索引与容量双重受限），特别适用于海量用户ID存在性判断等典型稀疏集合问题。

用 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 存储非空块（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) 存十六进制字符串节省体积

到这里，我们也就讲完了《BigInt构建高性能位向量方法》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！