如何用Go实现BitSet？

Question

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

Answer 1

如果使用[] uint64切片存储数据，则零切片可以用作空的BitSet。实际上，附加到nil切片会为您分配一个新数组，尽管Language Specification似乎并不能保证这一点。通过这种设置，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

}