Simple bitmap in golang

simple_bitmap_in_golang.go

package main

import (
	"bytes"
	"fmt"
)

//bitSet实现
type BitSet []uint64

const (
	Address_Bits_Per_Word uint8  = 6
	Words_Per_Size        uint64 = 64 //单字64位
)

//创建指定初始化大小的bitSet
func NewBitMap(nbits int) *BitSet {
	wordsLen := (nbits - 1) >> Address_Bits_Per_Word
	temp := BitSet(make([]uint64, wordsLen+1, wordsLen+1))
	return &temp
}

//把指定位置设为true
func (bs *BitSet) Set(bitIndex uint64) {
	wIndex := bs.wordIndex(bitIndex)
	bs.expandTo(wIndex)
	(*bs)[wIndex] |= uint64(0x01) << (bitIndex % Words_Per_Size)
}

//设置指定位置为false
func (bs *BitSet) Clear(bitIndex uint64) {
	wIndex := bs.wordIndex(bitIndex)
	if wIndex < len(*bs) {
		(*bs)[wIndex] &^= uint64(0x01) << (bitIndex % Words_Per_Size)
	}
}

//获取指定位置的值
func (bs BitSet) Get(bitIndex uint64) bool {
	wIndex := bs.wordIndex(bitIndex)
	return (wIndex < len(bs)) && ((bs)[wIndex]&(uint64(0x01)<<(bitIndex%Words_Per_Size)) != 0)
}

//获取某个值的排位
func (bs BitSet) Rank(bitIndex uint64) uint64 {
	var rank uint64
	var temp uint64
	for i := 0; i < len(bs); i++ {
		temp = (bs)[i]
		for j := 0; j < 64; j++ {
			if temp&(uint64(0x01)<<uint64(j)) != 0 {
				rank++
			}
			bitIndex--
			if bitIndex == 0 {
				return rank
			}
		}
	}

	return rank
}

//以二进制串的格式打印bitMap内容
func (bs BitSet) ToString() string {
	var temp uint64
	strAppend := &bytes.Buffer{}
	for i := 0; i < len(bs); i++ {
		temp = (bs)[i]
		for j := 0; j < 64; j++ {
			if temp&(uint64(0x01)<<uint64(j)) != 0 {
				strAppend.WriteString("1")
			} else {
				strAppend.WriteString("0")
			}
		}
	}
	fmt.Println("len:", len(strAppend.Bytes()))
	return strAppend.String()
}

//定位位置
func (bs BitSet) wordIndex(bitIndex uint64) int {
	return int(bitIndex >> Address_Bits_Per_Word)
}

//扩容:每次扩容两倍
func (bs *BitSet) expandTo(wordIndex int) {
	wordsRequired := wordIndex + 1
	if len(*bs) < wordsRequired {
		if wordsRequired < 2*len(*bs) {
			wordsRequired = 2 * len(*bs)
		}
		newCap := make([]uint64, wordsRequired, wordsRequired)
		copy(newCap, *bs)
		*bs = newCap
	}
}

func main() {
	bMap := NewBitMap(64)
	for i := 100; i < 1025; i++ {
		bMap.Set(uint64(i))
	}
	fmt.Printf("bmap第133个位置:%v \n", bMap.Get(133))
	fmt.Printf("bmap第133个的排位:%v \n", bMap.Rank(133))
	fmt.Printf("bmap2string:%s \n", bMap.ToString())
	fmt.Printf("end:cap=%d,len=%d \n", cap(*bMap), len(*bMap))
}

// 参考 https://play.golang.org/p/tPsib2JNyHq