Table of Contents

1. Bit 数组
   1. 数组结构
   2. golang 例子

Bit 数组

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

参考：

---

作者：杨柳_
来源：CSDN
原文：https://blog.csdn.net/qq_37375427/article/details/79797359
版权声明：本文为博主原创文章，转载请附上博文链接！

数组结构

例如：一个 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的所在位置。