位图在javascript中的实现

位图可以极大程度的压缩某一范围内不重复的数据，也可以优雅的表示一组布尔值的集合，占用空间小，查询速度快

应用场景#

集合操作

• 去重：位图可以用于快速去重，例如在处理大量数据时，位图可以用来记录是否已经出现过某个数据。

• 交集、并集、差集：位图在处理集合的交集、并集和差集时非常高效。
布尔数组

• 布尔标记：位图可以用来表示大量布尔标记，例如在编译器中，记录某个变量是否被使用。

• 任务状态：位图可以用于表示任务或进程的状态，例如任务是否已经完成。
空间优化

• 内存管理：在操作系统中，位图常用于管理内存分配，记录哪些内存块已经被使用。

• 磁盘空间管理：位图用于记录磁盘块的使用情况，哪些块是空闲的，哪些块是已经使用的。
数据过滤

• 布隆过滤器（Bloom Filter）：布隆过滤器使用多个位图来快速判断一个元素是否在集合中，具有高效和低内存占用的优点。
并行计算

• 线程管理：位图用于管理线程的状态，表示哪些线程处于活动状态，哪些线程已经完成。
图像处理

• 图像表示：在图像处理中，位图用于表示黑白图像的像素值，每个位表示一个像素点是黑还是白。

位图在 linux 系统中有大量的应用#

内存管理

• 伙伴系统（Buddy System）：Linux 内核中的内存管理使用伙伴系统来分配和释放内存块。位图用于记录每个内存块的使用情况，快速查找空闲内存块。
文件系统
• ext2/ext3/ext4 文件系统：这些文件系统使用位图来管理磁盘上的数据块和 inode，位图记录哪些数据块和 inode 是已用的，哪些是空闲的，从而高效地管理磁盘空间。
进程管理
• CPU 亲和性（CPU Affinity）：位图用于表示进程可以运行的 CPU 集合，通过位图设置和获取进程的 CPU 亲和性，以优化进程调度和系统性能。
设备管理
• 设备位图：位图用于管理设备的状态，例如网络设备的状态（启用 / 禁用）以及设备的分配情况。
虚拟内存
• 页框分配器（Page Frame Allocator）：位图用于管理物理页框的分配状态，跟踪哪些页框已被分配，哪些页框是空闲的，从而高效地进行页框分配和回收。

位图在前端范围的应用#

图像处理 - canvas 可以直接操作像素数据
位图字体 - 适用于低分辨率和复古游戏设计，渲染更快，更节省空间
布隆过滤器 - 快速查询
前端权限管理 - 将用户权限存储在位图内，可以用极低的占用和性能存储非常多的权限信息

javascript 中实现位图结构 - 基于 Uint8Array#

class Bitmap {
  constructor(size) {
    this.size = size;
    this.data = new Uint8Array(Math.ceil(size / 8));
  }

  // 设置第index位为1
  set(index) {
    if (index >= this.size) throw new RangeError('Index out of bounds');
    const byteIndex = Math.floor(index / 8);
    const bitIndex = index % 8;
    this.data[byteIndex] |= (1 << bitIndex);
  }

  // 清除第index位（设置为0）
  clear(index) {
    if (index >= this.size) throw new RangeError('Index out of bounds');
    const byteIndex = Math.floor(index / 8);
    const bitIndex = index % 8;
    this.data[byteIndex] &= ~(1 << bitIndex);
  }

  // 获取第index位的值
  get(index) {
    if (index >= this.size) throw new RangeError('Index out of bounds');
    const byteIndex = Math.floor(index / 8);
    const bitIndex = index % 8;
    return (this.data[byteIndex] & (1 << bitIndex)) !== 0;
  }
}