gopl 6.5 Bit数组 习题

inset.go

// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/

// See page 165.

// Package intset provides a set of integers based on a bit vector.
package intset

import (
	"bytes"
	"fmt"
)

func bitCount(n uint64) int {
	var c int
	for c=0; n!=0; c++ {
		n &= (n-1)
	}
	return c
}


//!+intset

// An IntSet is a set of small non-negative integers.
// Its zero value represents the empty set.
type IntSet struct {
	words []uint64
}

// Has reports whether the set contains the non-negative value x.
func (s *IntSet) Has(x int) bool {
	word, bit := x/64, uint(x%64)
	return word < len(s.words) && s.words[word]&(1<<bit) != 0
}

// Add adds the non-negative value x to the set.
func (s *IntSet) Add(x int) {
	word, bit := x/64, uint(x%64)
	for word >= len(s.words) {
		s.words = append(s.words, 0)
	}
	s.words[word] |= 1 << bit
}

// return the number count of Intset
func (s *IntSet) Len() int {
	var c int
	for _, tword := range s.words {
		c += bitCount(tword)
	}
	return c
}

// remove x from this IntSet.
func (s *IntSet) Remove(x int) {
	word, bit := x/64, uint(x%64)
	s.words[word] ^= 1 << bit
}

// remove all elements.
func (s *IntSet) Clear() {
	s.words = []uint64{}
}

// returns copy of this Intset.
func (s IntSet) Copy() IntSet {
	words := make([]uint64, len(s.words))
	copy(words, s.words)
	s.words = words
	return s
}

// adds the non-negative value x to the set.
func (s *IntSet) AddAll(vals...int) {
	for _, val := range vals {
		s.Add(val)
	}
}

// UnionWith sets s to the union of s and t.
func (s *IntSet) UnionWith(t *IntSet) {
	for i, tword := range t.words {
		if i < len(s.words) {
			s.words[i] |= tword
		} else {
			s.words = append(s.words, tword)
		}
	}
}

// IntersectWith sets s to the intersect of s and t.
func (s *IntSet) IntersectWith(t *IntSet) {
	for i, _ := range s.words {
		if i < len(t.words) {
			s.words[i] &= t.words[i]
		}else{
			s.words[i] = 0
		}
	}
}

// DifferenceWith sets s to the difference of s and t.
func (s *IntSet) DifferenceWith(t *IntSet) {
	for i, _ := range s.words {
		if i < len(t.words) {
			s.words[i] |= t.words[i]
			s.words[i] &^= t.words[i]
		}
	}
}

func (s *IntSet) SymmetricDifference(t *IntSet) {
	x := s.Copy()
	y := t.Copy()
	s.DifferenceWith(t)
	y.DifferenceWith(&x)
	s.UnionWith(&y)
}

func (s *IntSet) SymmetricDifference1(t *IntSet) {
	x := s.Copy()
	s.UnionWith(t)
	x.IntersectWith(t)
	s.DifferenceWith(&x)
}

//!-intset

//!+string

// String returns the set as a string of the form "{1, 2, 3}".
func (s IntSet) String() string {
	var buf bytes.Buffer
	buf.WriteByte('{')
	for i, word := range s.words {
		if word == 0 {
			continue
		}
		for j := 0; j < 64; j++ {
			if word&(1<<uint(j)) != 0 {
				if buf.Len() > len("{") {
					buf.WriteByte(',')
					buf.WriteByte(' ')
				}
				fmt.Fprintf(&buf, "%d", 64*i+j)
			}
		}
	}
	buf.WriteByte('}')
	return buf.String()
}
//!-string

func (s *IntSet) Elems() []int {
	var elems []int
	for i,word := range s.words {
		if word == 0 {
			continue
		}
		for j := 0; j < 64; j++ {
			if word&(1<<uint(j)) != 0 {
				elems = append(elems, 64*i+j)
			}
		}
	}
	return elems
}

inset_test.go

package intset

import "fmt"

func Example_one() {
    var x, y intset.IntSet

    x.AddAll(1,2,3,4,5,6,7,8,9,0)
    fmt.Println(x, x.Len())

    x.Remove(0)
    x.Remove(9)
    y = x.Copy()

    fmt.Println(x, x.Len())
    fmt.Println(y, y.Len())

    x.Clear()
    y.Clear()   

    x.AddAll(7,9,19,100,144,1024)
    y.AddAll(10,14,19,100,65536)
    fmt.Printf("x:%v\ny:%v\n",x ,y)
    fmt.Println(x.Elems())
}

func IntersectWith_test() {
    var x,y intset.IntSet
    x.AddAll(11,22,33,44,55,66,77,88,99)
    y.AddAll(77,88,99,111,222,333)
    x.IntersectWith(&y)
    fmt.Printf("x:%v\ny:%v\n",x ,y)     
}

func DifferenceWith_test() {
    var x,y intset.IntSet
    x.AddAll(11,22,33,44,55,66,77,88,99)
    y.AddAll(77,88,99,111,222,333)
    x.DifferenceWith(&y)
    fmt.Printf("x:%v\ny:%v\n",x ,y)    
}

func SymmetricDifference_test() {
    var x,y intset.IntSet
    x.AddAll(11,22,33,44,55,66,77,88,99)
    y.AddAll(77,88,99,111,222,333)
    x.SymmetricDifference(&y)
    // x.SymmetricDifference1(&y)
    fmt.Printf("x:%v\ny:%v\n",x ,y)
}