下面由golang教程栏目给大家介绍golang中bit数组的实现方法，希望对需要的朋友有所帮助！
go语言实现bit数组常用方法go语言里的集合一般会用map[t]bool这种形式来表示，t代表元素类型。集合用map类型来表示虽然非常灵活，但我们可以以一种更好的形式来表示它。例如在数据流分析领域，集合元素通常是一个非负整数，集合会包含很多元素，并且集合会经常进行并集、交集操作，这种情况下，bit数组会比map表现更加理想。
一个bit数组通常会用一个无符号数或者称之为“字”的slice来表示，每一个元素的每一位都表示集合里的一个值。当集合的第i位被设置时，我们才说这个集合包含元素i。下面的这个程序展示了一个简单的bit数组类型，并且实现了三个函数来对这个bit数组来进行操作：
package mainimport ( "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 << (^uint(0) >> 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[word]&(1<<bit) != 0}// add adds the non-negative value x to the set.func (s *intset) add(x int) { word, bit := x/bitnum, uint(x%bitnum) for word >= len(s.words) { s.words = append(s.words, 0) } s.words[word] |= 1 << bit}//a与b的交集，合并a与b// 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) } }}
因为每一个字都有64个二进制位，所以为了定位x的bit位，我们用了x/64的商作为字的下标，并且用x%64得到的值作为这个字内的bit的所在位置。
例如，对于数字1，将其加入比特数组：
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 << bit // s.words[0] |= 1 << 1}// 把1存入后，words数组变为了[]uint64{2}
同理，假如我们再将66加入比特数组：
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 << bit // s.words[1] |= 1 << 2}// 继续把66存入后，words数组变为了[]uint64{2, 4}
所以，对于words，每个元素可存储的值有64个，每超过64个则进位，即添加一个元素。（注意，0也占了一位，所以64才要进位，第一个元素可存储0-63）。
所以，对于words中的一个元素，要转换为具体的值时：首先取到其位置i，用 64 * i 作为已进位数（类似于每10位要进位）， 然后将这个元素转换为二进制数，从右往左数，第多少位为1则表示相应的有这个值，用这个位数 x+64 *i 即为我们存入的值。
相应的，可有如下string()函数// 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 < bitnum; j++ { if word&(1<<uint(j)) != 0 { if buf.len() > len("{") { buf.writebyte(' ') } fmt.fprintf(&buf, "%d", bitnum*i+j) } } } buf.writebyte('}') return buf.string()}
例如，前面存入了1和66后，转换过程为：
// []uint64{2 4}// 对于2: 1 << 1 = 2; 所以 x = 0 * 64 + 1 // 对于4: 1 << 2 = 4; 所以 x = 1 * 64 + 2// 所以转换为string为{1 66}
实现比特数组的其他方法函数func (s *intset) len() int { var len int for _, word := range s.words { for j := 0; j < bitnum; j++ { if word&(1<<uint(j)) != 0 { len++ } } } return len}func (s *intset) remove(x int) { word, bit := x/bitnum, uint(x%bitnum) if s.has(x) { s.words[word] ^= 1 << bit }}func (s *intset) clear() { s.words = append([]uint{})}func (s *intset) copy() *intset { intset := &intset{ words: []uint{}, } for _, value := range s.words { intset.words = append(intset.words, value) } return intset}func (s *intset) addall(args ...int) { for _, x := range args { s.add(x) }}//a与b的并集，a与b中均出现func (s *intset) intersectwith(t *intset) { for i, tword := range t.words { if i >= len(s.words) { continue } s.words[i] &= tword }}//a与b的差集，元素出现在a未出现在bfunc (s *intset) differencewith(t *intset) { t1 := t.copy() //为了不改变传参t，拷贝一份 t1.intersectwith(s) for i, tword := range t1.words { if i < len(s.words) { s.words[i] ^= tword } }}//a与b的并差集，元素出现在a没有出现在b，或出现在b没有出现在afunc (s *intset) symmetricdifference(t *intset) { for i, tword := range t.words { if i < len(s.words) { s.words[i] ^= tword } else { s.words = append(s.words, tword) } }}//获取比特数组中的所有元素的slice集合func (s *intset) elems() []int { var elems []int for i, word := range s.words { for j := 0; j < bitnum; j++ { if word&(1<<uint(j)) != 0 { elems = append(elems, bitnum*i+j) } } } return elems}
至此，比特数组的常用方法函数都已实现，现在可以来使用它。
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中bit数组如何实现（代码示例）的详细内容。