phpbit数组技巧_golang 实现Bit数组

文章目录 [+]

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

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

phpbit数组技巧_golang 实现Bit数组

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

（图片来自网络侵删）

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

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

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

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

var x, y IntSetx.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两个方法都因此指针类型IntSet来作为吸收器的，但实际上对付这两个类型来说，把吸收器声明为指针类型也没什么必要。
不过其余两个函数就不是这样了，由于其余两个函数操作的是s.words工具，如果你不把吸收器声明为指针工具，那么实际操作的是拷贝工具，而不是原来的那个工具。
因此，由于我们的String方法定义在IntSet指针上，以是当我们的变量是IntSet类型而不是IntSet指针时，可能会有下面这样让人意外的情形：

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

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

上面实现的add方法和String方法大概有些人不太理解，我刚开始也不理解，重新复习了下位运算了，原来是这么大略的骚操作：

先来大略复习下位运算左移动

1 << 1 0000 0001 -> 0000 0010 === 2

1 << 3 0000 0001 -> 0000 1000 === 8

&（位与）：比较二进制数相对应的每一位，相对的位均为1，则对应位输出 1，相对应有一位为0或无则为0

8 & 9 ： 1000 & 1001 ==> 1000 ；16&8：10000 & 1000==>0

|（位或）:比较二进制数相对应的每一位，相对的位有一个为1，则对应位输出1，相对应的均为0则为0

8 | 9：1000 & 1001 ==> 1001 ; 16&8: 10000 & 1000 ==> 11000 (24)

^(位异或)：比较二进制数相对应的每一位，相对的位相同，则对应位输出0，相对应的位不同则为1

8 ^ 9 : 1000 ^ 1001 ⇒ 0001 ; 16&8: 10000 ^ 1000 ==> 11000(24)

2 | 1<<3 :

0000 0010 | 0000 1000 ==== 0000 1010