golang实现的bitmap,增减查元素,附单元测试

bitmap.go

package ...
import (
	"bytes"
	"fmt"
)
type Bitmap struct {
	//按64*i取模后得到的值(i为数组元素下标)
	modValues []uint64
	length int
}
func (bitmap *Bitmap) IsExist(num int) bool {
	floor, bit := num/64, uint(num%64)
	return floor < len(bitmap.modValues) && (bitmap.modValues[floor]&(1<<bit)) != 0
}
//加入一个数,返回值:是否操作成功,true:本身不存在,加入成功;false:本身已存在
func (bitmap *Bitmap) Add(num int) bool {
	floor, bit := num/64, uint(num%64)
	isExist := false
	for floor >= len(bitmap.modValues) {
		bitmap.modValues = append(bitmap.modValues, 0)
		isExist = true
	}
	//余数转成对应bit位的值
	remainder := uint64(1<<bit)
	// 判断num是否已经存在bitmap中
	if !isExist && bitmap.modValues[floor] & remainder != 0 {
		return false
	}
	isExist = true
	//余数对应的bit位值置为1
	bitmap.modValues[floor] |= remainder
	bitmap.length++
	return isExist
}
//去掉一个数,返回值:是否操作成功,true:本身存在,被删除;false:本身就不存在
func (bitmap *Bitmap) Sub(num int) bool {
	floor, bit := num/64, uint(num%64)
	for floor >= len(bitmap.modValues) {
		return false
	}
	// 判断num是否已经存在bitmap中,不存在直接返回false
	if bitmap.modValues[floor] & (1<<bit) == 0 {
		return false
	}
	//余数对应的bit位值置为0
	bitmap.modValues[floor] -= 1 << bit
	bitmap.length--
	return true
}
func (bitmap *Bitmap) Len() int {
	return bitmap.length
}
func (bitmap *Bitmap) String() string {
	var buf bytes.Buffer
	buf.WriteByte('{')
	for i, v := range bitmap.modValues {
		if v == 0 {
			continue
		}
		uinti := uint(i)
		for j := uint(0); j < 64; j++ {
			if v & (1<<j) != 0 {
				if buf.Len() > 1 {
					buf.WriteByte(',')
				}
				fmt.Fprintf(&buf, "%d", 64 * uinti + j)
			}
		}
	}
	buf.WriteByte('}')
	fmt.Fprintf(&buf,"\nLength: %d", bitmap.length)
	return buf.String()
}

单元测试(bitmap_test.go):

package ...
import (
	"fmt"
	. "github.com/smartystreets/goconvey/convey"
	"testing"
)
func Test_Bitmap(t *testing.T) {
	Convey("test Bitmap", t, func() {
		bitmap := new(Bitmap)
		So(bitmap.Add(3), ShouldBeTrue)
		So(len(bitmap.modValues) == 1, ShouldBeTrue)
		//fmt.Println(bitmap.String())
		
		So(bitmap.length == 1, ShouldBeTrue)
		So(bitmap.Add(5), ShouldBeTrue)
		So(len(bitmap.modValues) == 1, ShouldBeTrue)
		So(bitmap.length == 2, ShouldBeTrue)
		So(bitmap.Add(63), ShouldBeTrue)
		So(len(bitmap.modValues) == 1, ShouldBeTrue)
		So(bitmap.length == 3, ShouldBeTrue)
		So(bitmap.Add(64), ShouldBeTrue)
		So(len(bitmap.modValues) == 2, ShouldBeTrue)
		So(bitmap.Add(127), ShouldBeTrue)
		So(len(bitmap.modValues) == 2, ShouldBeTrue)
		So(bitmap.length == 5, ShouldBeTrue)
		So(bitmap.Add(128), ShouldBeTrue)
		So(len(bitmap.modValues) == 3, ShouldBeTrue)
		So(bitmap.Add(256), ShouldBeTrue)
		So(len(bitmap.modValues) == 256/64+1, ShouldBeTrue)
		So(bitmap.Add(511), ShouldBeTrue)
		So(len(bitmap.modValues) == 512/64, ShouldBeTrue)
		So(bitmap.length == 8, ShouldBeTrue)
		So(bitmap.Add(513), ShouldBeTrue)
		So(len(bitmap.modValues) == 512/64+1, ShouldBeTrue)
		So(bitmap.length == 9, ShouldBeTrue)
		//fmt.Println(bitmap.Add(63))
		fmt.Println(bitmap.String())
		So(bitmap.Add(63), ShouldBeFalse)
		So(len(bitmap.modValues) == 512/64+1, ShouldBeTrue)
		So(bitmap.length == 9, ShouldBeTrue)
		So(bitmap.Sub(632), ShouldBeFalse)
		So(len(bitmap.modValues) == 512/64+1, ShouldBeTrue)
		So(bitmap.length == 9, ShouldBeTrue)
		So(bitmap.Sub(63), ShouldBeTrue)
		So(len(bitmap.modValues) == 512/64+1, ShouldBeTrue)
		So(bitmap.length == 8, ShouldBeTrue)
		So(bitmap.Sub(513), ShouldBeTrue)
		So(len(bitmap.modValues) == 512/64+1, ShouldBeTrue)
		So(bitmap.length == 7, ShouldBeTrue)
	})
}

• 编辑
• 预览