bit package - github.com/yourbasic/bit - Go Packages (original) (raw)

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.

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}

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}

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}

View Source

const ( MaxInt = 1<<(BitsPerWord-1) - 1 MinInt = -MaxInt - 1
MaxUint = 1<<BitsPerWord - 1
)

Implementation-specific integer limit values.

BitsPerWord is the implementation-specific size of int and uint in bits.

This section is empty.

Count returns the number of nonzero bits in w.

Deprecated: In Go 1.9 this function is available in package math/bits as OnesCount64.

LeadingZeros returns the number of leading zero bits in w; it returns 64 when w is zero.

Deprecated: In Go 1.9 this function is available in package math/bits as LeadingZeros64.

TrailingZeros returns the number of trailing zero bits in w; it returns 64 when w is zero.

Deprecated: In Go 1.9 this function is available in package math/bits as TrailingZeros64.

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.

New creates a new set with the given elements. Negative numbers are not included in the set.

package main

import ( "fmt" "github.com/yourbasic/bit" )

func main() { fmt.Println(bit.New(0, 1, 10, 10, -1)) }

Output:

{0 1 10}

func (s *Set) Add(n int) *Set

Add adds n to s and returns a pointer to the updated set. A negative n will not be added.

func (s *Set) AddRange(m, n int) *Set

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

func (s1 *Set) And(s2 *Set) *Set

And creates a new set that consists of all elements that belong to both s1 and s2.

func (*Set) AndNot

func (s1 *Set) AndNot(s2 *Set) *Set

AndNot creates a new set that consists of all elements that belong to s1, but not to s2.

Contains tells if n is an element of the set.

func (s *Set) Delete(n int) *Set

Delete removes n from s and returns a pointer to the updated set.

func (s *Set) DeleteRange(m, n int) *Set

DeleteRange removes all integers from m to n-1 from s and returns a pointer to the updated set.

func (s *Set) Empty() bool

Empty tells if the set is empty.

func (s1 *Set) Equal(s2 *Set) bool

Equal tells if s1 and s2 contain the same elements.

Max returns the maximum element of the set; it panics if the set is empty.

Next returns the next element n, n > m, in the set, or -1 if there is no such element.

func (s1 *Set) Or(s2 *Set) *Set

Or creates a new set that contains all elements that belong to either s1 or s2.

Prev returns the previous element n, n < m, in the set, or -1 if there is no such element.

func (s *Set) Set(s1 *Set) *Set

Set sets s to s1 and then returns a pointer to the updated set s.

func (*Set) SetAnd

func (s *Set) SetAnd(s1, s2 *Set) *Set

SetAnd sets s to the intersection s1 ∩ s2 and then returns a pointer to s.

func (*Set) SetAndNot

func (s *Set) SetAndNot(s1, s2 *Set) *Set

SetAndNot sets s to the set difference s1 ∖ s2 and then returns a pointer to s.

func (s *Set) SetOr(s1, s2 *Set) *Set

SetOr sets s to the union s1 ∪ s2 and then returns a pointer to s.

func (s *Set) SetXor(s1, s2 *Set) *Set

SetXor sets s to the symmetric difference A ∆ B = (A ∪ B) ∖ (A ∩ B) and then returns a pointer to s.

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.

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.

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 (s1 *Set) Subset(s2 *Set) bool

Subset tells if s1 is a subset of s2.

func (s *Set) Visit(do func(n int) (skip bool)) (aborted bool)

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.

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

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

func (s1 *Set) Xor(s2 *Set) *Set

Xor creates a new set that contains all elements that belong to either s1 or s2, but not to both.