您的位置:首页 > 技术中心 > 其他 >

Golang中Bit数组如何实现(代码示例)

时间:2022-02-24 10:28

下面由Golang教程栏目给大家介绍Golang中Bit数组的实现方法,希望对需要的朋友有所帮助!

Go语言实现Bit数组常用方法

Go语言里的集合一般会用map[T]bool这种形式来表示,T代表元素类型。集合用map类型来表示虽然非常灵活,但我们可以以一种更好的形式来表示它。例如在数据流分析领域,集合元素通常是一个非负整数,集合会包含很多元素,并且集合会经常进行并集、交集操作,这种情况下,bit数组会比map表现更加理想。

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

  1. package main
  2. import (
  3. "bytes"
  4. "fmt"
  5. )
  6. // An IntSet is a set of small non-negative integers.
  7. // Its zero value represents the empty set.
  8. type IntSet struct {
  9. words []uint
  10. }
  11. const (
  12. bitNum = (32 << (^uint(0) >> 63)) //根据平台自动判断决定是32还是64
  13. )
  14. // Has reports whether the set contains the non-negative value x.
  15. func (s *IntSet) Has(x int) bool {
  16. word, bit := x/bitNum, uint(x%bitNum)
  17. return word < len(s.words) && s.words[word]&(1<<bit) != 0
  18. }
  19. // Add adds the non-negative value x to the set.
  20. func (s *IntSet) Add(x int) {
  21. word, bit := x/bitNum, uint(x%bitNum)
  22. for word >= len(s.words) {
  23. s.words = append(s.words, 0)
  24. }
  25. s.words[word] |= 1 << bit
  26. }
  27. //A与B的交集,合并A与B
  28. // UnionWith sets s to the union of s and t.
  29. func (s *IntSet) UnionWith(t *IntSet) {
  30. for i, tword := range t.words {
  31. if i < len(s.words) {
  32. s.words[i] |= tword
  33. } else {
  34. s.words = append(s.words, tword)
  35. }
  36. }
  37. }

因为每一个字都有64个二进制位,所以为了定位x的bit位,我们用了x/64的商作为字的下标,并且用x%64得到的值作为这个字内的bit的所在位置。

例如,对于数字1,将其加入比特数组:

  1. func (s *IntSet) Add(x int) {
  2. word, bit := x/bitNum, uint(x%bitNum) //0, 1 := 1/64, uint(1%64)
  3. for word >= len(s.words) { // 条件不满足
  4. s.words = append(s.words, 0)
  5. }
  6. s.words[word] |= 1 << bit // s.words[0] |= 1 << 1
  7. }
  8. // 把1存入后,words数组变为了[]uint64{2}

同理,假如我们再将66加入比特数组:

  1. func (s *IntSet) Add(x int) {
  2. word, bit := x/bitNum, uint(x%bitNum) //1, 2 := 66/64, uint(66%64)
  3. for word >= len(s.words) { // 条件满足
  4. s.words = append(s.words, 0) // 此时s.words = []uint64{2, 0}
  5. }
  6. s.words[word] |= 1 << bit // s.words[1] |= 1 << 2
  7. }
  8. // 继续把66存入后,words数组变为了[]uint64{2, 4}

所以,对于words,每个元素可存储的值有64个,每超过64个则进位,即添加一个元素。(注意,0也占了一位,所以64才要进位,第一个元素可存储0-63)。

所以,对于words中的一个元素,要转换为具体的值时:首先取到其位置i,用 64 * i 作为已进位数(类似于每10位要进位), 然后将这个元素转换为二进制数,从右往左数,第多少位为1则表示相应的有这个值,用这个位数 x+64 *i 即为我们存入的值。

相应的,可有如下String()函数

  1. // String returns the set as a string of the form "{1 2 3}".
  2. func (s *IntSet) String() string {
  3. var buf bytes.Buffer
  4. buf.WriteByte('{')
  5. for i, word := range s.words {
  6. if word == 0 {
  7. continue
  8. }
  9. for j := 0; j < bitNum; j++ {
  10. if word&(1<<uint(j)) != 0 {
  11. if buf.Len() > len("{") {
  12. buf.WriteByte(' ')
  13. }
  14. fmt.Fprintf(&buf, "%d", bitNum*i+j)
  15. }
  16. }
  17. }
  18. buf.WriteByte('}')
  19. return buf.String()
  20. }

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

  1. // []uint64{2 4}
  2. // 对于2: 1 << 1 = 2; 所以 x = 0 * 64 + 1
  3. // 对于4: 1 << 2 = 4; 所以 x = 1 * 64 + 2
  4. // 所以转换为String为{1 66}

实现比特数组的其他方法函数

  1. func (s *IntSet) Len() int {
  2. var len int
  3. for _, word := range s.words {
  4. for j := 0; j < bitNum; j++ {
  5. if word&(1<<uint(j)) != 0 {
  6. len++
  7. }
  8. }
  9. }
  10. return len
  11. }
  12. func (s *IntSet) Remove(x int) {
  13. word, bit := x/bitNum, uint(x%bitNum)
  14. if s.Has(x) {
  15. s.words[word] ^= 1 << bit
  16. }
  17. }
  18. func (s *IntSet) Clear() {
  19. s.words = append([]uint{})
  20. }
  21. func (s *IntSet) Copy() *IntSet {
  22. intSet := &IntSet{
  23. words: []uint{},
  24. }
  25. for _, value := range s.words {
  26. intSet.words = append(intSet.words, value)
  27. }
  28. return intSet
  29. }
  30. func (s *IntSet) AddAll(args ...int) {
  31. for _, x := range args {
  32. s.Add(x)
  33. }
  34. }
  35. //A与B的并集,A与B中均出现
  36. func (s *IntSet) IntersectWith(t *IntSet) {
  37. for i, tword := range t.words {
  38. if i >= len(s.words) {
  39. continue
  40. }
  41. s.words[i] &= tword
  42. }
  43. }
  44. //A与B的差集,元素出现在A未出现在B
  45. func (s *IntSet) DifferenceWith(t *IntSet) {
  46. t1 := t.Copy() //为了不改变传参t,拷贝一份
  47. t1.IntersectWith(s)
  48. for i, tword := range t1.words {
  49. if i < len(s.words) {
  50. s.words[i] ^= tword
  51. }
  52. }
  53. }
  54. //A与B的并差集,元素出现在A没有出现在B,或出现在B没有出现在A
  55. func (s *IntSet) SymmetricDifference(t *IntSet) {
  56. for i, tword := range t.words {
  57. if i < len(s.words) {
  58. s.words[i] ^= tword
  59. } else {
  60. s.words = append(s.words, tword)
  61. }
  62. }
  63. }
  64. //获取比特数组中的所有元素的slice集合
  65. func (s *IntSet) Elems() []int {
  66. var elems []int
  67. for i, word := range s.words {
  68. for j := 0; j < bitNum; j++ {
  69. if word&(1<<uint(j)) != 0 {
  70. elems = append(elems, bitNum*i+j)
  71. }
  72. }
  73. }
  74. return elems
  75. }

至此,比特数组的常用方法函数都已实现,现在可以来使用它。

  1. func main() {
  2. var x, y IntSet
  3. x.Add(1)
  4. x.Add(144)
  5. x.Add(9)
  6. fmt.Println("x:", x.String()) // "{1 9 144}"
  7. y.Add(9)
  8. y.Add(42)
  9. fmt.Println("y:", y.String()) // "{9 42}"
  10. x.UnionWith(&y)
  11. fmt.Println("x unionWith y:", x.String()) // "{1 9 42 144}"
  12. fmt.Println("x has 9,123:", x.Has(9), x.Has(123)) // "true false"
  13. fmt.Println("x len:", x.Len()) //4
  14. fmt.Println("y len:", y.Len()) //2
  15. x.Remove(42)
  16. fmt.Println("x after Remove 42:", x.String()) //{1 9 144}
  17. z := x.Copy()
  18. fmt.Println("z copy from x:", z.String()) //{1 9 144}
  19. x.Clear()
  20. fmt.Println("clear x:", x.String()) //{}
  21. x.AddAll(1, 2, 9)
  22. fmt.Println("x addAll 1,2,9:", x.String()) //{1 2 9}
  23. x.IntersectWith(&y)
  24. fmt.Println("x intersectWith y:", x.String()) //{9}
  25. x.AddAll(1, 2)
  26. fmt.Println("x addAll 1,2:", x.String()) //{1 2 9}
  27. x.DifferenceWith(&y)
  28. fmt.Println("x differenceWith y:", x.String()) //{1 2}
  29. x.AddAll(9, 144)
  30. fmt.Println("x addAll 9,144:", x.String()) //{1 2 9 144}
  31. x.SymmetricDifference(&y)
  32. fmt.Println("x symmetricDifference y:", x.String()) //{1 2 42 144}
  33. for _, value := range x.Elems() {
  34. fmt.Print(value, " ") //1 2 42 144
  35. }
  36. }

以上就是Golang中Bit数组如何实现(代码示例)的详细内容,更多请关注gxlsystem.com其它相关文章!

热门排行

今日推荐

热门手游