bit

package module
Version: v0.0.0-...-45a4409 Latest Latest
Warning

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

Go to latest
Published: Mar 13, 2018 License: BSD-2-Clause Imports: 3 Imported by: 8

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

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 deprecated

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 deprecated

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 deprecated

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL