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

练习6.1:?为bit数组实现下面这些方法

<div class="cnblogs_Highlighter">
<pre class="brush:go;gutter:true;">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",64i+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,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,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
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!