如何用Go实现BitSet?

c90pui9n  于 2023-04-03  发布在  Go
关注(0)|答案(5)|浏览(119)

我在Go中没有找到BitSet包,所以我尝试实现它。我想使用uint64数组来存储位。
我需要分配uint64数组的位数。使用Java,我可以定义一个接受整数的构造函数。虽然Go没有提供构造函数,但当用户调用new()时,我如何正确初始化BitSet 'object'?

9jyewag0

9jyewag01#

Go语言的标准big.Int可以作为一个bit set:

package main

import (
    "fmt"
    "math/big"
)

func main() {
    var bits big.Int
    for i := 1000; i < 2000; i++ {
        bits.SetBit(&bits, i, 1)
    }
    for i := 0; i < 10000; i++ {
        if bits.Bit(i) != 0 {
            fmt.Println(i)
        }
    }
}

https://play.golang.org/p/xbIK-boouqC

vxf3dgd4

vxf3dgd42#

将bitSet声明为私有结构:

type bitSet struct {
  len int
  array []uint64
}

暴露接口BitSet:

type BitSet interface {
  Has(pos int) bool
  Add(pos int) bool
  Len() int
}

还公开了一个函数NewBitSet:

func NewBitSet(len int) BitSet {
  return &bitSet{len, make(uint64, (len+7) / 8) }
}

这是一个封装的Go方式:共享接口,而不是实现。

slmsl1lt

slmsl1lt3#

如果你使用[]uint64切片来存储数据,那么零切片可以用作空的BitSet。事实上,附加到nil切片会为你分配一个新的数组,尽管语言规范似乎并不保证这一点。通过这种设置,new(BitSet)将立即可用。示例:
bitset.go:

package bitset

const size = 64

type bits uint64

// BitSet is a set of bits that can be set, cleared and queried.
type BitSet []bits

// Set ensures that the given bit is set in the BitSet.
func (s *BitSet) Set(i uint) {
    if len(*s) < int(i/size+1) {
        r := make([]bits, i/size+1)
        copy(r, *s)
        *s = r
    }
    (*s)[i/size] |= 1 << (i % size)
}

// Clear ensures that the given bit is cleared (not set) in the BitSet.
func (s *BitSet) Clear(i uint) {
    if len(*s) >= int(i/size+1) {
        (*s)[i/size] &^= 1 << (i % size)
    }
}

// IsSet returns true if the given bit is set, false if it is cleared.
func (s *BitSet) IsSet(i uint) bool {
    return (*s)[i/size]&(1<<(i%size)) != 0
}

bitset_test.go:

package bitset

import "fmt"

func ExampleBitSet() {
    s := new(BitSet)
    s.Set(13)
    s.Set(45)
    s.Clear(13)
    fmt.Printf("s.IsSet(13) = %t; s.IsSet(45) = %t; s.IsSet(30) = %t\n",
               s.IsSet(13), s.IsSet(45), s.IsSet(30))
    // Output: s.IsSet(13) = false; s.IsSet(45) = true; s.IsSet(30) = false
}
m528fe3b

m528fe3b4#

简单地说,当客户端调用new()时,您无法正确地初始化BitSet对象。
你能做的最好的事情就是使BitSet的零值有效。这就是像list.Listsync.Mutexbig.Int这样的类型。这样你就知道客户端不可能得到无效的值。
下一个最好的方法是创建一个类似构造器的函数(在本例中命名为NewBitSet),并期望客户端调用它。

jgzswidk

jgzswidk5#

我也实现了my own,这就是它的工作原理:

bm := bitmask.New(4)        // [4]{0000}
bm.Set(3)                   // [4]{0001}
bm.Slice(2, 4).ToggleAll()  // [4]{0010}
bm.Slice(1, 3).ToggleAll()  // [4]{0100}
bm.Slice(0, 2).ToggleAll()  // [4]{1000}
bm.Clear()                  // [4]{0000}

正如其他人回答的那样,有一个惯例是使用New函数来模拟构造函数。

相关问题