go 位图(bitmap)的实现

xiaomeng · · 6917 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

## 位图 [github地址](https://github.com/xiaomeng79/go-algorithm) https://github.com/xiaomeng79/go-algorithm ### 概念 在一个结构中,用一个比特位来描述一个数据的状态,这种结构就称为位图。位图实际上是哈希表的一种变形 ### 位图可以干什么 - 大数据滤重 - 数据排序 ### 为什么使用 - 节省内存 - 可以位操作,更快 ### 代码 ``` package bitmap import "fmt" //位图 type BitMap struct { bits []byte max int } //初始化一个BitMap //一个byte有8位,可代表8个数字,取余后加1为存放最大数所需的容量 func NewBitMap(max int) *BitMap { bits := make([]byte, (max>>3)+1) return &BitMap{bits: bits, max: max} } //添加一个数字到位图 //计算添加数字在数组中的索引index,一个索引可以存放8个数字 //计算存放到索引下的第几个位置,一共0-7个位置 //原索引下的内容与1左移到指定位置后做或运算 func (b *BitMap) Add(num uint) { index := num >> 3 pos := num & 0x07 b.bits[index] |= 1 << pos } //判断一个数字是否在位图 //找到数字所在的位置,然后做与运算 func (b *BitMap) IsExist(num uint) bool { index := num >> 3 pos := num & 0x07 return b.bits[index]&(1<<pos) != 0 } //删除一个数字在位图 //找到数字所在的位置取反,然后与索引下的数字做与运算 func (b *BitMap) Remove(num uint) { index := num >> 3 pos := num & 0x07 b.bits[index] = b.bits[index] & ^(1 << pos) } //位图的最大数字 func (b *BitMap) Max() int { return b.max } func (b *BitMap) String() string { return fmt.Sprint(b.bits) } ```

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

6917 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传