在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;
  }
}