BitSet 原理

•
#go

BitSet 的特点是可以存储大量的数据，但使用很少的空间，原因就是使用 1 位（bit）表示 true/false 。

为了实现简单，我们规定记录数，然后就可以确定要使用的位数，从而可以确定需要的字节数，这里使用 uint64 作为最小的单位，最终通过 []uint64 存所有记录。

size := 100_000_000  
  
// uint64 数组长度  
bsLen := (size-1)/64 + 1  
words := make([]uint64, bsLen)  
  
// 设置为 true  
offset1 := 1000  
words[offset1/64] |= 1 << (offset1 % 64)  
  
// 判断是否为 true
offset2 := offset1 - 1  
exist := words[offset2/64]&(1<<(offset2%64)) != 0

offset/64 代表应该存储到哪个 uint64 ，通过 1 << (offset1 % 64) 找到对应 uint64 的哪一位，通过位或实现添加，位与判断是否存在。

清空（设置为 false ）

可以通过 bit clear（AND NOT） 实现清空：

words[offset3/64] &^= 1 << (offset3 % 64)
// 或者
words[offset3/64] &= ^(1 << (offset3 % 64))

计算 true 的个数

var count int  
for _, word := range words {
    count += bits.OnesCount64(word)  
}

bits.OnesCount64(x uint64) int 是 Go 提供的函数，Java 可以参考 int bitCount(long i) ，实现了相同的功能。