本系列整理了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
}
