bit

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}