本系列整理了10個工作量和難度適中的Golang小項目，適合已經(jīng)掌握Go語法的工程師進(jìn)一步熟練語法和常用庫的用法碴裙。
問題描述：
有一組非負(fù)整數(shù)钢悲，實(shí)現(xiàn)一個位向量類型，能在O(1)時間內(nèi)完成插入青团、刪除和查找等操作譬巫。
要點(diǎn)：
實(shí)現(xiàn)Has(uint)、Add(uint)督笆、Remove(uint)芦昔、Clear()、Copy()娃肿、String()咕缎、AddAll(…uint)、UnionWith()料扰、IntersectWith()凭豪、DifferenceWith()、SymmetricDifference()方法晒杈。
拓展：
使用uint存儲而不是uint32或uint64這樣限定字長的類型嫂伞。
代碼實(shí)現(xiàn)：
import (
? "bytes"
? "fmt"
)
func (s *IntSet)countBit(n uint)int{
? count := 0
? for n != 0{
? ? ? n = n & ( n - 1 )
? ? ? count += 1
? }
? return count
}
func (s *IntSet)calWordBit(x int)(word int, bit uint)? {
? word, bit = x / wordSize, uint(x%wordSize)
? return
}
const wordSize = 32 << (^uint(0) >> 63)
// An IntSet is a set of small non-negative integers.
// Its zero value represents the empty set.
type IntSet struct {
? words []uint
}
// Has reports whether the set contains the non-negative value x.
func (s *IntSet) Has(x int) bool {
? word, bit := s.calWordBit(x)
? 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 := s.calWordBit(x)
? for word >= len(s.words) {
? ? ? s.words = append(s.words, 0)
? }
? s.words[word] |= 1 << bit
}
func (s *IntSet) AddAll(nums ...int) {
? for _, n := range nums {
? ? ? s.Add(n)
? }
}
// 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)
? ? ? }
? }
}
// Set s to the intersection of s and t.
func (s *IntSet) IntersectWith(t *IntSet) {
? for i, tword := range t.words {
? ? ? if i < len(s.words) {
? ? ? ? s.words[i] &= tword
? ? ? } else {
? ? ? ? s.words = append(s.words, tword)
? ? ? }
? }
}
// Set s to the difference of s and t.
func (s *IntSet) DifferenceWith(t *IntSet) {
? for i, tword := range t.words {
? ? ? if i < len(s.words) {
? ? ? ? s.words[i] &^= tword
? ? ? } else {
? ? ? ? s.words = append(s.words, tword)
? ? ? }
? }
}
// Set s to the symmetric difference of s and t.
func (s *IntSet) SymmetricDifference(t *IntSet) {
? for i, tword := range t.words {
? ? ? if i < len(s.words) {
? ? ? ? s.words[i] ^= tword
? ? ? } else {
? ? ? ? s.words = append(s.words, tword)
? ? ? }
? }
}
// return the number of elements
func (s *IntSet) Len() int {
? count := 0
? for _, word := range s.words {
? ? ? count += s.countBit(word)
? }
? return count
}
// remove x from the set
func (s *IntSet) Remove(x int) {
? word, bit := s.calWordBit(x)
? s.words[word] &^= 1 << bit
}
// remove all elements from the set
func (s *IntSet) Clear() {
? for i := range s.words {
? ? ? s.words[i] = 0
? }
}
// return a copy of the set
func (s *IntSet) Copy() *IntSet {
? new := &IntSet{}
? new.words = make([]uint, len(s.words))
? copy(new.words, s.words)
? return new
}
// 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 < wordSize; j++ {
? ? ? ? if word&(1<<uint(j)) != 0 {
? ? ? ? ? ? if buf.Len() > len("{") {
? ? ? ? ? ? ? buf.WriteByte(' ')
? ? ? ? ? ? }
? ? ? ? ? ? fmt.Fprintf(&buf, "%d", wordSize*i+j)
? ? ? ? }
? ? ? }
? }
? buf.WriteByte('}')
? return buf.String()
}
// Return set elements.
func (s *IntSet) Elems() []int {
? e := make([]int, 0)
? for i, word := range s.words {
? ? ? for j := 0; j < wordSize; j++ {
? ? ? ? if word&(1<<uint(j)) != 0 {
? ? ? ? ? ? e = append(e, i*wordSize+j)
? ? ? ? }
? ? ? }
? }
? return e
}
