How to implement BitSet with Go?

I didn't find a BitSet package in Go, so I tried to implement it.
I'd like to use a array of uint64 to store the bits.

I need the number of bits to allocate the uint64 array.
With Java, I can define a constructor that takes an integer.
While Go doesn't provide constructor, how can I properly initialize
the BitSet 'object' when user call new()?

Go's standard big.Int can be used as a 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

Declare bitSet as a private struct:

type bitSet struct {
  len int
  array []uint64
}

Expose the interface BitSet:

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

Also expose a function NewBitSet:

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

This is a Go way for encapsulation: share an interface, not the implementation.

If you use a []uint64 slice to store your data, then the zero slice could function as the empty BitSet. In fact appending to a nil slice allocates a new array for you, although the Language Specification doesn't appear to guarantee that. With that kind of setup, new(BitSet) would be immediately usable. Example:

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
}

The short answer is, you can't properly initialize the BitSet object when a client calls new().

The best thing you can do is make it so that your BitSet's zero value is valid. This is what types like list.List, sync.Mutex, and big.Int do. This way you know that it's impossible for a client to get an invalid value.

The next best thing you can do is create a constuctor-like function (named NewBitSet in this case) and expect clients to call it.

I've implemented my own too, and that's how It works:

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}

As others have answered, there's a convention to use New function to mimic the constructor.