README
¶
Your basic bit 
Set data structure for positive numbers
A bit array, or bit set, is an efficient set data structure. It consists of an array that compactly stores bits and it uses bit-level parallelism to perform operations quickly.
Installation
Once you have installed Go, run this command
to install the bit package:
go get github.com/yourbasic/bit
Documentation
There is an online reference for the package at godoc.org/github.com/yourbasic/bit.
Roadmap
- The API of this library is frozen.
- Version numbers adhere to semantic versioning.
The only accepted reason to modify the API of this package is to handle issues that can't be resolved in any other reasonable way.
Stefan Nilsson – korthaj
Documentation
¶
Overview ¶
Package bit provides a bit array implementation.
Bit set ¶
A bit set, or bit array, is an efficient set data structure that consists of an array of 64-bit words. Because it uses bit-level parallelism, limits memory access, and efficiently uses the data cache, a bit set often outperforms other data structures.
Tutorial ¶
The Basics example shows how to create, combine, compare and print bit sets.
Primes contains a short and simple, but still efficient, implementation of a prime number sieve.
Union is a more advanced example demonstrating how to build an efficient variadic Union function using the SetOr method.
Example (Basics) ¶
Create, combine, compare and print bit sets.
package main
import (
"fmt"
"github.com/yourbasic/bit"
)
func main() {
// Add all elements in the range [0, 100) to the empty set.
A := new(bit.Set).AddRange(0, 100) // {0..99}
// Create a new set containing the two elements 0 and 200,
// and then add all elements in the range [50, 150) to the set.
B := bit.New(0, 200).AddRange(50, 150) // {0 50..149 200}
// Compute the symmetric difference A △ B.
X := A.Xor(B)
// Compute A △ B as (A ∖ B) ∪ (B ∖ A).
Y := A.AndNot(B).Or(B.AndNot(A))
// Compare the results.
if X.Equal(Y) {
fmt.Println(X)
}
}
Output: {1..49 100..149 200}
Example (Primes) ¶
Create the set of all primes less than n in O(n log log n) time. Try the code with n equal to a few hundred millions and be pleasantly surprised.
package main
import (
"fmt"
"github.com/yourbasic/bit"
"math"
)
func main() {
// Sieve of Eratosthenes
const n = 50
sieve := bit.New().AddRange(2, n)
sqrtN := int(math.Sqrt(n))
for p := 2; p <= sqrtN; p = sieve.Next(p) {
for k := p * p; k < n; k += p {
sieve.Delete(k)
}
}
fmt.Println(sieve)
}
Output: {2 3 5 7 11 13 17 19 23 29 31 37 41 43 47}
Example (Union) ¶
Implement an efficient variadic Union function using SetOr.
package main
import (
"fmt"
"github.com/yourbasic/bit"
)
// Union returns the union of the given sets.
func Union(s ...*bit.Set) *bit.Set {
// Optimization: allocate initital set with adequate capacity.
max := -1
for _, x := range s {
if x.Size() > 0 && x.Max() > max { // Max is not defined for the empty set.
max = x.Max()
}
}
res := bit.New(max) // A negative number will not be included in the set.
for _, x := range s {
res.SetOr(res, x) // Reuses memory.
}
return res
}
// Implement an efficient variadic Union function using SetOr.
func main() {
a, b, c := bit.New(1, 2), bit.New(2, 3), bit.New(5)
fmt.Println(Union(a, b, c))
}
Output: {1..3 5}
Index ¶
- Constants
- func Count(w uint64) intdeprecated
- func LeadingZeros(w uint64) intdeprecated
- func TrailingZeros(w uint64) intdeprecated
- type Set
- func (s *Set) Add(n int) *Set
- func (s *Set) AddRange(m, n int) *Set
- func (s1 *Set) And(s2 *Set) *Set
- func (s1 *Set) AndNot(s2 *Set) *Set
- func (s *Set) Contains(n int) bool
- func (s *Set) Delete(n int) *Set
- func (s *Set) DeleteRange(m, n int) *Set
- func (s *Set) Empty() bool
- func (s1 *Set) Equal(s2 *Set) bool
- func (s *Set) Max() int
- func (s *Set) Next(m int) int
- func (s1 *Set) Or(s2 *Set) *Set
- func (s *Set) Prev(m int) int
- func (s *Set) Set(s1 *Set) *Set
- func (s *Set) SetAnd(s1, s2 *Set) *Set
- func (s *Set) SetAndNot(s1, s2 *Set) *Set
- func (s *Set) SetOr(s1, s2 *Set) *Set
- func (s *Set) SetXor(s1, s2 *Set) *Set
- func (s *Set) Size() int
- func (s *Set) String() string
- func (s1 *Set) Subset(s2 *Set) bool
- func (s *Set) Visit(do func(n int) (skip bool)) (aborted bool)
- func (s1 *Set) Xor(s2 *Set) *Set
Examples ¶
Constants ¶
const ( MaxInt = 1<<(BitsPerWord-1) - 1 // either 1<<31 - 1 or 1<<63 - 1 MinInt = -MaxInt - 1 // either -1 << 31 or -1 << 63 MaxUint = 1<<BitsPerWord - 1 // either 1<<32 - 1 or 1<<64 - 1 )
Implementation-specific integer limit values.
const BitsPerWord = bitsPerWord // either 32 or 64
BitsPerWord is the implementation-specific size of int and uint in bits.
Variables ¶
This section is empty.
Functions ¶
func LeadingZeros
deprecated
func TrailingZeros
deprecated
Types ¶
type Set ¶
type Set struct {
// contains filtered or unexported fields
}
Set represents a mutable set of non-negative integers. The zero value is an empty set ready to use. A set occupies approximately n bits, where n is the maximum value that has been stored in the set.
func New ¶
New creates a new set with the given elements. Negative numbers are not included in the set.
Example ¶
package main
import (
"fmt"
"github.com/yourbasic/bit"
)
func main() {
fmt.Println(bit.New(0, 1, 10, 10, -1))
}
Output: {0 1 10}
func (*Set) Add ¶
Add adds n to s and returns a pointer to the updated set. A negative n will not be added.
func (*Set) AddRange ¶
AddRange adds all integers from m to n-1 to s and returns a pointer to the updated set. Negative numbers will not be added.
func (*Set) And ¶
And creates a new set that consists of all elements that belong to both s1 and s2.
func (*Set) AndNot ¶
AndNot creates a new set that consists of all elements that belong to s1, but not to s2.
func (*Set) DeleteRange ¶
DeleteRange removes all integers from m to n-1 from s and returns a pointer to the updated set.
func (*Set) Next ¶
Next returns the next element n, n > m, in the set, or -1 if there is no such element.
func (*Set) Prev ¶
Prev returns the previous element n, n < m, in the set, or -1 if there is no such element.
func (*Set) SetAndNot ¶
SetAndNot sets s to the set difference s1 ∖ s2 and then returns a pointer to s.
func (*Set) SetXor ¶
SetXor sets s to the symmetric difference A ∆ B = (A ∪ B) ∖ (A ∩ B) and then returns a pointer to s.
func (*Set) Size ¶
Size returns the number of elements in the set. This method scans the set; to check if a set is empty, consider using the more efficient Empty method.
func (*Set) String ¶
String returns a string representation of the set. The elements are listed in ascending order. Runs of at least three consecutive elements from a to b are given as a..b.
Example ¶
package main
import (
"fmt"
"github.com/yourbasic/bit"
)
func main() {
fmt.Println(bit.New(1, 2, 6, 5, 3))
}
Output: {1..3 5 6}
func (*Set) Visit ¶
Visit calls the do function for each element of s in numerical order. If do returns true, Visit returns immediately, skipping any remaining elements, and returns true. It is safe for do to add or delete elements e, e ≤ n. The behavior of Visit is undefined if do changes the set in any other way.
Example ¶
Compute the sum of all elements in a set.
package main
import (
"fmt"
"github.com/yourbasic/bit"
)
func main() {
s := bit.New(1, 2, 3, 4)
sum := 0
s.Visit(func(n int) (skip bool) {
sum += n
return
})
fmt.Println("sum", s, "=", sum)
}
Output: sum {1..4} = 10
Example (Abort) ¶
Abort an iteration in mid-flight.
package main
import (
"fmt"
"github.com/yourbasic/bit"
)
func main() {
s := bit.New(2, 3, 5, 7, 11, 13)
// Print all single digit numbers in s.
s.Visit(func(n int) (skip bool) {
if n >= 10 {
skip = true
return
}
fmt.Print(n, " ")
return
})
}
Output: 2 3 5 7
Source Files