BitMap可以在O(n)的复杂度下实现去重和排序，且节省空间。在node下，可以使用Uint8Array存储，每个元素可以存储8个状态，或代表8个数，可以定义为如下：

class BitMap {
    private readonly bytes: Uint8Array;
    private readonly capacity: number;

    constructor(capacity: number) {
        this.capacity = capacity;
        this.bytes = new Uint8Array(capacity);
    }
}

capacity定义为Uint8Array数组的长度，可以根据要存储的数据的最大值算出来，如下：

capacity = max >> 3 // max为要存储的数据的最大值， max >> 3等同于 Math.floor(max / 8)

即一个Uint8能存储8个数字的状态，则存储数字max时，需要存到数组第floor(max / 8)个元素上，

例若要存储的最大值为12345678，则应该定义的Uint8Array长度为：12345678 >> 3 = 1543208。

添加

添加一个数据num到BitMap里的过程如下：

• 先判断数据对应到Uint8Array中哪一个字节上，对应的index计算如下：

byteIndex = num >> 8

• 判断数据应存储到字节的哪一位

一个字节有8位，对数据取余，得到的余数即为要存到的位数：

bitOffset = num & 0x07

注意存到第几位是从0开始的

计算得到了要存储到的字节及字节中的位数，只需要将字节中对应的位置1即可，只需将1左移bitOffset位然后与字节进行或操作即可：

bytes[byteIndex] |= 1 << bitOffset

例，假设bitOffset为3，则1左移3位后变成了：

| 0 |  0  |  0  |  0  |  1  |  0  |  0  |  0  |

假设原字节数据为：

| 0 |  0  |  1  |  0  |  0  |  0  |  0  |  0  |

则两者做或操作后变为:

| 0 |  0  |  1  |  0  |  1  |  0  |  0  |  0  |

也就将相应的位置的0变成了1。

则添加代码如下：

add(num: number) {
    const index = num >> 8;
    const pos = num & 0x07;
    this.bytes[index] |= 1 << pos;
}

清除

删除某个数的状态，同添加一致，计算到byteIndex与bitOffset，然后将字节中对应位置0即可，置0时，将1左移bitOffset位，然后取反，再与原始字节做&操作即可，如下：

bytes[byteIndex] &= ~(1 << bitOffset)

以清除上步添加的位置的状态为例，字节如下：

| 0 |  0  |  1  |  0  |  1  |  0  |  0  |  0  |

bitOffset = 3，将1左移3位得到：

| 0 |  0  |  0  |  0  |  1  |  0  |  0  |  0  |

取反得到：

| 1 |  1  |  1  |  1  |  0  |  1  |  1  |  1  |

将字节与之做与操作，除了变为0的位数相应的变为0，其它位保持不变：

| 0 |  0  |  1  |  0  |  0  |  0  |  0  |  0  |

清除代码如下：

clear(num: number) {
    const index = num >> 8;
    const pos = num & 0x07;
    this.bytes[index] &= ~(1 << pos);
}

判断是否存在

要判断某值是否存在，只要看其对应的位是否为1即可，同添加一致，计算到byteIndex与bitOffset，，将1左移bitOffset位后，除了数值对应的位，其它位均为0，与对应的字节做与操作，若为0，则正面对应字节的对应位为0，说明不存在，否则说明对应字节的对应位为1，说明数值存在，如下：

has(num: number) {
    const index = this.getIndex(num);
    const pos = this.getPosition(num);
    return (this.bytes[index] & (1 << pos)) !== 0;
}

获取到原始值

因为原始值在bitmap中对应的字节索引与在字节中的位数是原始值与8做除法的整除值与余数，因此，可以很简单的到每个字节每位对应的原始值，即：

原始值 = 8 * 字节索引 + 位数

可以写迭代函数如下：

for (let i = 0; i < this.capacity; i ++) {
    const byte = this.bytes[i];
    for (let j = 0; j < 8; j ++) {
        if ((byte & (1 << j)) !== 0) {
            yield (i << 3) + j; // 对应的原始值
        }
    }
}

代码

最终代码如下：

class BitMap {
    private readonly bytes: Uint8Array;
    private readonly capacity: number;

    constructor(capacity: number) {
        this.capacity = capacity;
        this.bytes = new Uint8Array(capacity)
    }

    private getIndex(num: number) {
        return num >> 3; // int(num / 8)
    }
    private getPosition(num: number) {
        return num & 0x07; // num % 8
    }

    size() {
        return this.capacity;
    }

    bits() {
        return this.bytes;
    }

    add(num: number) {
        const index = this.getIndex(num);
        const pos = this.getPosition(num);
        this.bytes[index] |= 1 << pos;
    }

    has(num: number) {
        const index = this.getIndex(num);
        const pos = this.getPosition(num);
        return (this.bytes[index] & (1 << pos)) !== 0;
    }

    clear(num: number) {
        const index = this.getIndex(num);
        const pos = this.getPosition(num);
        this.bytes[index] &= ~(1 << pos);
    }

    *[Symbol.iterator]() {
        for (let i = 0; i < this.capacity; i ++) {
            const byte = this.bytes[i];
            for (let j = 0; j < 8; j ++) {
                if ((byte & (1 << j)) !== 0) {
                    yield (i << 3) + j;
                }
            }
        }
    }
}