Go语言圣经-指针对象的方法-bit数组习题详解编程语言

package main 
 
import ( 
        "bytes" 
        "fmt" 
) 
 
func main() { 
 
        var x, y IntSet 
        x.Add(1) 
        x.Add(144) 
        x.Add(9) 
        fmt.Println(x.String()) // "{1 9 144}" 
 
        y.Add(9) 
        y.Add(42) 
        fmt.Println(y.String()) // "{9 42}" 
 
        x.UnionWith(&y) 
        fmt.Println(x.String()) // "{1 9 42 144}" 
        fmt.Println(x.Len())    // 返回4 
        //x.Remove(9)         //"{1 42 144}" 
        z := x.Copy() 
        x.Clear() 
        fmt.Println(x.String()) //返回{} 
        fmt.Println(z.String()) //"{1 9 42 144}" 
 
        fmt.Println(x.Has(9), x.Has(123)) // "true false" 
} 
 
// 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 
} 
 
// 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) 
                }    
        }    
} 
 
// 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(' ') 
                                } 
                                fmt.Fprintf(&buf, "%d", 64*i+j) 
                        } 
                } 
        } 
        buf.WriteByte('}') 
        return buf.String() 
} 
 
/* 
练习6.1: 为bit数组实现下面这些方法 
*/ 
func (s *IntSet) Len() int { 
        sum := 0 
        for _, word := range s.words { 
                for j := 0; j < 64; j++ { 
                        if word&(1<<uint(j)) != 0 { 
                                sum++ 
                        } 
                } 
        } 
        return sum 
} 
 
//往集合中添加元素 
//1. 或|；两个值其中之一为1，结果为1 
//2. 1 << bit 1左移到指定位 
//3. a |= b ==> a= a|b  最终实现设置指定位为1 
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 
} 
 
//删除集合中的元素 
//1.异或^ ：两个值相同，结果为0；两个值不同结果为1； 
//2.与&：两个值都是1，结果为1；其他结果为0 
//3. s.words[word] ^ (1 << bit) 把我指定位的1改成了0 
//4. a &= b  ==>  a=a&b  最终实现设置指定位为0 
func (s *IntSet) Remove(x int) { 
        word, bit := x/64, uint(x%64) 
        s.words[word] &= s.words[word] ^ (1 << bit) 
} 
 
//清空集合 
//1. 设置每个位都为0 
//2. 使用异或,把位是1的改成0 
func (s *IntSet) Clear() { 
        for i, word := range s.words { 
                for j := 0; j < 64; j++ { 
                        if word&(1<<uint(j)) != 0 { 
                                s.words[i] ^= 1 << uint(j) 
                        } 
                } 
        } 
} 
 
//copy一个set 
//编译器判断变量的生命期会超出作用域后，自动在堆上分配 
func (s *IntSet) Copy() (r *IntSet) { 
        var result IntSet 
        for _, word := range s.words { 
                result.words = append(result.words, word) 
        } 
        return &result 
}