bitset

package
v1.20.7 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 31, 2025 License: MIT Imports: 10 Imported by: 0

Documentation

Overview

Package bitset provides a thread-safe, efficient bit set implementation with comprehensive bit manipulation operations.

The package offers a BitSet type that stores bits efficiently using byte slices, supporting operations like setting/getting bits, bitwise operations (AND, OR, XOR, ANDNOT, NOT), counting set bits, range operations, and conversion to various string formats.

Features

  • Thread-safe: All operations are protected by read-write mutexes
  • Efficient storage: Uses byte slices for compact bit representation
  • Negative indexing: Supports negative offsets (e.g., -1 for last bit)
  • Auto-growing: Automatically expands when setting bits beyond current size
  • Iterator integration: Implements iterator.BitSetLike interface for use with gust iterators

Basic Usage 

// Create a new bit set
bs := bitset.New()
bs.Set(0, true).Unwrap()  // Set first bit
bs.Set(5, true).Unwrap()   // Set 6th bit

// Get bit values
if bs.Get(0) {
	fmt.Println("First bit is set")
}

// Count set bits
count := bs.Count(0, -1)  // Count all bits

// Convert to hex string
fmt.Println(bs.String())  // Output: "21" (binary: 00100001)

Iterator Integration

The BitSet implements iterator.BitSetLike interface, allowing seamless integration with gust iterators: 

import "github.com/andeya/gust/iterator"

bs := bitset.New()
bs.Set(0, true).Unwrap()
bs.Set(2, true).Unwrap()

// Iterate over all bits
iterator.FromBitSet(bs).ForEach(func(p pair.Pair[int, bool]) {
	fmt.Printf("Bit %d: %v\n", p.A, p.B)
})

// Get only set bits
setBits := iterator.FromBitSetOnes(bs).Collect()
fmt.Println(setBits)  // Output: [0 2]

Bitwise Operations 

bs1 := bitset.NewFromString("c0", bitset.EncodingHex).Unwrap()  // 11000000
bs2 := bitset.NewFromString("30", bitset.EncodingHex).Unwrap()  // 00110000

and := bs1.And(bs2)   // 00000000
or := bs1.Or(bs2)     // 11110000
xor := bs1.Xor(bs2)   // 11110000
not := bs1.Not()      // 00111111

Examples

See the examples package for more detailed usage examples.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func NewFromBase64URL 

func NewFromBase64URL(base64URLStr string) result.Result[*BitSet]

NewFromBase64URL creates a BitSet from a Base64URL encoded string. This is a convenience function for NewFromString(str, EncodingBase64URL). Base64URL is the default encoding format used by String() method.

Examples 

bs := bitset.NewFromBase64URL("wCA=").Unwrap()
// Creates a bit set with bytes: [0xc0, 0x20]

// Round-trip: encode and decode
original := bitset.New(0xFF, 0x00)
encoded := original.String()  // Base64URL encoding
decoded := bitset.NewFromBase64URL(encoded).Unwrap()
// decoded equals original

func NewFromString 

func NewFromString(encodedStr string, format EncodingFormat) result.Result[*BitSet]

NewFromString creates a BitSet from an encoded string using the specified format. Returns an error if the string is invalid for the given format.

Examples 

// From hex string
bs := bitset.NewFromString("c020", bitset.EncodingHex).Unwrap()

// From base64url string (recommended for modern applications)
bs := bitset.NewFromString("wCA", bitset.EncodingBase64URL).Unwrap()

// From base62 string
bs := bitset.NewFromString("lTn7eSlSalC", bitset.EncodingBase62).Unwrap()

Types

type BitSet 

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

BitSet represents a thread-safe bit set that stores bits efficiently using byte slices. Bits are stored with the most significant bit (MSB) first within each byte.

The BitSet implements iterator.BitSetLike interface, making it compatible with gust iterator functions like FromBitSet, FromBitSetOnes, and FromBitSetZeros.

Example 
package main

import (
	"fmt"

	"github.com/andeya/gust/bitset"
)

func main() {
	bs := bitset.NewFromString("c020", bitset.EncodingHex).Unwrap()
	fmt.Println("Origin:", bs.Binary(" "))
	not := bs.Not()
	fmt.Println("Not:", not.Binary(" "))
	fmt.Println("AndNot:", not.AndNot(bitset.New(1, 1)).Binary(" "))
	fmt.Println("And:", not.And(bitset.New(1<<1, 1<<1)).Binary(" "))
	fmt.Println("Or:", not.Or(bitset.New(1<<7, 1<<7)).Binary(" "))
	fmt.Println("Xor:", not.Xor(bitset.New(1<<7, 1<<7)).Binary(" "))

	not.Range(func(k int, v bool) bool {
		fmt.Println(v)
		return true
	})

}

Output:

Origin: 11000000 00100000
Not: 00111111 11011111
AndNot: 00111110 11011110
And: 00000010 00000010
Or: 10111111 11011111
Xor: 10111111 01011111
false
false
true
true
true
true
true
true
true
true
false
true
true
true
true
true

func New 

func New(initialBytes ...byte) *BitSet

New creates a new BitSet with optional initial bytes. If no bytes are provided, creates an empty bit set.

Examples 

// Empty bit set
bs := bitset.New()

// Bit set with initial bytes
bs := bitset.New(0xFF, 0x00, 0xAA)

func (*BitSet) And 

func (b *BitSet) And(others ...*BitSet) *BitSet

And returns a new BitSet that is the bitwise AND of this bit set and the provided bit sets. If no bit sets are provided, returns a copy of this bit set. The original bit set is not modified.

Examples 

bs1 := bitset.NewFromString("c0", bitset.EncodingHex).Unwrap()  // 11000000
bs2 := bitset.NewFromString("30", bitset.EncodingHex).Unwrap()  // 00110000
and := bs1.And(bs2)                      // 00000000

func (*BitSet) AndNot 

func (b *BitSet) AndNot(others ...*BitSet) *BitSet

AndNot returns a new BitSet that is the bitwise AND NOT (bit clear) of this bit set and the provided bit sets. If no bit sets are provided, returns a copy of this bit set. The original bit set is not modified.

Examples 

bs1 := bitset.NewFromString("c0", bitset.EncodingHex).Unwrap()  // 11000000
bs2 := bitset.NewFromString("30", bitset.EncodingHex).Unwrap()  // 00110000
andNot := bs1.AndNot(bs2)                // 11000000 (bits in bs2 are cleared)

func (*BitSet) Binary 

func (b *BitSet) Binary(sep string) string

Binary returns a binary string representation of the bit set. The sep parameter specifies the separator between bytes.

Examples 

bs := bitset.NewFromString("c020", bitset.EncodingHex).Unwrap()
fmt.Println(bs.Binary(" "))  // Output: "11000000 00100000"

func (*BitSet) Bytes 

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

Bytes returns a copy of the underlying byte slice. Modifying the returned slice does not affect the bit set.

Examples 

bs := bitset.New()
bs.Set(0, true).Unwrap()
bytes := bs.Bytes()
fmt.Printf("%x\n", bytes)  // Output: "01"

func (*BitSet) Clear 

func (b *BitSet) Clear()

Clear sets all bits in the bit set to 0. The size of the bit set remains unchanged.

Examples 

bs := bitset.New()
bs.Set(0, true).Unwrap()
bs.Set(5, true).Unwrap()
bs.Clear()
// All bits are now 0

func (*BitSet) Clone 

func (b *BitSet) Clone() *BitSet

Clone returns a deep copy of the bit set.

func (*BitSet) Count 

func (b *BitSet) Count(start, end int) int

Count returns the number of bits set to 1 within the specified range [start, end]. Both start and end are inclusive and support negative indexing.

Examples 

bs := bitset.New()
bs.Set(0, true).Unwrap()
bs.Set(2, true).Unwrap()
bs.Set(5, true).Unwrap()

count := bs.Count(0, -1)  // Count all bits: 3
count := bs.Count(0, 3)   // Count bits 0-3: 2

func (*BitSet) Encode 

func (b *BitSet) Encode(format EncodingFormat) string

Encode returns a string representation of the bit set using the specified encoding format.

Encoding Formats

  • EncodingHex: Hexadecimal (base16), compression ratio 2.00
  • EncodingBase64: Standard Base64, compression ratio ~1.33
  • EncodingBase64URL: URL-safe Base64 (recommended), compression ratio ~1.33
  • EncodingBase62: Base62 encoding, compression ratio ~1.38-1.50

Examples 

bs := bitset.NewFromString("c020", bitset.EncodingHex).Unwrap()
fmt.Println(bs.Encode(bitset.EncodingHex))        // "c020"
fmt.Println(bs.Encode(bitset.EncodingBase64URL))  // "wCA"
fmt.Println(bs.Encode(bitset.EncodingBase62))     // "gYU"

func (*BitSet) Get 

func (b *BitSet) Get(offset int) bool

Get returns the value of the bit at the specified offset. Returns false if the offset is out of range.

Offset semantics:

  • Positive offsets: 0 = first bit, 1 = second bit, etc.
  • Negative offsets: -1 = last bit, -2 = second-to-last bit, etc.

Examples 

bs := bitset.New()
bs.Set(5, true).Unwrap()
if bs.Get(5) {
	fmt.Println("Bit 5 is set")
}

// Get last bit using negative index
lastBit := bs.Get(-1)

func (*BitSet) Not 

func (b *BitSet) Not() *BitSet

Not returns a new BitSet that is the bitwise NOT of this bit set. The original bit set is not modified.

Examples 

bs := bitset.NewFromHex("c0").Unwrap()  // 11000000
not := bs.Not()                          // 00111111

func (*BitSet) Or 

func (b *BitSet) Or(others ...*BitSet) *BitSet

Or returns a new BitSet that is the bitwise OR of this bit set and the provided bit sets. If no bit sets are provided, returns a copy of this bit set. The original bit set is not modified.

Examples 

bs1 := bitset.NewFromString("c0", bitset.EncodingHex).Unwrap()  // 11000000
bs2 := bitset.NewFromString("30", bitset.EncodingHex).Unwrap()  // 00110000
or := bs1.Or(bs2)                        // 11110000

func (*BitSet) Range 

func (b *BitSet) Range(f func(offset int, value bool) bool)

Range calls the function f sequentially for each bit in the bit set. If f returns false, Range stops the iteration.

The function receives the bit offset and its value (true if set, false if unset).

Examples 

bs := bitset.New()
bs.Set(0, true).Unwrap()
bs.Set(2, true).Unwrap()

bs.Range(func(offset int, value bool) bool {
	if value {
		fmt.Printf("Bit %d is set\n", offset)
	}
	return true  // Continue iteration
})

func (*BitSet) Set 

func (b *BitSet) Set(offset int, value bool) result.Result[bool]

Set sets the bit at the specified offset to the given value. Returns the previous value of the bit and any error encountered.

Offset semantics:

  • Positive offsets: 0 = first bit, 1 = second bit, etc.
  • Negative offsets: -1 = last bit, -2 = second-to-last bit, etc.
  • Out of range: If offset is beyond current size, the bit set automatically grows

Examples 

bs := bitset.New()
oldValue, err := bs.Set(0, true).Unwrap()
// oldValue = false (bit was unset), err = nil

// Set last bit using negative index
bs.Set(-1, true).Unwrap()

func (*BitSet) Size 

func (b *BitSet) Size() int

Size returns the total number of bits in the bit set. The size is always a multiple of 8 (aligned to byte boundaries).

Examples 

bs := bitset.New()
bs.Set(15, true).Unwrap()
fmt.Println(bs.Size())  // Output: 16 (2 bytes * 8 bits)

func (*BitSet) String 

func (b *BitSet) String() string

String returns a string representation of the bit set using Base64URL encoding (default). Implements fmt.Stringer interface.

Base64URL is chosen as the default because it provides:

  • Best compression ratio (~1.33 for aligned data)
  • URL-safe characters (no need for URL encoding)
  • Standard library support (no external dependencies)

For other encoding formats, use Encode() method.

Examples 

bs := bitset.New()
bs.Set(0, true).Unwrap()
fmt.Println(bs.String())  // Output: "AQ==" (Base64URL)

func (*BitSet) Sub 

func (b *BitSet) Sub(start, end int) *BitSet

Sub returns a new BitSet containing bits from the specified range [start, end]. Both start and end are inclusive and support negative indexing. The original bit set is not modified.

The extracted bits are packed into the result bit set, starting from offset 0.

Examples 

bs := bitset.New()
bs.Set(5, true).Unwrap()
bs.Set(10, true).Unwrap()
bs.Set(15, true).Unwrap()

sub := bs.Sub(5, 15)  // Extract bits 5-15

func (*BitSet) Xor 

func (b *BitSet) Xor(others ...*BitSet) *BitSet

Xor returns a new BitSet that is the bitwise XOR of this bit set and the provided bit sets. If no bit sets are provided, returns a copy of this bit set. The original bit set is not modified.

Examples 

bs1 := bitset.NewFromString("c0", bitset.EncodingHex).Unwrap()  // 11000000
bs2 := bitset.NewFromString("30", bitset.EncodingHex).Unwrap()  // 00110000
xor := bs1.Xor(bs2)                      // 11110000

type EncodingFormat 

type EncodingFormat int

EncodingFormat represents the encoding format for string representation of BitSet. 

const (
	// EncodingHex represents hexadecimal encoding (base16).
	// Compression ratio: 2.00 (2 characters per byte).
	// Best for: Human readability, debugging, backward compatibility.
	EncodingHex EncodingFormat = iota

	// EncodingBase64 represents standard Base64 encoding.
	// Compression ratio: ~1.33 for 3-byte aligned data (best theoretical ratio).
	// Best for: General purpose encoding, standard compatibility.
	// Note: Uses '+' and '/' characters, may need URL encoding.
	EncodingBase64

	// EncodingBase64URL represents URL-safe Base64 encoding (RFC 4648).
	// Compression ratio: ~1.33 for 3-byte aligned data (best theoretical ratio).
	// Best for: URL embedding, API responses, modern applications (recommended default).
	// Note: Uses '-' and '_' instead of '+' and '/', no padding '='.
	EncodingBase64URL

	// EncodingBase62 represents base62 encoding (0-9, a-z, A-Z).
	// Compression ratio: ~1.38-1.50 for large byte arrays.
	// Best for: Maximum compression without special characters, URL-friendly.
	//
	// Implementation uses math/big.Int.Text(62) instead of digit.FormatUint(62):
	//
	//	Feature              big.Int.Text(62)        digit.FormatUint(62)
	//	Value Range          Unlimited               Limited to uint64
	//	Byte Array           Direct (SetBytes)       Must convert to uint64 (may overflow)
	//	Performance          General algorithm       Fast path for small integers
	//	Interface            Independent             Compatible with strconv
	//	Append               Not supported           Supported (zero-copy)
	//
	// IMPORTANT: Size Limitations
	//   - digit.FormatUint(62) only supports uint64 range (0 to 18,446,744,073,709,551,615)
	//   - For byte arrays larger than 8 bytes, converting to uint64 will cause overflow
	//   - big.Int.Text(62) has no size limit and can handle arbitrarily large byte arrays
	//
	// This implementation chooses big.Int because:
	//   - BitSet byte arrays can be arbitrarily large (not limited to uint64)
	//   - big.Int.SetBytes() directly handles byte slices without conversion
	//   - Avoids potential overflow when converting large byte arrays to uint64
	EncodingBase62
)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.