go - 如何用 Go 实现 BitSet？

Question

我在 Go 中没有找到 BitSet 包，所以我尝试实现它。我想使用一个 uint64 数组来存储这些位。

我需要分配 uint64 数组的位数。使用 Java，我可以定义一个接受整数的构造函数。虽然 Go 不提供构造函数，但当用户调用 new() 时，如何正确初始化 BitSet“对象”？

Answer 1

Go 的标准big.Int可以用作位集：

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

Answer 2

将 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 的封装方式：共享一个接口，而不是实现。

Answer 3

如果您使用 []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
}

Answer 4

BitSet简短的回答是，当客户端调用new()时，您无法正确初始化对象。

你能做的最好的事情就是让你BitSet的零值有效。这就是喜欢list.List,sync.Mutex和big.Int做的类型。这样您就知道客户端不可能获得无效值。

您可以做的下一个最好的事情是创建一个类似构造函数的函数（NewBitSet在本例中命名）并期望客户端调用它。