ch6/ch6-05 #134

2022-10-17T06:57:23Z

giscus[bot]
bot Oct 17, 2022

ch6/ch6-05

中文版

https://golang-china.github.io/gopl-zh/ch6/ch6-05.html

qbmiller · 2022-10-17T06:57:25Z

qbmiller
Oct 17, 2022 — with giscus

指针这学了点新知识...

0 replies

dugulingping · 2022-12-13T10:45:14Z

dugulingping
Dec 13, 2022 — with giscus

练习6.1

// Len returns the number of elements.
func (s *IntSet) Len() (l int) {
	//遍历s.words
	for _, word := range s.words {
		// 判断是否为空切片
		if word == 0 {
			// 为空则跳过
			continue
		}
		// 不为空则遍历word
		for j := 0; j < 64; j++ {
			// 判断word的第j位是否为1
			// 如果为1, 则代表这个位置存在数字
			if word&(1<<uint(j)) != 0 {
				// 为1则l++
				l++
			}
		}
	}
	// 返回l
	return l
}
// Remove removes x from the set.
func (s *IntSet) Remove(x int) {
	// 取得x的word和bit
	word, bit := x/64, uint(x%64)
	// 判断word是否越界
	if word < len(s.words) {
		// 如果没有越界, 则将word的第bit位置为0
		s.words[word] &= ^(1 << bit)
	}
}
// Clear removes all elements from the set.
func (s *IntSet) Clear() {
	// 将s.words置为nil
	s.words = nil
}
// Copy returns a copy of the set.
func (s *IntSet) Copy() *IntSet {
	// 创建一个新的IntSet
	var newIntSet IntSet
	// 将s.words赋值给new.words
	newIntSet.words = append(newIntSet.words, s.words...)
	// 返回newIntSet
	return &newIntSet
}

0 replies

dugulingping · 2022-12-13T11:03:21Z

dugulingping
Dec 13, 2022 — with giscus

练习6.2

func (s *IntSet) AddAll(nums ...int) {
	for _, num := range nums {
		s.Add(num)
	}
}

0 replies

dugulingping · 2022-12-13T11:38:43Z

dugulingping
Dec 13, 2022 — with giscus

练习6.3

// IntersectWith computes the intersection of s and t.
// 这个不解释了=_=|
func (s *IntSet) IntersectWith(t *IntSet) {
	// 遍历s.words
	for i, word := range s.words {
		// 判断i是否越界
		if i >= len(t.words) {
			// 如果越界, 则将word置为0
			// 越界代表t中没有这个word, 与任何数都是0, 所以将s中的word置为0
			s.words[i] = 0
		} else {
			// 如果没有越界, 则将s.words[i]和t.words[i]进行与运算
			// 与运算的结果就是s和t的交集
			s.words[i] = word & t.words[i]
		}
	}
}

// DifferenceWith computes the difference of s and t.
// s集扣掉s与t的交集就是s与t的差集
func (s *IntSet) DifferenceWith(t *IntSet) {
	// 遍历s.words
	for i, word := range s.words {
		// 判断i是否越界
		if i >= len(t.words) {
			// 如果越界, 则跳过
			continue
		}
		// 如果没有越界, 则将s.words[i]和t.words[i]进行异或运算
		// 异或运算的结果就是s和t的差集
		s.words[i] = word ^ t.words[i]
	}
}

// SymmetricDifference computes the symmetric difference of s and t.
// s和t的并集扣掉他们的交集就是差并集(对称差集)
func (s *IntSet) SymmetricDifference(t *IntSet) {
	// 创建一个空的IntSet
	var u IntSet
	// 将s和t的并集赋值给u, 相当于u里面有s和t的所有元素
	u.UnionWith(s)
	u.UnionWith(t)
	// 将s和t的交集赋值给s, 相当于s中只有s和t中共同都有的元素了, 这也就是交集
	s.IntersectWith(t)
	// 将u和s的差集赋值给u, 相当于u扣掉了s和t的交集
	u.DifferenceWith(s)
	// 将u赋值给s
	*s = u
}

0 replies

dugulingping · 2022-12-13T11:42:03Z

dugulingping
Dec 13, 2022 — with giscus

练习6.4

// Elems returns a slice containing the elements of the set.
// Elems 返回一个包含集合中所有元素的切片。
func (s *IntSet) Elems() (elems []int) {
	// 创建一个空的切片
	//var elems []int
	// 遍历s.words
	for i, word := range s.words {
		// 判断word是否为空
		if word == 0 {
			// 如果为空, 则跳过
			continue
		}
		// 遍历word
		for j := 0; j < PlatformCompatible; j++ {
			// 判断word的第j位是否为1
			if word&(1<<uint(j)) != 0 {
				// 如果为1, 则将PlatformCompatible*i+j添加到elems中
				elems = append(elems, PlatformCompatible*i+j)
			}
		}
	}
	// 返回elems
	return elems
}

1 reply

dugulingping Dec 13, 2022 — with giscus

不知道PlatformCompatible是什么的请看练习6.5

dugulingping · 2022-12-13T11:48:01Z

dugulingping
Dec 13, 2022 — with giscus

练习6.5

唉😮‍💨,常量本应该是全部大写的,但是我忘记了😓

type IntSet struct {
	// 将words从uint64切片改为uint切片，以适应32位和64位平台
	words []uint
}

const (
	// PlatformCompatible 用于适应32位和64位平台
	PlatformCompatible = 32 << (^uint(0) >> 63)
	
	// 将代码中所有的64改为PlatformCompatible, 就完成了适配
)
// 展示一下效果

func (s *IntSet) Has(x int) bool {
	word, bit := x/PlatformCompatible, uint(x%PlatformCompatible)
	fmt.Println("word, bit: ", word, bit)
	return word < len(s.words) && s.words[word]&(1<<bit) != 0
}

func (s *IntSet) Add(x int) {
	word, bit := x/PlatformCompatible, uint(x%PlatformCompatible)
	for word >= len(s.words) {
		s.words = append(s.words, 0)
	}
	s.words[word] |= 1 << bit
}

0 replies

zhangbest5 · 2023-01-13T01:13:05Z

zhangbest5
Jan 13, 2023 — with giscus

一脸懵逼

0 replies

Fu-LianPeng · 2023-01-19T12:21:35Z

Fu-LianPeng
Jan 19, 2023 — with giscus

package main

import (
"bytes"
"fmt"
)

const PLATFORM_ARCH = 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
/在 Go 语言中也实现了随着平台位数变化而
变化的数据类型uint。一般来说，这个类型
在32位的系统中长度和uint32一致，在64位的系统中长度和uint64一致。/
}

// Has reports whether the set contains the non-negative value x.
func (s *IntSet) Has(x int) bool {
word, bit := x/PLATFORM_ARCH, uint(x%PLATFORM_ARCH)
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 := x/PLATFORM_ARCH, uint(x%PLATFORM_ARCH)
for word >= len(s.words) {
s.words = append(s.words, 0)
}
s.words[word] |= 1 << bit
}

func (s *IntSet) AddAll(x ...int) {
for _, e := range x {
s.Add(e)
}
}

// 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)
}
}
}
func (s *IntSet) IntersectWith(t *IntSet) {
for i := 0; i < len(t.words) && i < len(s.words); i++ {
s.words[i] = t.words[i] & s.words[i]
}
if len(s.words) > len(t.words) {
s.words = s.words[:len(t.words)]
}
}
func (s *IntSet) DifferenceWith(t *IntSet) {
for i := 0; i < len(s.words) && i < len(t.words); i++ {
s.words[i] = s.words[i] &^ t.words[i]
}
}
func (s *IntSet) SymmetricDifference(t *IntSet) {
var u IntSet
u.UnionWith(s)
u.UnionWith(t) //u有全部s和t
s.IntersectWith(t) //取交集

u.DifferenceWith(s)
*s = u

}

// 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 < PLATFORM_ARCH; j++ {
if word&(1<<uint(j)) != 0 {
if buf.Len() > len("{") {
buf.WriteByte(' ')
}
fmt.Fprintf(&buf, "%d", PLATFORM_ARCH*i+j)
}
}
}
buf.WriteByte('}')
return buf.String()
}

func (s *IntSet) Len() int { // return the number of elements
res := 0
for _, e := range s.words {
for e > 0 {
res++
e &= (e - 1)
}
}
return res
}
func (s *IntSet) Remove(x int) { // remove x from the set
word, bit := x/PLATFORM_ARCH, uint(x%PLATFORM_ARCH)
bit = ^bit
s.words[word] &= bit
}
func (s *IntSet) Clear() { // remove all elements from the set
s.words = nil
}
func (s *IntSet) Copy() *IntSet { // return a copy of the set
res := new(IntSet)
res.words = make([]uint, len(s.words))
copy(res.words, s.words)
return res
}
func (s IntSet) Elems() (res []int) {
for i, e := range s.words {
if e != 0 {
for j := 0; j < PLATFORM_ARCH; j++ {
if e&(1<<j) != 0 {
res = append(res, iPLATFORM_ARCH+j)
}
}
}
}
return res
}
func main() {
var a IntSet = IntSet{nil}
a.AddAll(1, 3, 5, 19, 79)

b := new(IntSet)
b.AddAll(3, 5, 7, 9)

a.SymmetricDifference(b)
fmt.Println(a)

}

0 replies

Fu-LianPeng · 2023-01-19T12:22:13Z

Fu-LianPeng
Jan 19, 2023 — with giscus

package main

import (
	"bytes"
	"fmt"
)

const PLATFORM_ARCH = 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
	/*在 Go 语言中也实现了随着平台位数变化而
	变化的数据类型uint。一般来说，这个类型
	在32位的系统中长度和uint32一致，在64位的系统中长度和uint64一致。*/
}

// Has reports whether the set contains the non-negative value x.
func (s *IntSet) Has(x int) bool {
	word, bit := x/PLATFORM_ARCH, uint(x%PLATFORM_ARCH)
	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 := x/PLATFORM_ARCH, uint(x%PLATFORM_ARCH)
	for word >= len(s.words) {
		s.words = append(s.words, 0)
	}
	s.words[word] |= 1 << bit
}

func (s *IntSet) AddAll(x ...int) {
	for _, e := range x {
		s.Add(e)
	}
}

// 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)
		}
	}
}
func (s *IntSet) IntersectWith(t *IntSet) {
	for i := 0; i < len(t.words) && i < len(s.words); i++ {
		s.words[i] = t.words[i] & s.words[i]
	}
	if len(s.words) > len(t.words) {
		s.words = s.words[:len(t.words)]
	}
}
func (s *IntSet) DifferenceWith(t *IntSet) {
	for i := 0; i < len(s.words) && i < len(t.words); i++ {
		s.words[i] = s.words[i] &^ t.words[i]
	}
}
func (s *IntSet) SymmetricDifference(t *IntSet) {
	var u IntSet
	u.UnionWith(s)
	u.UnionWith(t)     //u有全部s和t
	s.IntersectWith(t) //取交集

	u.DifferenceWith(s)
	*s = u
}

// 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 < PLATFORM_ARCH; j++ {
			if word&(1<<uint(j)) != 0 {
				if buf.Len() > len("{") {
					buf.WriteByte(' ')
				}
				fmt.Fprintf(&buf, "%d", PLATFORM_ARCH*i+j)
			}
		}
	}
	buf.WriteByte('}')
	return buf.String()
}

func (s *IntSet) Len() int { // return the number of elements
	res := 0
	for _, e := range s.words {
		for e > 0 {
			res++
			e &= (e - 1)
		}
	}
	return res
}
func (s *IntSet) Remove(x int) { // remove x from the set
	word, bit := x/PLATFORM_ARCH, uint(x%PLATFORM_ARCH)
	bit = ^bit
	s.words[word] &= bit
}
func (s *IntSet) Clear() { // remove all elements from the set
	s.words = nil
}
func (s *IntSet) Copy() *IntSet { // return a copy of the set
	res := new(IntSet)
	res.words = make([]uint, len(s.words))
	copy(res.words, s.words)
	return res
}
func (s *IntSet) Elems() (res []int) {
	for i, e := range s.words {
		if e != 0 {
			for j := 0; j < PLATFORM_ARCH; j++ {
				if e&(1<<j) != 0 {
					res = append(res, i*PLATFORM_ARCH+j)
				}
			}
		}
	}
	return res
}
func main() {
	var a IntSet = IntSet{nil}
	a.AddAll(1, 3, 5, 19, 79)

	b := new(IntSet)
	b.AddAll(3, 5, 7, 9)

	a.SymmetricDifference(b)
	fmt.Println(a)
	
}

0 replies

xubai2001 · 2024-01-10T14:11:03Z

xubai2001
Jan 10, 2024 — with giscus

练习6.1

// return the number of elements
func (s *IntSet) Len() int {
	count := 0
	for _, word := range s.words {
		if word == 0 {
			continue
		}
		for word > 0 {
			word = word & (word - 1)
			count++
		}
	}
	return count
}

// remove x from the set
func (s *IntSet) Remove(x int) {
	word, bit := x/64, uint(x%64)
	if word < len(s.words) {
		num := ^(uint64(1) << bit)
		s.words[word] &= num
	}
}

// remove all elements from the set
func (s *IntSet) Clear() {
	s.words = nil
}

// return a copy of the set
func (s *IntSet) Copy() *IntSet {
	var copys IntSet
	copys.words = append(copys.words, s.words...)
	return &copys
}

0 replies

xubai2001 · 2024-01-10T14:43:38Z

xubai2001
Jan 10, 2024 — with giscus

练习6.2 & 6.3

func (s *IntSet) AddAll(nums ...int) {
	for _, num := range nums {
		s.Add(num)
	}
}

func (s *IntSet) IntersectWith(t *IntSet) {
	for i, tword := range t.words {
		if i >= len(s.words) {
			break
		}
		s.words[i] &= tword
	}
}

func (s *IntSet) DifferenceWith(t *IntSet) {
	for i, tword := range t.words {
		if i >= len(s.words) {
			break
		}
		s.words[i] &= s.words[i] ^ tword
	}
}

func (s *IntSet) SymmetricDifference(t *IntSet) {
	for i, tword := range t.words {
		if i >= len(s.words) {
			break
		}
		s.words[i] ^= tword
	}
}

0 replies

jiajialinli · 2024-02-29T05:10:27Z

jiajialinli
Feb 29, 2024 — with giscus

如果 x 是65，那么 word 是1，bit 是1，表示整数65在 words[1] 中的第2个比特位上，帮助理解。

0 replies

hongjiala · 2025-04-08T02:23:12Z

hongjiala
Apr 8, 2025 — with giscus

func (s *IntSet)AddAll(x ...int) {
	for _, v := range x {
		s.Add(v)
	}
	
}

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 reply

hongjiala Apr 8, 2025 — with giscus

6.2

hongjiala · 2025-04-08T03:16:02Z

hongjiala
Apr 8, 2025 — with giscus

// 练习6.1: 为bit数组实现下面这些方法
// 方法1：func (*IntSet) Len() int      // return the number of elements
func (s *IntSet) Len() int {
	count := 0
	for _, word := range s.words {
		for i := 0; i < 64; i++ {
			if word&(1<<i) != 0 {
				count++
			}
		}
	}
	return count
}

// 方法2：func (*IntSet) Remove(x int)  // remove x from the set
func (s *IntSet) Remove(x int) {
	word, bit := x/64, uint(x%64)
	if word < len(s.words) {
		s.words[word] &^= 1 << bit
	}
}
// 方法3：func (*IntSet) Clear()  // remove all elements from the set
func (s *IntSet) Clear() {
	s.words = nil
}
// 方法4：func (*IntSet) Copy() *IntSet  // return a copy of the set
func (s *IntSet) Copy() *IntSet {
	newSet := &IntSet{}
	newSet.words = make([]uint64, len(s.words))
	copy(newSet.words, s.words)
	return newSet
}

0 replies

hongjiala · 2025-04-08T09:03:25Z

hongjiala
Apr 8, 2025 — with giscus

//练习 6.3： (*IntSet).UnionWith会用|操作符计算两个集合的并集，我们再为IntSet实现另外的几个函数IntersectWith（交集：元素在A集合B集合均出现），DifferenceWith（差集：元素出现在A集合，未出现在B集合），SymmetricDifference（并差集：元素出现在A但没有出现在B，或者出现在B没有出现在A）。
func (s *IntSet) IntersectWith(t *IntSet) {
	for i := 0; i < len(s.words); i++ {
		s.words[i] &= t.words[i]
	}
}

func (s *IntSet) DifferenceWith(t *IntSet) {
	for i := 0; i < len(s.words); i++ {
		s.words[i] &= ^t.words[i]
	}
}

func (s *IntSet) SymmetricDifference(t *IntSet) {
	for i := 0; i < len(s.words); i++ {
		s.words[i] = (s.words[i] | t.words[i]) & (^s.words[i] | ^t.words[i])
	}
}

0 replies

hongjiala · 2025-04-08T10:47:31Z

hongjiala
Apr 8, 2025 — with giscus

// 练习 6.4： 实现一个Elems方法，返回集合中的所有元素，用于做一些range之类的遍历操作。
func (s *IntSet) Elems() []int {
	elems := []int{}
	for i, word := range s.words {
		for j := 0; j < 64; j++ {
			if word&(1<<j) != 0 {
				elems = append(elems, i*64+j)
			}
		}
	}
	return elems
}

0 replies

hongjiala · 2025-04-08T10:52:15Z

hongjiala
Apr 8, 2025 — with giscus

 //练习 6.5： 我们这章定义的IntSet里的每个字都是用的uint64类型，但是64位的数值可能在32位的平台上不高效。
 // 修改程序，使其使用uint类型，这种类型对于32位平台来说更合适。当然了，这里我们可以不用简单粗暴地除64，可以定义一个常量来决定是用32还是64，这里你可能会用到平台的自动判断的一个智能表达式：32 << (^uint(0) >> 63)
type IntSet2 struct {
	words []uint

}
const (
	p = 32 << (^uint(0) >> 63) // 32 or 64
)
func (s *IntSet2) Add(x int) {
	word, bit := x/p, uint(x%p)
	for word >= len(s.words) {
		s.words = append(s.words, 0)
	}
	s.words[word] |= 1 << bit
}

0 replies

w2807 · 2025-04-29T14:33:52Z

w2807
Apr 29, 2025 — with giscus

6.1和6.2

func (s *IntSet) Len() int {
	res := 0
	for _, word := range s.words {
		if word == 0 {
			continue
		}
		for j := range 64 {
			if word&(1<<uint(j)) != 0 {
				res++
			}
		}
	}
	return res
}

func (s *IntSet) Remove(x int) {
	for i, word := range s.words {
		if word == 0 {
			continue
		}
		j := x - i*64
		if j < 0 || j > 63 {
			continue
		} else {
			s.words[i] &= ^(1 << uint(j))
		}
	}
}

func (s *IntSet) Clear() {
	for i := range s.words {
		s.words[i] = 0
	}
}

func (s *IntSet) Copy() *IntSet {
	res := &IntSet{}
	for _, word := range s.words {
		res.words = append(res.words, word)
	}
	return res
}

func (s *IntSet) AddAll(x ...int) {
	for _, i := range x {
		s.Add(i)
	}
}

0 replies

w2807 · 2025-04-29T14:41:38Z

w2807
Apr 29, 2025 — with giscus

6.4

func (s *IntSet) Elems() []uint64 {
	res := make([]uint64, 0)
	for i, word := range s.words {
		if word == 0 {
			continue
		}
		for j := 0; j < 64; j++ {
			if word&(1<<uint(j)) != 0 {
				res = append(res, uint64(64*i+j))
			}
		}
	}
	return res
}

0 replies

ch6/ch6-05 #134

Uh oh!

giscus[bot] bot Oct 17, 2022

ch6/ch6-05

Replies: 19 comments · 2 replies

Uh oh!

qbmiller Oct 17, 2022 — with giscus

Uh oh!

dugulingping Dec 13, 2022 — with giscus

练习6.1

Uh oh!

dugulingping Dec 13, 2022 — with giscus

练习6.2

Uh oh!

dugulingping Dec 13, 2022 — with giscus

练习6.3

Uh oh!

dugulingping Dec 13, 2022 — with giscus

练习6.4

Uh oh!

dugulingping Dec 13, 2022 — with giscus

Uh oh!

dugulingping Dec 13, 2022 — with giscus

练习6.5

Uh oh!

zhangbest5 Jan 13, 2023 — with giscus

Uh oh!

Fu-LianPeng Jan 19, 2023 — with giscus

Uh oh!

Fu-LianPeng Jan 19, 2023 — with giscus

Uh oh!

xubai2001 Jan 10, 2024 — with giscus

练习6.1

Uh oh!

xubai2001 Jan 10, 2024 — with giscus

练习6.2 & 6.3

Uh oh!

jiajialinli Feb 29, 2024 — with giscus

Uh oh!

hongjiala Apr 8, 2025 — with giscus

Uh oh!

hongjiala Apr 8, 2025 — with giscus

Uh oh!

hongjiala Apr 8, 2025 — with giscus

Uh oh!

hongjiala Apr 8, 2025 — with giscus

Uh oh!

hongjiala Apr 8, 2025 — with giscus

Uh oh!

hongjiala Apr 8, 2025 — with giscus

Uh oh!

w2807 Apr 29, 2025 — with giscus

Uh oh!

w2807 Apr 29, 2025 — with giscus

giscus[bot]
bot Oct 17, 2022

Replies: 19 comments 2 replies

qbmiller
Oct 17, 2022 — with giscus

dugulingping
Dec 13, 2022 — with giscus

dugulingping
Dec 13, 2022 — with giscus

dugulingping
Dec 13, 2022 — with giscus

dugulingping
Dec 13, 2022 — with giscus

dugulingping
Dec 13, 2022 — with giscus

zhangbest5
Jan 13, 2023 — with giscus

Fu-LianPeng
Jan 19, 2023 — with giscus

Fu-LianPeng
Jan 19, 2023 — with giscus

xubai2001
Jan 10, 2024 — with giscus

xubai2001
Jan 10, 2024 — with giscus

jiajialinli
Feb 29, 2024 — with giscus

hongjiala
Apr 8, 2025 — with giscus

hongjiala
Apr 8, 2025 — with giscus

hongjiala
Apr 8, 2025 — with giscus

hongjiala
Apr 8, 2025 — with giscus

hongjiala
Apr 8, 2025 — with giscus

w2807
Apr 29, 2025 — with giscus

w2807
Apr 29, 2025 — with giscus