原文鏈接：https://gopl-zh.github.io/ch6/ch6-05.html

6.5. 示例: Bit數(shù)組

Go語(yǔ)言里的集合一般會(huì)用map[T]bool這種形式來(lái)表示，T代表元素類型。集合用map類型來(lái)表示雖然非常靈活，但我們可以以一種更好的形式來(lái)表示它。例如在數(shù)據(jù)流分析領(lǐng)域，集合元素通常是一個(gè)非負(fù)整數(shù)，集合會(huì)包含很多元素，并且集合會(huì)經(jīng)常進(jìn)行并集、交集操作，這種情況下，bit數(shù)組會(huì)比map表現(xiàn)更加理想。（譯注：這里再補(bǔ)充一個(gè)例子，比如我們執(zhí)行一個(gè)http下載任務(wù)，把文件按照16kb一塊劃分為很多塊，需要有一個(gè)全局變量來(lái)標(biāo)識(shí)哪些塊下載完成了，這種時(shí)候也需要用到bit數(shù)組。）

一個(gè)bit數(shù)組通常會(huì)用一個(gè)無(wú)符號(hào)數(shù)或者稱之為“字”的slice來(lái)表示，每一個(gè)元素的每一位都表示集合里的一個(gè)值。當(dāng)集合的第i位被設(shè)置時(shí)，我們才說(shuō)這個(gè)集合包含元素i。下面的這個(gè)程序展示了一個(gè)簡(jiǎn)單的bit數(shù)組類型，并且實(shí)現(xiàn)了三個(gè)函數(shù)來(lái)對(duì)這個(gè)bit數(shù)組來(lái)進(jìn)行操作：

gopl.io/ch6/intset

// 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
}

// Add adds the non-negative value x to the set.
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
}

// 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)
        }
    }
}

因?yàn)槊恳粋€(gè)字都有64個(gè)二進(jìn)制位，所以為了定位x的bit位，我們用了x/64的商作為字的下標(biāo)，并且用x%64得到的值作為這個(gè)字內(nèi)的bit的所在位置。UnionWith這個(gè)方法里用到了bit位的“或”邏輯操作符號(hào)|來(lái)一次完成64個(gè)元素的或計(jì)算。（在練習(xí)6.5中我們還會(huì)有程序用到這個(gè)64位字的例子。）

當(dāng)前這個(gè)實(shí)現(xiàn)還缺少了很多必要的特性，我們把其中一些作為練習(xí)題列在本小節(jié)之后。但是有一個(gè)方法如果缺失的話我們的bit數(shù)組可能會(huì)比較難混：將IntSet作為一個(gè)字符串來(lái)打印。這里我們來(lái)實(shí)現(xiàn)它，讓我們來(lái)給上面的例子添加一個(gè)String方法，類似2.5節(jié)中做的那樣：

// 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()
}

這里留意一下String方法，是不是和3.5.4節(jié)中的intsToString方法很相似；bytes.Buffer在String方法里經(jīng)常這么用。當(dāng)你為一個(gè)復(fù)雜的類型定義了一個(gè)String方法時(shí)，fmt包就會(huì)特殊對(duì)待這種類型的值，這樣可以讓這些類型在打印的時(shí)候看起來(lái)更加友好，而不是直接打印其原始的值。fmt會(huì)直接調(diào)用用戶定義的String方法。這種機(jī)制依賴于接口和類型斷言，在第7章中我們會(huì)詳細(xì)介紹。

現(xiàn)在我們就可以在實(shí)戰(zhàn)中直接用上面定義好的IntSet了：

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.Has(9), x.Has(123)) // "true false"

這里要注意：我們聲明的String和Has兩個(gè)方法都是以指針類型*IntSet來(lái)作為接收器的，但實(shí)際上對(duì)于這兩個(gè)類型來(lái)說(shuō)，把接收器聲明為指針類型也沒什么必要。不過(guò)另外兩個(gè)函數(shù)就不是這樣了，因?yàn)榱硗鈨蓚€(gè)函數(shù)操作的是s.words對(duì)象，如果你不把接收器聲明為指針對(duì)象，那么實(shí)際操作的是拷貝對(duì)象，而不是原來(lái)的那個(gè)對(duì)象。因此，因?yàn)槲覀兊腟tring方法定義在IntSet指針上，所以當(dāng)我們的變量是IntSet類型而不是IntSet指針時(shí)，可能會(huì)有下面這樣讓人意外的情況：

fmt.Println(&x)         // "{1 9 42 144}"
fmt.Println(x.String()) // "{1 9 42 144}"
fmt.Println(x)          // "{[4398046511618 0 65536]}"

在第一個(gè)Println中，我們打印一個(gè)*IntSet的指針，這個(gè)類型的指針確實(shí)有自定義的String方法。第二Println，我們直接調(diào)用了x變量的String()方法；這種情況下編譯器會(huì)隱式地在x前插入&操作符，這樣相當(dāng)于我們還是調(diào)用的IntSet指針的String方法。在第三個(gè)Println中，因?yàn)镮ntSet類型沒有String方法，所以Println方法會(huì)直接以原始的方式理解并打印。所以在這種情況下&符號(hào)是不能忘的。在我們這種場(chǎng)景下，你把String方法綁定到IntSet對(duì)象上，而不是IntSet指針上可能會(huì)更合適一些，不過(guò)這也需要具體問題具體分析。

練習(xí)6.1: 為bit數(shù)組實(shí)現(xiàn)下面這些方法

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

練習(xí) 6.2： 定義一個(gè)變參方法(*IntSet).AddAll(...int)，這個(gè)方法可以添加一組IntSet，比如s.AddAll(1,2,3)。

練習(xí) 6.3： (*IntSet).UnionWith會(huì)用|操作符計(jì)算兩個(gè)集合的并集，我們?cè)贋镮ntSet實(shí)現(xiàn)另外的幾個(gè)函數(shù)IntersectWith（交集：元素在A集合B集合均出現(xiàn)），DifferenceWith（差集：元素出現(xiàn)在A集合，未出現(xiàn)在B集合），SymmetricDifference（并差集：元素出現(xiàn)在A但沒有出現(xiàn)在B，或者出現(xiàn)在B沒有出現(xiàn)在A）。

練習(xí) 6.4:  實(shí)現(xiàn)一個(gè)Elems方法，返回集合中的所有元素，用于做一些range之類的遍歷操作。

練習(xí) 6.5： 我們這章定義的IntSet里的每個(gè)字都是用的uint64類型，但是64位的數(shù)值可能在32位的平臺(tái)上不高效。修改程序，使其使用uint類型，這種類型對(duì)于32位平臺(tái)來(lái)說(shuō)更合適。當(dāng)然了，這里我們可以不用簡(jiǎn)單粗暴地除64，可以定義一個(gè)常量來(lái)決定是用32還是64，這里你可能會(huì)用到平臺(tái)的自動(dòng)判斷的一個(gè)智能表達(dá)式：32 << (^uint(0) >> 63)