bit: github.com/yourbasic/bit Index | Examples | Files

package bit

import "github.com/yourbasic/bit"

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.

Code:

// 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.

Code:

// 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.

Code:

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))
}

Index

Examples

Package Files

funcs.go set_1_10.go

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.

func Count Uses

func Count(w uint64) int

Count returns the number of nonzero bits in w.

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

func LeadingZeros Uses

func LeadingZeros(w uint64) int

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.

func TrailingZeros Uses

func TrailingZeros(w uint64) int

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.

type Set Uses

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 Uses

func New(n ...int) *Set

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

Code:

fmt.Println(bit.New(0, 1, 10, 10, -1))

Output:

{0 1 10}

func (*Set) Add Uses

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 (*Set) AddRange Uses

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 Uses

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 Uses

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.

func (*Set) Contains Uses

func (s *Set) Contains(n int) bool

Contains tells if n is an element of the set.

func (*Set) Delete Uses

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

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

func (*Set) DeleteRange Uses

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 (*Set) Empty Uses

func (s *Set) Empty() bool

Empty tells if the set is empty.

func (*Set) Equal Uses

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

Equal tells if s1 and s2 contain the same elements.

func (*Set) Max Uses

func (s *Set) Max() int

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

func (*Set) Next Uses

func (s *Set) Next(m int) int

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

func (*Set) Or Uses

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

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

func (*Set) Prev Uses

func (s *Set) Prev(m int) int

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

func (*Set) Set Uses

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 Uses

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 Uses

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 (*Set) SetOr Uses

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

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

func (*Set) SetXor Uses

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.

func (*Set) Size Uses

func (s *Set) Size() int

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 Uses

func (s *Set) String() 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.

Code:

fmt.Println(bit.New(1, 2, 6, 5, 3))

Output:

{1..3 5 6}

func (*Set) Subset Uses

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

Subset tells if s1 is a subset of s2.

func (*Set) Visit Uses

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.

Code:

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.

Code:

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 (*Set) Xor Uses

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.

Package bit imports 3 packages (graph). Updated 2018-07-27. Refresh now. Tools for package owners.