golang练手小项目系列(1)-位向量

本系列整理了10个工作量和难度适中的Golang小项目，适合已经掌握 Go 语法的工程师进一步熟练语法和常用库的用法。

问题描述：

有一组非负整数，实现一个位向量类型，能在O(1)时间内完成插入、删除和查找等操作。

要点：

• 实现Has(uint)、Add(uint)、Remove(uint)、Clear()、Copy()、String()、AddAll(…uint)、UnionWith()、IntersectWith()、DifferenceWith()、SymmetricDifference()方法。

拓展：

• 使用uint存储而不是uint32或uint64这样限定字长的类型。

代码实现：

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
}