193 lines
3.6 KiB
Go
193 lines
3.6 KiB
Go
package bitmap
|
||
|
||
import (
|
||
"encoding/base64"
|
||
"sync"
|
||
)
|
||
|
||
/*
|
||
@Author: by LH
|
||
@date: 2019-06-12
|
||
@function:位图算法go语言版本类型抽象
|
||
*/
|
||
const byteBitLength = 8 //一个字节的位数,也是一个uint8类型的位数
|
||
|
||
type BitMap struct {
|
||
value []uint8
|
||
//bit uint64
|
||
mu sync.RWMutex
|
||
count uint64
|
||
}
|
||
|
||
func NewBitMapFromBase64String(s string) (*BitMap, error) { //不要太长比较好
|
||
decodeBytes, e := base64.StdEncoding.DecodeString(s)
|
||
if e != nil {
|
||
return nil, e
|
||
}
|
||
|
||
return &BitMap{
|
||
value: decodeBytes,
|
||
count: count(decodeBytes),
|
||
mu: sync.RWMutex{},
|
||
}, nil
|
||
}
|
||
|
||
//统计1数量
|
||
func count(m []byte) (r uint64) {
|
||
for _, v := range m {
|
||
for i := 0; i < byteBitLength; i++ {
|
||
if ByteIndexIsOne(v, i) {
|
||
r++
|
||
}
|
||
}
|
||
}
|
||
return
|
||
}
|
||
|
||
//从string加载
|
||
func NewBitMapFromString(s string) *BitMap {
|
||
|
||
return &BitMap{
|
||
value: []byte(s),
|
||
mu: sync.RWMutex{},
|
||
count: count([]byte(s)),
|
||
}
|
||
}
|
||
|
||
func (b *BitMap) Reset() {
|
||
b.mu.Lock()
|
||
defer b.mu.Unlock()
|
||
b.value = make([]uint8, 0)
|
||
b.count = 0
|
||
}
|
||
|
||
func (b *BitMap) Count() uint64 {
|
||
return b.count
|
||
}
|
||
|
||
//获取当前位数长度
|
||
func (b *BitMap) Length() int {
|
||
b.mu.RLock()
|
||
defer b.mu.RUnlock()
|
||
return len(b.value) * byteBitLength
|
||
}
|
||
|
||
//func (b *BitMap) BitLength() uint64 {
|
||
// return b.bit
|
||
//}
|
||
|
||
//判断指定位置是否为1
|
||
func (b *BitMap) IsBit(index int) (r bool) {
|
||
b.mu.RLock()
|
||
defer b.mu.RUnlock()
|
||
if index < 0 || index >= len(b.value)*byteBitLength { //边界情况
|
||
return
|
||
}
|
||
x := index / byteBitLength
|
||
y := index % byteBitLength
|
||
if ByteIndexIsOne(b.value[x], y) {
|
||
r = true
|
||
}
|
||
return
|
||
}
|
||
|
||
//value数组增加num个长度
|
||
func (b *BitMap) addLength(n int) {
|
||
for i := 0; i < n; i++ {
|
||
b.value = append(b.value, 0)
|
||
}
|
||
}
|
||
|
||
//设置指定位置为1
|
||
func (b *BitMap) SetBit(index int) {
|
||
if index < 0 {
|
||
return
|
||
}
|
||
|
||
b.mu.Lock()
|
||
defer b.mu.Unlock()
|
||
if index >= len(b.value)*byteBitLength { //需要加长度
|
||
b.addLength(index/byteBitLength + 1 - len(b.value))
|
||
}
|
||
|
||
arrIndex := index / byteBitLength
|
||
bitIndex := index % byteBitLength
|
||
|
||
if !ByteIndexIsOne(b.value[arrIndex], bitIndex) { //不为1时设置为1
|
||
b.value[arrIndex] ^= 128 >> bitIndex
|
||
b.count++
|
||
}
|
||
|
||
}
|
||
|
||
//设置指定位置为0
|
||
func (b *BitMap) CancelBit(index int) {
|
||
if index < 0 || index >= len(b.value)*byteBitLength {
|
||
return
|
||
}
|
||
|
||
arrIndex := index / byteBitLength
|
||
bitIndex := index % byteBitLength
|
||
|
||
if ByteIndexIsOne(b.value[arrIndex], bitIndex) { //为1时设置为0
|
||
b.mu.Lock()
|
||
defer b.mu.Unlock()
|
||
b.value[arrIndex] ^= 128 >> bitIndex
|
||
b.count--
|
||
}
|
||
}
|
||
|
||
//base64转化为string
|
||
func (b *BitMap) Base64String() string {
|
||
b.mu.RLock()
|
||
defer b.mu.RUnlock()
|
||
return base64.StdEncoding.EncodeToString(b.value)
|
||
}
|
||
|
||
//转 string
|
||
func (b *BitMap) String() string {
|
||
b.mu.RLock()
|
||
defer b.mu.RUnlock()
|
||
return string(b.value)
|
||
}
|
||
|
||
//判断一个byte的指定位置是否为1,顺序为从高位到低位下标分别为0->7
|
||
func ByteIndexIsOne(a byte, index int) bool {
|
||
if index < 0 || index >= byteBitLength {
|
||
return false
|
||
}
|
||
|
||
//t := a
|
||
//t ^= 128 >> index //判断t是否和a相等
|
||
a <<= index
|
||
a >>= 7
|
||
if a == 0 {
|
||
return false
|
||
}
|
||
return true
|
||
}
|
||
|
||
func ByteReverse(b byte) byte {
|
||
for i := 0; i < 4; i++ {
|
||
if (b&(128>>i))>>(7-i) != (b&(1<<i))>>i {
|
||
b ^= 128 >> i
|
||
b ^= 1 << i
|
||
}
|
||
}
|
||
return b
|
||
}
|
||
|
||
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>以下函数为测试,封装好类型的在上面<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
|
||
//从第0位开始判断
|
||
func GetBit(s []uint8, index int) (r bool) {
|
||
if index < 0 || index >= len(s)*byteBitLength { //边界情况
|
||
return
|
||
}
|
||
a := index / byteBitLength
|
||
b := index % byteBitLength
|
||
if ByteIndexIsOne(s[a], b) {
|
||
r = true
|
||
}
|
||
return
|
||
}
|