示例: Bit数组

Go 语言里的集合一般会用 map[T]bool 这种形式来表示，T 代表元素类型。集合用 map 类型来表示虽然非常灵活，但我们可以以一种更好的形式来表示它。例如在数据流分析领域，集合元素通常是一个非负整数，集合会包含很多元素，并且集合会经常进行并集、交集操作，这种情况下，bit 数组会比 map 表现更加理想。（译注：这里再补充一个例子，比如我们执行一个 http 下载任务，把文件按照 16kb 一块划分为很多块，需要有一个全局变量来标识哪些块下载完成了，这种时候也需要用到 bit 数组。）

一个 bit 数组通常会用一个无符号数或者称之为“字”的 slice 来表示，每一个元素的每一位都表示集合里的一个值。当集合的第 i 位被设置时，我们才说这个集合包含元素 i 。下面的这个程序展示了一个简单的 bit 数组类型，并且实现了三个函数来对这个 bit 数组来进行操作：

ch6/intset

Unresolved include directive in modules/ROOT/pages/ch6/ch6-05.adoc - include::example$ch6/intset/intset.go[]

因为每一个字都有 64 个二进制位，所以为了定位 x 的bit位，我们用了 x/64 的商作为字的下标，并且用 x%64 得到的值作为这个字内的 bit 的所在位置。 UnionWith 这个方法里用到了 bit 位的“或”逻辑操作符号 | 来一次完成 64 个元素的或计算。（在练习6.5中我们还会有程序用到这个 64 位字的例子。）

当前这个实现还缺少了很多必要的特性，我们把其中一些作为练习题列在本小节之后。但是有一个方法如果缺失的话我们的 bit 数组可能会比较难混：将 IntSet 作为一个字符串来打印。这里我们来实现它，让我们来给上面的例子添加一个 String 方法，类似 2.5 节中做的那样：

ch6/intset

Unresolved include directive in modules/ROOT/pages/ch6/ch6-05.adoc - include::example$ch6/intset/intset.go[]

这里留意一下 String 方法，是不是和3.5.4节中的 intsToString 方法很相似；bytes.Buffer 在 String 方法里经常这么用。当你为一个复杂的类型定义了一个 String 方法时，fmt 包就会特殊对待这种类型的值，这样可以让这些类型在打印的时候看起来更加友好，而不是直接打印其原始的值。fmt 会直接调用用户定义的 String 方法。这种机制依赖于接口和类型断言，在第7章中我们会详细介绍。

现在我们就可以在实战中直接用上面定义好的 IntSet 了：

ch6/intset

Unresolved include directive in modules/ROOT/pages/ch6/ch6-05.adoc - include::example$ch6/intset/intset_test.go[]

这里要注意：我们声明的 String 和 Has 两个方法都是以指针类型 *IntSet 来作为接收器的，但实际上对于这两个类型来说，把接收器声明为指针类型也没什么必要。不过另外两个函数就不是这样了，因为另外两个函数操作的是 s.words 对象，如果你不把接收器声明为指针对象，那么实际操作的是拷贝对象，而不是原来的那个对象。因此，因为我们的 String 方法定义在 IntSet 指针上，所以当我们的变量是 IntSet 类型而不是 IntSet 指针时，可能会有下面这样让人意外的情况：

ch6/intset

Unresolved include directive in modules/ROOT/pages/ch6/ch6-05.adoc - include::example$ch6/intset/intset_test.go[]

在第一个 Println 中，我们打印一个 *IntSet 的指针，这个类型的指针确实有自定义的 String 方法。第二 Println ，我们直接调用了 x 变量的 String() 方法；这种情况下编译器会隐式地在 x 前插入 & 操作符，这样相当于我们还是调用的 IntSet 指针的 String 方法。在第三个 Println 中，因为 IntSet 类型没有 String 方法，所以 Println 方法会直接以原始的方式理解并打印。所以在这种情况下 & 符号是不能忘的。在我们这种场景下，你把 String 方法绑定到 IntSet 对象上，而不是 IntSet 指针上可能会更合适一些，不过这也需要具体问题具体分析。

练习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

练习 6.2：定义一个变参方法 (*IntSet).AddAll(…int) ，这个方法可以添加一组 IntSet ，比如 s.AddAll(1,2,3) 。

练习 6.3： (*IntSet).UnionWith 会用 | 操作符计算两个集合的并集，我们再为 IntSet 实现另外的几个函数 IntersectWith （交集：元素在 A 集合 B 集合均出现）， DifferenceWith（差集：元素出现在 A 集合，未出现在 B 集合）， SymmetricDifference（并差集：元素出现在 A 但没有出现在 B，或者出现在 B 没有出现在 A）。

练习 6.4：实现一个 Elems 方法，返回集合中的所有元素，用于做一些 range 之类的遍历操作。

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