Golang 位向量

位图

　　位图（Bitmap）是通过一个 bit 来表示某个元素对应的值或者状态。它并不是什么新的数据结构。它的内容其实就是普通的字符串。

　　在redis中，我们可以通过 get/set 获取位图的内容，也可以使用 getbit/setbit 操作 bit 值（0 或者 1）。

　　Bit即比特，是目前计算机中数据最小的单位。

　　8个Bit一个Byte（字节）。Bit的值，要么为 0 ，要么为 1。

　　由于Bit是计算机中最小的单位，使用它进行储存将非常节省空间。特别适合一些数据量大的场景。例如，统计每日活跃用户、统计每月打卡数等统计场景。

    

       可以看出，上图中，将b、i、g各自的ASCII值用1byte来存储，redis中能够用命令来修改每一个bit的值(0或1)

位向量

　　与位图存储不同之处在于，位向量注重偏移量和存储索引

　　例如如何利用位向量向集合中插入值呢？

　　

　　如何利用位向量判断值A是否存在呢？

　　1. 值A的索引要存在，例如在位向量中，集合中最大值的索引之后是没有存储变量的，所以也要对A分割出索引index和偏移offset，如果index>集合长度，则认为不存在

　　2. 判断了索引还需要判断片偏移，将1<<offset的结果与索引位上的值逐位相&（与），若为1则集合中存在A。

// 集合
type UintSet struct {
    words []uint64
}

// 向bitmap插入数据
func (s *UintSet) AddEle (x int)  {
    index, offset := x/64, uint(x%64)
    for index >= len((*s).words) {
        (*s).words = append(s.words, 0)
    }
    bitVal := uint64(1 << offset)
    (*s).words[index] = bitVal
}

// 向bitmap查找数据
func (s *UintSet) find(ele int) bool {
    index, offset := ele/64, uint(ele%64)
    return index < len((*s).words) && s.words[index]&(1<<offset)!=0
}