[日常] Go语言圣经-指针对象的方法-bit数组习题

func (*IntSet) Len() int      // return the number of elements
func (*IntSet) Remove(x int)  // remove x from the set
func (*IntSet) Clear()        // remove all elements from the set
func (*IntSet) Copy() *IntSet // return a copy of the set

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
}