bit

package module
v1.0.1 Latest Latest
Warning

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

 Go to latest Published: Apr 5, 2022 License: Apache-2.0 Imports: 2 Imported by: 11

README

bit

-- import "github.com/andybalholm/go-bit"

Package bit provides a bitset implementation and utility bit functions for uint64 words.

Usage

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

Implementation-specific size of int and uint in bits.

func Count
func Count(w uint64) int

Count returns the number of nonzero bits in w.

func MaxPos
func MaxPos(w uint64) int

MaxPos returns the position of the maximum nonzero bit in w, w ≠ 0. It panics for w = 0.

func MinPos
func MinPos(w uint64) int

MinPos returns the position of the minimum nonzero bit in w, w ≠ 0. It panics for w = 0.

type Set
type Set struct {
}

Set represents a mutable set of non-negative integers. The zero value of Set 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) (S *Set)

New creates a new set S with the given elements.

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

Add adds n to S, setting S to S ∪ {n}, and returns the updated set.

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

AddRange adds all integers between m and n-1, m ≤ n, setting S to S ∪ {m..n-1}, and returns the updated set.

func (*Set) And
func (A *Set) And(B *Set) (S *Set)

And creates a new intersection S = A ∩ B that consists of all elements that belong to both A and B.

func (*Set) AndNot
func (A *Set) AndNot(B *Set) (S *Set)

AndNot creates a new set difference S = A ∖ B that consists of all elements that belong to A, but not to B.

func (*Set) Clear
func (S *Set) Clear() *Set

Clear removes all elements and returns the updated empty set.

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

Contains returns true if n, n ≥ 0, is an element of S.

func (*Set) Do
func (S *Set) Do(f func(n int))

Do calls function f for each element n ∊ S in numerical order. It is safe for f to add or remove elements e, e ≤ n, from S. The behavior of Do is undefined if f changes the set in any other way.

func (*Set) Equals
func (A *Set) Equals(B *Set) bool

Equals returns true if A and B contain the same elements.

func (*Set) Flip
func (S *Set) Flip(n int) *Set

Flip removes n from S if it is present, otherwise it adds n, setting S to S ∆ {n}, and returns the updated set.

func (*Set) FlipRange
func (S *Set) FlipRange(m, n int) *Set

FlipRange flips all elements in the range m..n-1, m ≤ n, setting S to S ∆ {m..n-1}, and returns the updated set.

func (*Set) Intersects
func (A *Set) Intersects(B *Set) bool

Intersects returns true if A and B overlap, i.e. A ∩ B ≠ ∅.

func (*Set) IsEmpty
func (S *Set) IsEmpty() bool

IsEmpty returns true if S = ∅.

func (*Set) Max
func (S *Set) Max() int

Max returns the maximum element of the set. It panics if S is empty.

func (*Set) Min
func (S *Set) Min() int

Min returns the minimum element of the set. It panics if S is empty.

func (*Set) Next
func (S *Set) Next(m int) (n int, found bool)

Next returns (n, true), where n is the smallest element of S such that m < n, or (0, false) if no such element exists.

func (*Set) Or
func (A *Set) Or(B *Set) (S *Set)

Or creates a new union S = A ∪ B that contains all elements that belong to either A or B.

func (*Set) Previous
func (S *Set) Previous(m int) (n int, found bool)

Previous returns (n, true), where n is the largest element of S such that n < m, or (0, false) if no such element exists.

func (*Set) Remove
func (S *Set) Remove(n int) *Set

Remove removes n from S, setting S to S ∖ {n}, and returns the updated set.

func (*Set) RemoveMax
func (S *Set) RemoveMax() (max int)

RemoveMax removes the maximum element from S, setting S to S ∖ {max}, and returns max. It panics if S is empty.

func (*Set) RemoveMin
func (S *Set) RemoveMin() (min int)

RemoveMin removes the minimum element from S, setting S to S ∖ {min}, and returns min. It panics if S is empty.

func (*Set) RemoveRange
func (S *Set) RemoveRange(m, n int) *Set

RemoveRange removes all integers between m and n-1, m ≤ n, setting S to S ∖ {m..n-1}, and returns the updated set.

func (*Set) Set
func (S *Set) Set(A *Set) *Set

Set sets S to A and returns S.

func (*Set) SetAnd
func (S *Set) SetAnd(A, B *Set) *Set

SetAnd sets S to the intersection A ∩ B and returns S.

func (*Set) SetAndNot
func (S *Set) SetAndNot(A, B *Set) *Set

SetAndNot sets S to the set difference A ∖ B and returns S.

func (*Set) SetOr
func (S *Set) SetOr(A, B *Set) *Set

SetOr sets S to the union A ∪ B and returns S.

func (*Set) SetWord
func (S *Set) SetWord(i int, w uint64) *Set

SetWord interprets w as a bitset with numbers in the range 64i to 64i + 63, where 0 ≤ i ≤ ⌊MaxInt/64⌋, overwrites this range in S with w, and returns S.

func (*Set) SetXor
func (S *Set) SetXor(A, B *Set) *Set

SetXor sets S to the symmetric difference A ∆ B = (A ∪ B) ∖ (A ∩ B) and returns S.

func (*Set) Size
func (S *Set) Size() int

Size returns |S|, the number of elements in S. This method scans the set. To check if a set is empty, consider using the more efficient IsEmpty.

func (*Set) String
func (S *Set) String() string

String returns a string representation of S. The elements are listed in ascending order, enclosed by braces, and separated by ", ". Runs of at least three elements a, a+1, ..., b are given as "a..b".

For example, the set {1, 2, 6, 5, 3} is represented as "{1..3, 5, 6}".

func (*Set) SubsetOf
func (A *Set) SubsetOf(B *Set) bool

SubsetOf returns true if A ⊆ B.

func (*Set) Word
func (S *Set) Word(i int) (w uint64)

Word returns the range 64i to 64i + 63 of S as a bitset represented by w.

func (*Set) Xor
func (A *Set) Xor(B *Set) (S *Set)

Xor creates a new symmetric difference S = A ∆ B = (A ∪ B) ∖ (A ∩ B) that consists of all elements that belong to either A or B, but not to both.

Documentation

Overview

Package bit provides a bitset implementation and utility bit functions for uint64 words.

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

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.

func MaxPos 

func MaxPos(w uint64) int

MaxPos returns the position of the maximum nonzero bit in w, w ≠ 0. It panics for w = 0.

Example (Allocation) 
package main

import (
	"fmt"
	bit "github.com/andybalholm/go-bit"
)

func main() {
	// Compute suitable allocation size (using MaxPos and MaxInt)
	// favoring powers of two and guaranteeing linear amortized cost
	// for a repeated number of allocations.
	newSize := func(want, had int) int {
		if n := NextPowerOfTwo(had); n > want {
			return n
		}
		return want
	}

	say := func(h, w, g int) {
		fmt.Printf("Had %#x, wanted %#x, got %#x.\n", h, w, g)
	}

	had := 0xff0
	want := had + 0x008       // shy of next power of two
	got := newSize(want, had) // got == NextPowerOfTwo(had)
	say(had, want, got)

	had = got
	want = had + 0x2000      // overshooting next power of two
	got = newSize(want, had) // got == want
	say(had, want, got)

	had = got
	want = had + 0x1000      // hitting next power of two
	got = newSize(want, had) // got == want
	say(had, want, got)

}

// NextPowerOfTwo returns the smallest p = 1, 2, 4, ..., 1<<k
// such that p > n, or MaxInt if p > MaxInt.
func NextPowerOfTwo(n int) (p int) {
	if n <= 0 {
		return 1
	}

	if k := bit.MaxPos(uint64(n)) + 1; k < bit.BitsPerWord-1 {
		return 1 << uint(k)
	}
	return bit.MaxInt
}

Output:

Had 0xff0, wanted 0xff8, got 0x1000.
Had 0x1000, wanted 0x3000, got 0x3000.
Had 0x3000, wanted 0x4000, got 0x4000.

func MinPos 

func MinPos(w uint64) int

MinPos returns the position of the minimum nonzero bit in w, w ≠ 0. It panics for w = 0.

Types

type Set 

type Set struct {
	// contains filtered or unexported fields
}

Set represents a mutable set of non-negative integers. The zero value of Set 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.

Example (Eratosthenes)

Create the set of all primes ≤ max using Sieve of Eratosthenes. 

package main

import (
	"fmt"
	bit "github.com/andybalholm/go-bit"
)

func main() {
	const max = 50
	sieve := bit.New().AddRange(2, max)
	for p, found := 2, true; found; p, found = sieve.Next(p) {
		for n := 2 * p; n <= max; n += p {
			sieve.Remove(n)
		}
	}
	fmt.Println(sieve)
}

Output:

{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}
Example (Memory) 
package main

import (
	"fmt"
	bit "github.com/andybalholm/go-bit"
	"math/rand"
)

func main() {
	// Memory management
	S := bit.New(100, 100000) // Make a set that occupies a few kilobyes.
	S.RemoveMax()             // The big element is gone. Memory remains.
	S = bit.New().Set(S)      // Give excess capacity to garbage collector.

	// Memory hints and memory reuse
	IntegerRuns(10, 5)

	// Example output:
	//
	//      Max     Size     Runs
	//       10        9        2    {0..2, 4..9}
	//       20       18        2    {0, 1, 3..11, 13..19}
	//       30       24        4    {0..3, 6..8, 10..13, 15..27}
	//       40       32        5
	//       50       44        5
}

// IntegerRuns(s, n) generates random sets R(i), i = 1, 2, ..., n,
// with elements drawn from 0..i*s-1 and computes the number of runs
// in each set. A run is a sequence of at least three integers
// a, a+1, ..., b, such that {a..b} ⊆ S and {a-1, b+1} ∩ S = ∅.
func IntegerRuns(start, n int) {
	// Give a capacity hint.
	R := bit.New(n*start - 1).Clear()

	fmt.Printf("\n%8s %8s %8s\n", "Max", "Size", "Runs")
	for i := 1; i <= n; i++ {
		// Reuse memory from last iteration.
		R.Clear()

		// Create a random set with ~86% population.
		max := i * start
		for j := 2 * max; j > 0; j-- {
			R.Add(rand.Intn(max))
		}

		// Compute the number of runs.
		runs, length, prev := 0, 0, -2
		R.Do(func(i int) {
			if i == prev+1 { // Continue run.
				length++
			} else { // Start a new run.
				if length >= 3 {
					runs++
				}
				length = 1
			}
			prev = i
		})
		if length >= 3 {
			runs++
		}
		fmt.Printf("%8d %8d %8d", max, R.Size(), runs)
		if max <= 32 {
			fmt.Printf("%4s%v", "", R)
		}
		fmt.Println()
	}
	fmt.Println()
}

Output:
Example (Operators) 
package main

import (
	"fmt"
	bit "github.com/andybalholm/go-bit"
)

func main() {
	A := new(bit.Set).AddRange(0, 100)     // A = {0..99}
	B := bit.New(0, 200).AddRange(50, 150) // B = {0, 50..149, 200}
	S := A.Xor(B)                          // S = A ∆ B
	C := A.Or(B).AndNot(A.And(B))          // C = (A ∪ B) ∖ (A ∩ B)
	D := A.AndNot(B).Or(B.AndNot(A))       // D = (A ∖ B) ∪ (B ∖ A)

	if C.Equals(S) && D.Equals(S) {
		fmt.Printf("A ∆ B = %v\n", S)
	}
}

Output:

A ∆ B = {1..49, 100..149, 200}
Example (Union) 
package main

import (
	"fmt"
	bit "github.com/andybalholm/go-bit"
)

// Variadic Union function efficiently implemented with SetOr.
func Union(A ...*bit.Set) *bit.Set {
	// Optimization: Allocate empty set with adequate capacity.
	max := 0
	for _, X := range A {
		if e := X.Max(); e > max {
			max = e
		}
	}
	S := bit.New(max).Clear()

	for _, X := range A {
		S.SetOr(S, X)
	}
	return S
}

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}
Example (Words) 
package main

import (
	"fmt"
	bit "github.com/andybalholm/go-bit"
)

func main() {
	const faraway = 46                         // billion light years
	Universe := bit.New().AddRange(0, faraway) // Universe = {0..faraway-1}
	Even := bit.New().SetWord(0, 1<<faraway/3) // Even = {0, 2, 4, ..., faraway-2}

	Odd := Universe.AndNot(Even)
	fmt.Printf("Odd = %v\n", Odd)

	Even.FlipRange(0, faraway)
	fmt.Printf("Even = %v\n", Even)
}

Output:

Odd = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45}
Even = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45}

func New 

func New(n ...int) (S *Set)

New creates a new set S with the given elements.

func (*Set) Add 

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

Add adds n to S, setting S to S ∪ {n}, and returns the updated set.

func (*Set) AddRange 

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

AddRange adds all integers between m and n-1, m ≤ n, setting S to S ∪ {m..n-1}, and returns the updated set.

func (*Set) And 

func (A *Set) And(B *Set) (S *Set)

And creates a new intersection S = A ∩ B that consists of all elements that belong to both A and B.

func (*Set) AndNot 

func (A *Set) AndNot(B *Set) (S *Set)

AndNot creates a new set difference S = A ∖ B that consists of all elements that belong to A, but not to B.

func (*Set) Clear 

func (S *Set) Clear() *Set

Clear removes all elements and returns the updated empty set.

func (*Set) Contains 

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

Contains returns true if n, n ≥ 0, is an element of S.

func (*Set) Do 

func (S *Set) Do(f func(n int))

Do calls function f for each element n ∊ S in numerical order. It is safe for f to add or remove elements e, e ≤ n, from S. The behavior of Do is undefined if f changes the set in any other way.

Example 
package main

import (
	"fmt"
	bit "github.com/andybalholm/go-bit"
)

func main() {
	A := bit.New(1, 2, 3, 4)
	sum := 0
	A.Do(func(n int) {
		sum += n
	})
	fmt.Printf("sum %v = %d\n", A, sum)
}

Output:

sum {1..4} = 10

func (*Set) Equals 

func (A *Set) Equals(B *Set) bool

Equals returns true if A and B contain the same elements.

func (*Set) Flip 

func (S *Set) Flip(n int) *Set

Flip removes n from S if it is present, otherwise it adds n, setting S to S ∆ {n}, and returns the updated set.

func (*Set) FlipRange 

func (S *Set) FlipRange(m, n int) *Set

FlipRange flips all elements in the range m..n-1, m ≤ n, setting S to S ∆ {m..n-1}, and returns the updated set.

func (*Set) Intersects 

func (A *Set) Intersects(B *Set) bool

Intersects returns true if A and B overlap, i.e. A ∩ B ≠ ∅.

func (*Set) IsEmpty 

func (S *Set) IsEmpty() bool

IsEmpty returns true if S = ∅.

func (*Set) Max 

func (S *Set) Max() int

Max returns the maximum element of the set. It panics if S is empty.

func (*Set) Min 

func (S *Set) Min() int

Min returns the minimum element of the set. It panics if S is empty.

func (*Set) Next 

func (S *Set) Next(m int) (n int, found bool)

Next returns (n, true), where n is the smallest element of S such that m < n, or (0, false) if no such element exists.

Example 
package main

import (
	"fmt"
	bit "github.com/andybalholm/go-bit"
)

func main() {
	A := bit.New(2, 3, 5, 7, 11, 13)

	// Print all single digit numbers in A.
	for n, found := A.Next(-1); found && n < 10; n, found = A.Next(n) {
		fmt.Printf("%d ", n)
	}
}

Output:

2 3 5 7

func (*Set) Or 

func (A *Set) Or(B *Set) (S *Set)

Or creates a new union S = A ∪ B that contains all elements that belong to either A or B.

func (*Set) Previous 

func (S *Set) Previous(m int) (n int, found bool)

Previous returns (n, true), where n is the largest element of S such that n < m, or (0, false) if no such element exists.

Example 
package main

import (
	"fmt"
	bit "github.com/andybalholm/go-bit"
)

func main() {
	A := bit.New(2, 3, 5, 7)

	// Print all numbers in A in reverse order.
	if !A.IsEmpty() {
		for n, found := A.Max(), true; found; n, found = A.Previous(n) {
			fmt.Printf("%d ", n)
		}
	}
}

Output:

7 5 3 2

func (*Set) Remove 

func (S *Set) Remove(n int) *Set

Remove removes n from S, setting S to S ∖ {n}, and returns the updated set.

func (*Set) RemoveMax 

func (S *Set) RemoveMax() (max int)

RemoveMax removes the maximum element from S, setting S to S ∖ {max}, and returns max. It panics if S is empty.

func (*Set) RemoveMin 

func (S *Set) RemoveMin() (min int)

RemoveMin removes the minimum element from S, setting S to S ∖ {min}, and returns min. It panics if S is empty.

func (*Set) RemoveRange 

func (S *Set) RemoveRange(m, n int) *Set

RemoveRange removes all integers between m and n-1, m ≤ n, setting S to S ∖ {m..n-1}, and returns the updated set.

func (*Set) Set 

func (S *Set) Set(A *Set) *Set

Set sets S to A and returns S.

func (*Set) SetAnd 

func (S *Set) SetAnd(A, B *Set) *Set

SetAnd sets S to the intersection A ∩ B and returns S.

func (*Set) SetAndNot 

func (S *Set) SetAndNot(A, B *Set) *Set

SetAndNot sets S to the set difference A ∖ B and returns S.

func (*Set) SetOr 

func (S *Set) SetOr(A, B *Set) *Set

SetOr sets S to the union A ∪ B and returns S.

func (*Set) SetWord 

func (S *Set) SetWord(i int, w uint64) *Set

SetWord interprets w as a bitset with numbers in the range 64i to 64i + 63, where 0 ≤ i ≤ ⌊MaxInt/64⌋, overwrites this range in S with w, and returns S.

func (*Set) SetXor 

func (S *Set) SetXor(A, B *Set) *Set

SetXor sets S to the symmetric difference A ∆ B = (A ∪ B) ∖ (A ∩ B) and returns S.

func (*Set) Size 

func (S *Set) Size() int

Size returns |S|, the number of elements in S. This method scans the set. To check if a set is empty, consider using the more efficient IsEmpty.

func (*Set) String 

func (S *Set) String() string

String returns a string representation of S. The elements are listed in ascending order, enclosed by braces, and separated by ", ". Runs of at least three elements a, a+1, ..., b are given as "a..b".

For example, the set {1, 2, 6, 5, 3} is represented as "{1..3, 5, 6}".

func (*Set) SubsetOf 

func (A *Set) SubsetOf(B *Set) bool

SubsetOf returns true if A ⊆ B.

func (*Set) Word 

func (S *Set) Word(i int) (w uint64)

Word returns the range 64i to 64i + 63 of S as a bitset represented by w.

func (*Set) Xor 

func (A *Set) Xor(B *Set) (S *Set)

Xor creates a new symmetric difference S = A ∆ B = (A ∪ B) ∖ (A ∩ B) that consists of all elements that belong to either A or B, but not to both.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.