README

Your basic bit GoDoc

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.

Venn diagram

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 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"
	"math"

	"github.com/yourbasic/bit"
)

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

Examples

Constants

View Source
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.

View Source
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 Count

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

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

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.

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

func New(n ...int) *Set

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

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

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.

func (*Set) Contains

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

Contains tells if n is an element of the set.

func (*Set) Delete

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

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

func (*Set) DeleteRange

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

func (s *Set) Empty() bool

Empty tells if the set is empty.

func (*Set) Equal

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

Equal tells if s1 and s2 contain the same elements.

func (*Set) Max

func (s *Set) Max() int

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

func (*Set) Next

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

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

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

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

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

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

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

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.

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

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

Subset tells if s1 is a subset of s2.

func (*Set) Visit

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.

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

func (*Set) Xor

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.