摘要

文章先介绍位掩码的概念、操作符及相关操作，再阐述位集概念，然后讲解在 JavaScript 中如何构建 BitSet 类，包括解析输入索引、实现 add、remove、has 方法，最后提及处理边缘情况并预告下一部分关于位集的快速迭代内容。

一、位掩码（Bit Masks）

位掩码能将多个布尔值紧凑地存储在一个数字中，每个位对应一个布尔值，1 代表true，0 代表false。例如在用户权限管理中，不同的位可表示不同权限（如READ、UPDATE等）。

const READ   = 0b0001;
const UPDATE = 0b0010;
const CREATE = 0b0100;
const DELETE = 0b1000;
function canRead(permissions: number) {
    return (permissions & READ)!== 0;
}
function canUpdate(permissions: number) {
    return (permissions & UPDATE)!== 0;
}

这里使用了位操作符，如&（位与）、|（位或）、~（位非）。

• &操作符：当两个输入位都为 1 时，结果位才为 1。
• |操作符：只要输入位有一个为 1，结果位就为 1。
• ~操作符：是一元操作符，将数字的所有位取反。

可以使用这些操作符进行权限的判断、添加和移除等操作。例如通过&判断是否有某个权限，通过|添加权限，通过~结合&移除权限。不过位掩码有容量限制，JavaScript 只支持 32 位整数，所以只能存储 32 位。

二、位集（Bit Sets）

当需要存储超过 32 个布尔值时，可以使用位集。在 JavaScript 中实现BitSet类，BitSet类中的整数被称为words，存储位集的位。

class BitSet {
    private words: number[];
    add(index: number) { }
    remove(index: number) { }
    has(index: number) { }
}

（一）解析输入索引（Parsing an input index）

由于 JavaScript 支持 32 位整数，定义WORD_LEN为 32。计算wordIndex需要将输入索引右移log2(WORD_LEN)位（即 5 位），可使用>>操作符。计算bitIndex取输入索引的 5 个最低有效位，可使用&操作符与0b11111进行位与操作。

const WORD_LEN = 32;
const WORD_LOG = Math.log2(WORD_LEN);
const wordIndex = index >> WORD_LOG;
const bitIndex = index & 0b11111;

（二）BitSet 类的方法实现

1. BitSet.add 方法

add方法要将指定索引的位设为 1。先计算wordIndex和bitIndex（简化后可直接左移index），然后通过位或操作将对应位设为 1。

class BitSet {
    add(index: number) {
        const wordIndex = index >> WORD_LOG;
        this.words[wordIndex] |= (1 << index);
    }
}

2. BitSet.remove 方法

remove方法要将指定索引的位设为 0。先计算wordIndex，然后创建对应位的位掩码并取反，再通过位与操作将对应位设为 0。

class BitSet {
    remove(index: number) {
        const wordIndex = index >> WORD_LOG;
        this.words[wordIndex] &= ~(1 << index);
    }
}

3. BitSet.has 方法

has方法要判断指定索引的位是否为 1。先计算wordIndex，然后创建对应位的位掩码并进行位与操作，如果结果非零则该位为 1。

class BitSet {
    has(index: number) {
        const wordIndex = index >> WORD_LOG;
        return (this.words[wordIndex] & (1 << index))!== 0;
    }
}

三、处理边缘情况（Handling edge cases）

容易遇到的边缘情况是wordIndex越界，可以添加resize方法确保words数组包含wordIndex，这里没有详细介绍其他边缘情况，可查看 GitHub 上的完整实现。

四、后续内容（Next up）

这篇文章涵盖了很多内容，下一部分将学习如何利用补码和汉明权重快速迭代位集。