README

bitset

Go language library to map between non-negative integers and boolean values

Test Master Coverage Status Go Report Card PkgGoDev

Description

Package bitset implements bitsets, a mapping between non-negative integers and boolean values. It should be more efficient than map[uint] bool.

It provides methods for setting, clearing, flipping, and testing individual integers.

But it also provides set intersection, union, difference, complement, and symmetric operations, as well as tests to check whether any, all, or no bits are set, and querying a bitset's current length and number of positive bits.

BitSets are expanded to the size of the largest set bit; the memory allocation is approximately Max bits, where Max is the largest set bit. BitSets are never shrunk. On creation, a hint can be given for the number of bits that will be used.

Many of the methods, including Set, Clear, and Flip, return a BitSet pointer, which allows for chaining.

Example use:
package main

import (
	"fmt"
	"math/rand"

	"github.com/willf/bitset"
)

func main() {
	fmt.Printf("Hello from BitSet!\n")
	var b bitset.BitSet
	// play some Go Fish
	for i := 0; i < 100; i++ {
		card1 := uint(rand.Intn(52))
		card2 := uint(rand.Intn(52))
		b.Set(card1)
		if b.Test(card2) {
			fmt.Println("Go Fish!")
		}
		b.Clear(card1)
	}

	// Chaining
	b.Set(10).Set(11)

	for i, e := b.NextSet(0); e; i, e = b.NextSet(i + 1) {
		fmt.Println("The following bit is set:", i)
	}
	if b.Intersection(bitset.New(100).Set(10)).Count() == 1 {
		fmt.Println("Intersection works.")
	} else {
		fmt.Println("Intersection doesn't work???")
	}
}

As an alternative to BitSets, one should check out the 'big' package, which provides a (less set-theoretical) view of bitsets.

Package documentation is at: https://pkg.go.dev/github.com/willf/bitset?tab=doc

Memory Usage

The memory usage of a bitset using N bits is at least N/8 bytes. The number of bits in a bitset is at least as large as one plus the greatest bit index you have accessed. Thus it is possible to run out of memory while using a bitset. If you have lots of bits, you might prefer compressed bitsets, like the Roaring bitmaps and its Go implementation.

Implementation Note

Go 1.9 introduced a native math/bits library. We provide backward compatibility to Go 1.7, which might be removed.

It is possible that a later version will match the math/bits return signature for counts (which is int, rather than our library's unit64). If so, the version will be bumped.

Installation

go get github.com/willf/bitset

Contributing

If you wish to contribute to this project, please branch and issue a pull request against master ("GitHub Flow")

Running all tests

Before committing the code, please check if it passes tests, has adequate coverage, etc.

go test
go test -cover
Expand ▾ Collapse ▴

Documentation

Overview

    Package bitset implements bitsets, a mapping between non-negative integers and boolean values. It should be more efficient than map[uint] bool.

    It provides methods for setting, clearing, flipping, and testing individual integers.

    But it also provides set intersection, union, difference, complement, and symmetric operations, as well as tests to check whether any, all, or no bits are set, and querying a bitset's current length and number of positive bits.

    BitSets are expanded to the size of the largest set bit; the memory allocation is approximately Max bits, where Max is the largest set bit. BitSets are never shrunk. On creation, a hint can be given for the number of bits that will be used.

    Many of the methods, including Set,Clear, and Flip, return a BitSet pointer, which allows for chaining.

    Example use:

    import "bitset"
    var b BitSet
    b.Set(10).Set(11)
    if b.Test(1000) {
    	b.Clear(1000)
    }
    if B.Intersection(bitset.New(100).Set(10)).Count() > 1 {
    	fmt.Println("Intersection works.")
    }
    

    As an alternative to BitSets, one should check out the 'big' package, which provides a (less set-theoretical) view of bitsets.

    Index

    Examples

    Constants

    This section is empty.

    Variables

    This section is empty.

    Functions

    func Base64StdEncoding

    func Base64StdEncoding()

      Base64StdEncoding Marshal/Unmarshal BitSet with base64.StdEncoding(Default: base64.URLEncoding)

      func Cap

      func Cap() uint

        Cap returns the total possible capacity, or number of bits

        func LittleEndian

        func LittleEndian()

          LittleEndian Marshal/Unmarshal Binary as Little Endian(Default: binary.BigEndian)

          Types

          type BitSet

          type BitSet struct {
          	// contains filtered or unexported fields
          }

            A BitSet is a set of bits. The zero value of a BitSet is an empty set of length 0.

            func From

            func From(buf []uint64) *BitSet

              From is a constructor used to create a BitSet from an array of integers

              func New

              func New(length uint) (bset *BitSet)

                New creates a new BitSet with a hint that length bits will be required

                func (*BitSet) All

                func (b *BitSet) All() bool

                  All returns true if all bits are set, false otherwise. Returns true for empty sets.

                  func (*BitSet) Any

                  func (b *BitSet) Any() bool

                    Any returns true if any bit is set, false otherwise

                    func (*BitSet) BinaryStorageSize

                    func (b *BitSet) BinaryStorageSize() int

                      BinaryStorageSize returns the binary storage requirements

                      func (*BitSet) Bytes

                      func (b *BitSet) Bytes() []uint64

                        Bytes returns the bitset as array of integers

                        func (*BitSet) Clear

                        func (b *BitSet) Clear(i uint) *BitSet

                          Clear bit i to 0

                          func (*BitSet) ClearAll

                          func (b *BitSet) ClearAll() *BitSet

                            ClearAll clears the entire BitSet

                            func (*BitSet) Clone

                            func (b *BitSet) Clone() *BitSet

                              Clone this BitSet

                              func (*BitSet) Compact

                              func (b *BitSet) Compact() *BitSet

                                Compact shrinks BitSet to so that we preserve all set bits, while minimizing memory usage. Compact calls Shrink.

                                func (*BitSet) Complement

                                func (b *BitSet) Complement() (result *BitSet)

                                  Complement computes the (local) complement of a biset (up to length bits)

                                  func (*BitSet) Copy

                                  func (b *BitSet) Copy(c *BitSet) (count uint)

                                    Copy into a destination BitSet Returning the size of the destination BitSet like array copy

                                    func (*BitSet) Count

                                    func (b *BitSet) Count() uint

                                      Count (number of set bits). Also known as "popcount" or "popularity count".

                                      func (*BitSet) DeleteAt

                                      func (b *BitSet) DeleteAt(i uint) *BitSet

                                        DeleteAt deletes the bit at the given index position from within the bitset All the bits residing on the left of the deleted bit get shifted right by 1 The running time of this operation may potentially be relatively slow, O(length)

                                        func (*BitSet) Difference

                                        func (b *BitSet) Difference(compare *BitSet) (result *BitSet)

                                          Difference of base set and other set This is the BitSet equivalent of &^ (and not)

                                          func (*BitSet) DifferenceCardinality

                                          func (b *BitSet) DifferenceCardinality(compare *BitSet) uint

                                            DifferenceCardinality computes the cardinality of the differnce

                                            func (*BitSet) DumpAsBits

                                            func (b *BitSet) DumpAsBits() string

                                              DumpAsBits dumps a bit set as a string of bits

                                              func (*BitSet) Equal

                                              func (b *BitSet) Equal(c *BitSet) bool

                                                Equal tests the equivalence of two BitSets. False if they are of different sizes, otherwise true only if all the same bits are set

                                                func (*BitSet) Flip

                                                func (b *BitSet) Flip(i uint) *BitSet

                                                  Flip bit at i. If i>= Cap(), this function will panic. Warning: using a very large value for 'i' may lead to a memory shortage and a panic: the caller is responsible for providing sensible parameters in line with their memory capacity.

                                                  func (*BitSet) InPlaceDifference

                                                  func (b *BitSet) InPlaceDifference(compare *BitSet)

                                                    InPlaceDifference computes the difference of base set and other set This is the BitSet equivalent of &^ (and not)

                                                    func (*BitSet) InPlaceIntersection

                                                    func (b *BitSet) InPlaceIntersection(compare *BitSet)

                                                      InPlaceIntersection destructively computes the intersection of base set and the compare set. This is the BitSet equivalent of & (and)

                                                      func (*BitSet) InPlaceSymmetricDifference

                                                      func (b *BitSet) InPlaceSymmetricDifference(compare *BitSet)

                                                        InPlaceSymmetricDifference creates the destructive SymmetricDifference of base set and other set This is the BitSet equivalent of ^ (xor)

                                                        func (*BitSet) InPlaceUnion

                                                        func (b *BitSet) InPlaceUnion(compare *BitSet)

                                                          InPlaceUnion creates the destructive union of base set and compare set. This is the BitSet equivalent of | (or).

                                                          func (*BitSet) InsertAt

                                                          func (b *BitSet) InsertAt(idx uint) *BitSet

                                                            InsertAt takes an index which indicates where a bit should be inserted. Then it shifts all the bits in the set to the left by 1, starting from the given index position, and sets the index position to 0.

                                                            Depending on the size of your BitSet, and where you are inserting the new entry, this method could be extremely slow and in some cases might cause the entire BitSet to be recopied.

                                                            func (*BitSet) Intersection

                                                            func (b *BitSet) Intersection(compare *BitSet) (result *BitSet)

                                                              Intersection of base set and other set This is the BitSet equivalent of & (and)

                                                              func (*BitSet) IntersectionCardinality

                                                              func (b *BitSet) IntersectionCardinality(compare *BitSet) uint

                                                                IntersectionCardinality computes the cardinality of the union

                                                                func (*BitSet) IsStrictSuperSet

                                                                func (b *BitSet) IsStrictSuperSet(other *BitSet) bool

                                                                  IsStrictSuperSet returns true if this is a strict superset of the other set

                                                                  func (*BitSet) IsSuperSet

                                                                  func (b *BitSet) IsSuperSet(other *BitSet) bool

                                                                    IsSuperSet returns true if this is a superset of the other set

                                                                    func (*BitSet) Len

                                                                    func (b *BitSet) Len() uint

                                                                      Len returns the number of bits in the BitSet. Note the difference to method Count, see example.

                                                                      Example
                                                                      Output:
                                                                      
                                                                      len 9
                                                                      count 1
                                                                      

                                                                      func (*BitSet) MarshalBinary

                                                                      func (b *BitSet) MarshalBinary() ([]byte, error)

                                                                        MarshalBinary encodes a BitSet into a binary form and returns the result.

                                                                        func (*BitSet) MarshalJSON

                                                                        func (b *BitSet) MarshalJSON() ([]byte, error)

                                                                          MarshalJSON marshals a BitSet as a JSON structure

                                                                          func (*BitSet) NextClear

                                                                          func (b *BitSet) NextClear(i uint) (uint, bool)

                                                                            NextClear returns the next clear bit from the specified index, including possibly the current index along with an error code (true = valid, false = no bit found i.e. all bits are set)

                                                                            func (*BitSet) NextSet

                                                                            func (b *BitSet) NextSet(i uint) (uint, bool)

                                                                              NextSet returns the next bit set from the specified index, including possibly the current index along with an error code (true = valid, false = no set bit found) for i,e := v.NextSet(0); e; i,e = v.NextSet(i + 1) {...}

                                                                              Users concerned with performance may want to use NextSetMany to retrieve several values at once.

                                                                              func (*BitSet) NextSetMany

                                                                              func (b *BitSet) NextSetMany(i uint, buffer []uint) (uint, []uint)

                                                                                NextSetMany returns many next bit sets from the specified index, including possibly the current index and up to cap(buffer). If the returned slice has len zero, then no more set bits were found

                                                                                buffer := make([]uint, 256) // this should be reused
                                                                                j := uint(0)
                                                                                j, buffer = bitmap.NextSetMany(j, buffer)
                                                                                for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j,buffer) {
                                                                                 for k := range buffer {
                                                                                  do something with buffer[k]
                                                                                 }
                                                                                 j += 1
                                                                                }
                                                                                

                                                                                It is possible to retrieve all set bits as follow:

                                                                                indices := make([]uint, bitmap.Count())
                                                                                bitmap.NextSetMany(0, indices)
                                                                                

                                                                                However if bitmap.Count() is large, it might be preferable to use several calls to NextSetMany, for performance reasons.

                                                                                func (*BitSet) None

                                                                                func (b *BitSet) None() bool

                                                                                  None returns true if no bit is set, false otherwise. Returns true for empty sets.

                                                                                  func (*BitSet) ReadFrom

                                                                                  func (b *BitSet) ReadFrom(stream io.Reader) (int64, error)

                                                                                    ReadFrom reads a BitSet from a stream written using WriteTo

                                                                                    func (*BitSet) Set

                                                                                    func (b *BitSet) Set(i uint) *BitSet

                                                                                      Set bit i to 1, the capacity of the bitset is automatically increased accordingly. If i>= Cap(), this function will panic. Warning: using a very large value for 'i' may lead to a memory shortage and a panic: the caller is responsible for providing sensible parameters in line with their memory capacity.

                                                                                      func (*BitSet) SetTo

                                                                                      func (b *BitSet) SetTo(i uint, value bool) *BitSet

                                                                                        SetTo sets bit i to value. If i>= Cap(), this function will panic. Warning: using a very large value for 'i' may lead to a memory shortage and a panic: the caller is responsible for providing sensible parameters in line with their memory capacity.

                                                                                        func (*BitSet) Shrink

                                                                                        func (b *BitSet) Shrink(lastbitindex uint) *BitSet

                                                                                          Shrink shrinks BitSet so that the provided value is the last possible set value. It clears all bits > the provided index and reduces the size and length of the set.

                                                                                          Note that the parameter value is not the new length in bits: it is the maximal value that can be stored in the bitset after the function call. The new length in bits is the parameter value + 1. Thus it is not possible to use this function to set the length to 0, the minimal value of the length after this function call is 1.

                                                                                          A new slice is allocated to store the new bits, so you may see an increase in memory usage until the GC runs. Normally this should not be a problem, but if you have an extremely large BitSet its important to understand that the old BitSet will remain in memory until the GC frees it.

                                                                                          func (*BitSet) String

                                                                                          func (b *BitSet) String() string

                                                                                            String creates a string representation of the Bitmap

                                                                                            func (*BitSet) SymmetricDifference

                                                                                            func (b *BitSet) SymmetricDifference(compare *BitSet) (result *BitSet)

                                                                                              SymmetricDifference of base set and other set This is the BitSet equivalent of ^ (xor)

                                                                                              func (*BitSet) SymmetricDifferenceCardinality

                                                                                              func (b *BitSet) SymmetricDifferenceCardinality(compare *BitSet) uint

                                                                                                SymmetricDifferenceCardinality computes the cardinality of the symmetric difference

                                                                                                func (*BitSet) Test

                                                                                                func (b *BitSet) Test(i uint) bool

                                                                                                  Test whether bit i is set.

                                                                                                  func (*BitSet) Union

                                                                                                  func (b *BitSet) Union(compare *BitSet) (result *BitSet)

                                                                                                    Union of base set and other set This is the BitSet equivalent of | (or)

                                                                                                    func (*BitSet) UnionCardinality

                                                                                                    func (b *BitSet) UnionCardinality(compare *BitSet) uint

                                                                                                      UnionCardinality computes the cardinality of the uniton of the base set and the compare set.

                                                                                                      func (*BitSet) UnmarshalBinary

                                                                                                      func (b *BitSet) UnmarshalBinary(data []byte) error

                                                                                                        UnmarshalBinary decodes the binary form generated by MarshalBinary.

                                                                                                        func (*BitSet) UnmarshalJSON

                                                                                                        func (b *BitSet) UnmarshalJSON(data []byte) error

                                                                                                          UnmarshalJSON unmarshals a BitSet from JSON created using MarshalJSON

                                                                                                          func (*BitSet) WriteTo

                                                                                                          func (b *BitSet) WriteTo(stream io.Writer) (int64, error)

                                                                                                            WriteTo writes a BitSet to a stream

                                                                                                            type Error

                                                                                                            type Error string

                                                                                                              Error is used to distinguish errors (panics) generated in this package.