Bit 数组

位数组，主要是为了有效地利用内存空间而设计的一种存储数据的方式。 在这种结构中一个整数在内存中用一位（1 bit）表示。 这里表示就是如果整数存在，相应的二进制位就为 1，否则为 0。

学习思路：CSDN-杨柳

---

数组结构

例如：一个 char 类型的数据在内存中占用 1Byte（即 8 bit），如果我们用二进制位在内存中的顺序来代表整数则可以存储更多的信息。

一个 char 类型可以存储 8 个整数。假设 a 是一个 char 数组的话，整数 8 就可以用 a[1] 的第一个二进制位表示了。 那么 512 字节就是 4096 位，第一位代表 0，第二位代表 1，第三位代表 2，第 4096 位代表 4095，这样我们就可以用 512 字节存储 4096 个数了，大大的节省了内存空间。

golang 例子

// An IntSet is a set of small non-negative integers.
// Its zero value represents the empty set.
type IntSet struct {
    words []uint64
}

// Has reports whether the set contains the non-negative value x.
func (s \*IntSet) Has(x int) bool {
    word, bit := x/64, uint(x%64)
    return word < len(s.words) && s.words[word]&(1<<bit) != 0
}

// Add adds the non-negative value x to the set.
func (s \*IntSet) Add(x int) {
    word, bit := x/64, uint(x%64)
    for word >= len(s.words) {
        s.words = append(s.words, 0)
    }
    s.words[word] |= 1 << bit
}

// UnionWith sets s to the union of s and t.
func (s *IntSet) UnionWith(t *IntSet) {
    for i, tword := range t.words {
        if i < len(s.words) {
            s.words[i] |= tword
        } else {
            s.words = append(s.words, tword)
        }
    }
}

因为每一个字都有 64 个二进制位，所以为了定位 x 的 bit 位，我们用了 x/64 的商作为字的下标，并且用 x%64 得到的值作为这个字内的 bit 的所在位置。