位图
嵌牛导读：位图的引出，主要还是在于当我们想做一个很大的set的时候，位图可以帮助我们节省非常大的空间。
嵌牛鼻子：位图
嵌牛提问：处理算法复杂度过高，如何降低算法复杂度呢？
嵌牛正文：
比如说：我们有1千万个整数，整数的范围在1到1亿之间。如何快速查找某个整数是否在1千万个整数中呢？
非常简单的话，我们可以用一个桶来做。但是会浪费90%的空间。即做一个1亿大小的bool数组，哪个数存在，哪个置为true。需要100M空间
用一个散列表。假设散列函数非常完美，有50%的占有率的一个hashset。我们需要2千万 * 4 = 80M大小的空间。但是这里的散列函数是有一点计算复杂度的。
引出
而我们的位图就是用的第一种思想，但是，我们用一个字节来表示俩个状态，true和false太过浪费，我们就只用1个bit来表示。
所以就只需要100M / 8 = 20 大概不到20M左右的空间。
小坑
我们的想法是非常好的，但是要怎么操作呢？大部分语言中让我们可以操纵的最小计算机单位是1个字节。即我们是没办法直接去操纵一个位的。因此我们就需要一个映射。
Add
原来的想法
如果我们想要表示1个数字已经存在，比如x。我们直接就是
vector<bool> charVec;
charVec[x] = true;
这样就可以了。
上面的想法实际上就是置第x+1个bool值为true，位图的想法就是去置第x+1个bit值为1
但是大部分语言提供的最小的可操作单位就是一个字节。因此我们就需要做一个简单的映射
int index = x / 8
int bit = x % 8
charVec[index] |= 1 << bit
// 或者
vector<int16t> int16Vec
int index = x / 16
int bit = x % 16
int16Vec[index] |= 1 << bit
// 或者
vector<int32t> int32Vec
int index = x / 32
int bit = x % 32
int32Vec[index] |= 1 << bit
我觉得上面的代码已经讲得非常清楚了，用语言表示反而比较苍白无力。
比如说我们想要Add(100)，我们就需要在第101个bit上置1。（我们的第一个bit置1表示0，这个可以自己修改），然后我们就要算出第101个bit首先在第多少个字节上。其在第index个字节上。然后再算出其在第多少个bit上。其在第bit+1个bit上。大概就是这样的一个数学关系，举几个例子就很好理清楚。
Has
如何判断一个数是否在我们在set中呢？
int index = x / 8
int bit = x % 8
if( charVec[index] & (1 << bit) )
return true
备注：以上是大概类似c++形式的伪代码。仅仅做了俩个方法，C++11是新出了bitset的数据结构供我们使用的。非常方便。我自己就不重复造轮子了。下面是《Go语言圣经》中的部分源码，注意其底层结构时动态增长的。
go源码
type IntSet struct {
words []uint64
}
func (s *IntSet) Has(x int) bool {
index, bit := x/64, uint(x%64)
return index < len(s.words) && s.words[index]&(1<<bit) != 0
}
func (s *IntSet) Add(x int) {
index, bit := x/64, uint(x%64)
// 扩容，如果下标不够就需要扩容
for index >= len(s.words) {
s.words = append(s.words, 0)
}
s.words[index] |= (1 << bit)
}
// 合并俩个set
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)
}
}
}
func (s *IntSet) String() string {
var buf bytes.Buffer
buf.WriteByte('{')
for i, word := range s.words {
if word == 0 {
continue
}
for j := 0; j < 64; j++ {
if word&(1<<uint(j)) != 0 {
if buf.Len() > len("{") {
buf.WriteByte(' ')
}
fmt.Fprintf(&buf, "%d", 64*i+j)
}
}
}
buf.WriteByte('}')
return buf.String()
}
