Golang中Bit数组的实现方式

本篇文章给大家分享《Golang中Bit数组的实现方式》，覆盖了Golang的常见基础知识，其实一个语言的全部知识点一篇文章是不可能说完的，但希望通过这些问题，让读者对自己的掌握程度有一定的认识(B 数)，从而弥补自己的不足，更好的掌握它。

Go语言里的集合一般会用map[T]bool这种形式来表示，T代表元素类型。集合用map类型来表示虽然非常灵活，但我们可以以一种更好的形式来表示它。

例如在数据流分析领域，集合元素通常是一个非负整数，集合会包含很多元素，并且集合会经常进行并集、交集操作，这种情况下，bit数组会比map表现更加理想。

一个bit数组通常会用一个无符号数或者称之为“字”的slice来表示，每一个元素的每一位都表示集合里的一个值。当集合的第i位被设置时，我们才说这个集合包含元素i。

下面的这个程序展示了一个简单的bit数组类型，并且实现了三个函数来对这个bit数组来进行操作：

package main
import (
	"bytes"
	"fmt"
)
// An IntSet is a set of small non-negative integers.
// Its zero value represents the empty set.
type IntSet struct {
	words []uint
}
const (
	bitNum = (32 > 63)) //根据平台自动判断决定是32还是64
)
// Has reports whether the set contains the non-negative value x.
func (s *IntSet) Has(x int) bool {
	word, bit := x/bitNum, uint(x%bitNum)
	return word = len(s.words) {
		s.words = append(s.words, 0)
	}
	s.words[word] |= 1 

<p>因为每一个字都有64个二进制位，所以为了定位x的bit位，我们用了x/64的商作为字的下标，并且用x%64得到的值作为这个字内的bit的所在位置。</p>
<p>例如，对于数字1，将其加入比特数组：</p>

<pre class="brush:plain;">
func (s *IntSet) Add(x int) {
 word, bit := x/bitNum, uint(x%bitNum) //0, 1 := 1/64, uint(1%64)
 for word >= len(s.words) { // 条件不满足
  s.words = append(s.words, 0)
 }
 s.words[word] |= 1 

<p>同理，假如我们再将66加入比特数组：</p>

<pre class="brush:plain;">
func (s *IntSet) Add(x int) {
 word, bit := x/bitNum, uint(x%bitNum) //1, 2 := 66/64, uint(66%64)
 for word >= len(s.words) { // 条件满足
  s.words = append(s.words, 0) // 此时s.words = []uint64{2, 0}
 }
 s.words[word] |= 1 

<p>所以，对于words，每个元素可存储的值有64个，每超过64个则进位，即添加一个元素。（注意，0也占了一位，所以64才要进位，第一个元素可存储0-63）。</p>
<p>所以，对于words中的一个元素，要转换为具体的值时：首先取到其位置i，用 64 * i 作为已进位数（类似于每10位要进位）， 然后将这个元素转换为二进制数，从右往左数，第多少位为1则表示相应的有这个值，用这个位数 x+64 *i 即为我们存入的值。</p>
<h2>相应的，可有如下String()函数</h2>

<pre class="brush:plain;">
// 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  len("{") {
     buf.WriteByte(' ')
    }
    fmt.Fprintf(&buf, "%d", bitNum*i+j)
   }
  }
 }
 buf.WriteByte('}')
 return buf.String()
}

例如，前面存入了1和66后，转换过程为：

// []uint64{2 4}
// 对于2: 1 

<h2>实现比特数组的其他方法函数</h2>

<pre class="brush:plain;">
func (s *IntSet) Len() int {
	var len int
	for _, word := range s.words {
		for j := 0; j = len(s.words) {
			continue
		}
		s.words[i] &= tword
	}
}
//A与B的差集，元素出现在A未出现在B
func (s *IntSet) DifferenceWith(t *IntSet) {
	t1 := t.Copy() //为了不改变传参t，拷贝一份
	t1.IntersectWith(s)
	for i, tword := range t1.words {
		if i 

<p>至此，比特数组的常用方法函数都已实现，现在可以来使用它。</p>

<pre class="brush:plain;">
func main() {
	var x, y IntSet
	x.Add(1)
	x.Add(144)
	x.Add(9)
	fmt.Println("x:", x.String()) // "{1 9 144}"
	y.Add(9)
	y.Add(42)
	fmt.Println("y:", y.String()) // "{9 42}"
	x.UnionWith(&y)
	fmt.Println("x unionWith y:", x.String())         // "{1 9 42 144}"
	fmt.Println("x has 9,123:", x.Has(9), x.Has(123)) // "true false"
	fmt.Println("x len:", x.Len())                    //4
	fmt.Println("y len:", y.Len())                    //2
	x.Remove(42)
	fmt.Println("x after Remove 42:", x.String()) //{1 9 144}
	z := x.Copy()
	fmt.Println("z copy from x:", z.String()) //{1 9 144}
	x.Clear()
	fmt.Println("clear x:", x.String()) //{}
	x.AddAll(1, 2, 9)
	fmt.Println("x addAll 1,2,9:", x.String()) //{1 2 9}
	x.IntersectWith(&y)
	fmt.Println("x intersectWith y:", x.String()) //{9}
	x.AddAll(1, 2)
	fmt.Println("x addAll 1,2:", x.String()) //{1 2 9}
	x.DifferenceWith(&y)
	fmt.Println("x differenceWith y:", x.String()) //{1 2}
	x.AddAll(9, 144)
	fmt.Println("x addAll 9,144:", x.String()) //{1 2 9 144}
	x.SymmetricDifference(&y)
	fmt.Println("x symmetricDifference y:", x.String()) //{1 2 42 144}
	for _, value := range x.Elems() {
		fmt.Print(value, " ") //1 2 42 144
	}
}

以上为个人经验，希望能给大家一个参考，也希望大家多多支持golang学习网。如有错误或未考虑完全的地方，望不吝赐教。

到这里，我们也就讲完了《Golang中Bit数组的实现方式》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于golang的知识点！