位向量-go

1、概述

在实际的使用中，有些集合元素都是小的非负整型，且集合元素较多，比如数据流分析领域，针对集合的操作多数是求交并集，位向量是个理想的数据结构。
位向量使用一个无符号整数值的slice，每一位代表集合中的一个元素，比如设置第i位的元素，则认为集合包含i。

实现： 每一个字拥有bits =32<<(^uint(0)>>63)位（为了兼容32bits、64bits系统，偷巧的方式 <_>）,通过使用源数/bits得到其在slice中索引，再使用源数%bits得到其在uint数据位的内索引，使用位向量同一个索引下会存在多个元素，故而使用uint的每个bit代表一个元素是否存在：1存在 0不存在

2、实现

import (
    "bytes"
    "fmt"
)

const SYSTEM_BIT int =  (32<<(^uint(0)>>63)) // 64
// IntSet: 一个字64bits
type IntSet struct {
    words []uint
}

// Has：是否存在
// 通过使用x得到下标索引及其内位的索引，再判断对应下标是否越界 同时uint内位索引是否有元素(1：有  0：无)
func(s *IntSet) Has(x int) bool{
    word, bit := x/SYSTEM_BIT, uint(x%SYSTEM_BIT) // 字索引  字内位索引
    return word < len(s.words) && s.words[word]&(1 << bit) != 0
}

// Add: 添加
// 根据x得到其在slice中的下标索引及其内位的索引，首先判断当前下标索引是否已存在
// 存在: 代表已有元素存在, 则直接将该索引的元素与位移偏移量 进行 |=(或)操作，这样该索引内容变为两者的和，对应uint内位为1
// 不存在：需要添加新的位置来填充，并将uint其中对应bit位置为1，最后执行元素存在时的或操作
func (s *IntSet) Add(x int){
    word, bit := x/SYSTEM_BIT, uint(x%SYSTEM_BIT)
    for word >= len(s.words){
        s.words = append(s.words,0)
    }
    s.words[word] |= 1 << bit
}

// UnionWith: 并集
// 迭代t中的每个元素
// 对应的s中未存在 则直接append即可
// 若是存在 直接将索引位上的元素与添加元素直接进行 |= 操作即可
func (s *IntSet) UnionWith(t *IntSet){
    for i, tword := range t.words{
        if i < len(s.words){
            s.words[i] |= tword
        } else{
            s.words = append(s.words, tword)
        }
    }
}

// Len: 长度(保留相同索引的不同位的内容)
func (s *IntSet) Len() int{
    count := 0
    for _, word := range s.words{   // 索引位内容
        for word != 0{                   // 内索引位的内容
            count++
            word &= word - 1
        }
    }
    return count
}

// Remove: 移除
func (s *IntSet) Remove(x int){
    word, bit := x/SYSTEM_BIT, uint(x%SYSTEM_BIT)
    s.words[word] &^= 1 << bit     // 与添加操作相反 通过&^(对应位置的值通过与操作位移的异或)
}

// Clear: 清空
func (s *IntSet) Clear(){
    for i := range s.words{
        s.words[i] = 0      // 仅将对应下标索引对应的内容置为0即可
    }
}

// Copy：复制
func (s *IntSet) Copy() *IntSet{
    ss := &IntSet{}
    ss.words = make([]uint, len(s.words))
    copy(ss.words, s.words)
    //
    return ss
}

// String: 字符串表现形式
func (s *IntSet) String() string{
    var buf bytes.Buffer
    buf.WriteByte('{')
    for i, word := range s.words{
        if word == 0{
            continue
        }
        for j := 0; j < 64; j++{
            if word & (1 << uint(j)) != 0{
                if buf.Len() > len("{"){
                    buf.WriteByte(' ')
                }
                fmt.Fprintf(&buf, "%d", 64*i + j)
            }
        }
    }
    buf.WriteByte('}')
    return buf.String()
}

3、使用

func main() {
    //
    var x,y bitvector.IntSet
    x.Add(1)
    x.Add(144)
    x.Add(9)
    fmt.Println(x.String())

    // 添加
    y.Add(9)
    y.Add(42)
    fmt.Println(y.String())

    // 并集
    x.UnionWith(&y)
    fmt.Println(x.String())

    // 存在
    fmt.Println(x.Has(9), x.Has(123))
    //var udatas [4]uint64
    //udatas[0] = 1
    //udatas[0] |= 2
    //fmt.Println(udatas, udatas[0])

    // 移除
    y.Clear()
    fmt.Println(y)

    // 添加
    y.Add(9)
    y.Add(42)
    fmt.Println(y.String())

    // 长度
    len := x.Len()
    fmt.Printf("the Intset's length is %d \n", len)

    // 复制
    sy := y.Copy()
    fmt.Println(sy)
}