欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-05 11:47:20
练习6.1: 为bit数组实现下面这些方法 ......

练习6.1: 为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
}