更多优质内容
请关注公众号

算法小白的入门日记(十四)高性能统计结构——位图-张柏沛IT博客

正文内容

算法小白的入门日记(十四)高性能统计结构——位图

栏目:算法专题 系列:算法小白的入门日记 发布时间:2021-12-03 13:40 浏览量:272
本系列文章目录
展开/收起

· 位图

位图是内存中连续的二进制位(bit)所组成的数据结构,该算法主要用于对大量整数做去重和查询操作。

 

位图的每一个位都有自己下标,从0开始,且位图下标的递增是从右到左的(大端表示法)。每一个位的值只能是01

例如我想往一个大小为10bite的位图中插入4,2,1,34个值,那么就需要在下标为4,2,1,3的位上设置值为1

 

位图的实现

位图不像整型、字符类型这种简单的数据类型被各种语言直接支持,由于一个位图有成千上万位,因此需要用一个long型(64位)的数组把所有的位连起来。下面为了画图方便,我们使用4位整型的数组代替long型数组。

 

依旧是以10bite的位图为例,该位图用4位整型的数组表现为:

 

上图中,每一个数组元素都有4个位,一共有12个位,每个位的下标在自己的数组元素内是从右到左递增的,在元素与元素之间是从左到右递增的。但在逻辑上我们把它当做是下标从右到左递增的。

在下标为4,7,9,3的位上设置值为1后变成:

 

Q2:如何把某个位下标的值设为0或者1

假设位下标为 i

1.先找到位下标对应的数组下标

idx = math.floor(i / 4)

 

2.让arr[idx]中对应的位与 1 << i进行|运算可置为1,与^(1 << i)进行&运算可置为0

arr[idx] | (1 << i) 可将下标i的位置为1arr[idx] & ^(1 << i) 可将下标i的位置为0

 

例如下图:

我想把位下标为6的位置为1。已知它所在的数组元素是arr[1]

arr[2] = arr[2] | (1 << 6) = 1001 | 0100 = 1101

 

我想把位下标为7的位置为1。已知它所在的数组元素是arr[1]

arr[2] = arr[2] & ^(1 << 7) = 1001 & (^1000) = 1001 & 0111 = 0001

 

 

下面是位图的代码实现:

type Bitmap struct{
	arr []int64
	size int
}

func BitMapConstructor(size int) *Bitmap{
	arr := make([]int64, getBitInArrIdx(size-1) + 1)
	return &Bitmap{size:size, arr:arr}
}

// 获取某个位下标对应的数组下标
func getBitInArrIdx(bitIdx int) int{
	return bitIdx >> 6
}

// 将位下标idx下的位置为1
func (this *Bitmap) setBit(idx int){
	if idx >= this.size{	// 超出范围
		return
	}
	arrIdx := getBitInArrIdx(idx)
	this.arr[arrIdx] |= int64(1) << (idx % 64)
}

// 将位下标idx下的位置为0
func (this *Bitmap) unsetBit(idx int){
	if idx >= this.size{	// 超出范围
		return
	}
	arrIdx := getBitInArrIdx(idx)
	this.arr[arrIdx] &= ^(int64(1) << (idx % 64))
}

// 获取位下标idx位置的值
func (this *Bitmap) getBit(idx int) bool{
	if idx >= this.size{	// 超出范围
		return false
	}
	arrIdx := getBitInArrIdx(idx)
	return this.arr[arrIdx] & (int64(1) << (idx % 64)) != 0
}

 




更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > 算法小白的入门日记(十四)高性能统计结构——位图

热门推荐
推荐新闻