bitset

BitSet instances are not safe for concurrent access from different goroutines because they are unsynchronized for performance.

To use a BitSet across multiple goroutines, you must provide your own synchronization. Recommended approaches include:

1. Using channels to pass the BitSet around so that only one goroutine owns it at a time.
2. Using a sync.Mutex to serialize operations on the BitSet.

A bitset's memory usage is at least N/8 bytes, where N is the number of bits. The bitset expands to the size of the largest set bit. Because bitsets are not automatically shrunk, they can consume significant memory if you access very high bit indices.

If you have a very sparse or large bitset, consider using Roaring Bitmaps (via the github.com/RoaringBitmap/roaring library). You can convert between bitset and roaring instances:

mybitset := roaringbitmap.ToBitSet()
newroaringbitmap := roaring.FromBitSet(mybitset)

You can safely and portably serialize a bitset to a stream of bytes using WriteTo and deserialize it using ReadFrom. ReadFrom attempts to read data into the existing instance to minimize memory allocations.

Performance Tip: Wrap your file or network streams with bufio (e.g., bufio.NewWriter or bufio.NewReader) for better performance.

Serialization Example

var buf bytes.Buffer
n, err := bs.WriteTo(&buf)
// n == buf.Len()

Deserialization Example

bs = bitset.New()
n, err = bs.ReadFrom(&buf)
// n is the number of bytes read

    const length = 9585
	const oneEvery = 97
	bs := bitset.New(length)
	// Add some bits
	for i := uint(0); i < length; i += oneEvery {
		bs = bs.Set(i)
	}

	var buf bytes.Buffer
	n, err := bs.WriteTo(&buf)
	if err != nil {
		// failure
	}

To add the bitset library to your Go project, use the following command:

go get github.com/bits-and-blooms/bitset

You can create a new BitSet using New(length uint) or MustNew(length uint).

• New(length): Creates a new BitSet with a hint for the number of bits required. If allocation fails, it returns an empty BitSet instead of panicking.
• MustNew(length): Creates a new BitSet with the given length. It will panic if the length exceeds the theoretical capacity or if there is a lack of memory.

BitSets are expanded automatically when setting bits, but providing a hint via New can improve efficiency by reducing reallocations.

import "github.com/bits-and-blooms/bitset"

// Recommended: use New with a size hint
var b bitset.BitSet
b.Set(10).Set(11)

if b.Test(1000) {
    b.Clear(1000)
}

// If you want to ensure a specific size and are okay with panics on failure
b2 := bitset.MustNew(100)

The package uses global settings for serialization. These affect how WriteTo and other encoding methods behave. Use these functions to configure the package globally:

• LittleEndian(): Sets the binary marshaling order to Little Endian (Default: binary.BigEndian).
• BigEndian(): Sets the binary marshaling order to Big Endian.
• BinaryOrder() binary.ByteOrder: Returns the current binary order.
• Base64StdEncoding(): Sets the JSON/Base64 encoding to base64.StdEncoding (Default: base64.URLEncoding).

OnesBetween(from, to uint) returns the number of set bits in the range [from, to).

• The range is inclusive of from.
• The range is exclusive of to.
• If from >= to, it returns 0.

BitSet supports JSON marshaling and unmarshaling. The BitSet is encoded as a Base64-encoded string of its binary representation.

• MarshalJSON(): Converts the BitSet to a JSON string.
• UnmarshalJSON(data []byte): Decodes a JSON string back into the BitSet.

This is useful for embedding bitsets in web APIs or configuration files.

Use these methods to inspect the contents of a BitSet:

• Test(i uint) bool: Returns true if bit i is set. Returns false if i is outside the current length.
• Count() uint: Returns the number of set bits (population count).
• Len() uint: Returns the current length (number of bits) of the BitSet.
• All() bool: Returns true if all bits up to Len() are set. Returns true for empty sets.
• Any() bool: Returns true if any bit is set.
• None() bool: Returns true if no bits are set.
• IsSuperSet(other *BitSet) bool: Returns true if this set contains all bits present in other.

BitSets expand automatically to accommodate the largest set bit, but they do not shrink automatically. To reclaim memory, use:

• Shrink(lastbitindex uint) *BitSet: Reduces the BitSet size so that lastbitindex is the maximum possible value that can be stored. The new length becomes lastbitindex + 1.
• Compact() *BitSet: Automatically shrinks the BitSet to the minimum size required to preserve all currently set bits.