关于godailylib:Go-每日一库之-bitset

咱们都晓得计算机是基于二进制的，位运算是计算机的根底运算。位运算的劣势很显著，CPU 指令原生反对、速度快。基于位运算的位汇合在无限的场景中替换汇合数据结构能够收到意想不到的成果。bitset库实现了位汇合及相干操作，无妨拿来即用。

本文代码应用 Go Modules。

创立目录并初始化：

$ mkdir -p bitset && cd bitset
$ go mod init github.com/darjun/go-daily-lib/bitset

装置 bitset 库：

$ go get -u github.com/bits-and-blooms/bitset

位汇合的基本操作有：

查看位（Test）：查看某个索引是否为 1。类比查看元素是否在汇合中
设置位（Set）：将某个索引设置为 1。类比向汇合增加元素
革除位（Clear）：将某个索引革除，设置为 0。类比从汇合中删除元素
翻转位（Flip）：如果某个索引为 1，则设置为 0，反之设置为 1
并（Union）：两个位汇合执行并操作。类比汇合的并
交（Intersection）：两个位汇合执行交操作。类比汇合的交

位汇合个别用于小数值的非负整数的场景中。就拿游戏中简略的签到举例吧，很多游戏都有签到流动，短的有 7 天的，长的有 30 天。这种就很适宜应用位汇合。每个位的值示意其索引地位对应的那天有没有签到。

type Player struct {sign *bitset.BitSet}

func NewPlayer(sign uint) *Player {
  return &Player{sign: bitset.From([]uint64{uint64(sign)}),
  }
}

func (this *Player) Sign(day uint) {this.sign.Set(day)
}

func (this *Player) IsSigned(day uint) bool {return this.sign.Test(day)
}

func main() {player := NewPlayer(1) // 第一天签到
  for day := uint(2); day <= 7; day++ {if rand.Intn(100)&1 == 0 {player.Sign(day - 1)
    }
  }

  for day := uint(1); day <= 7; day++ {if player.IsSigned(day - 1) {fmt.Printf("day:%d signed\n", day)
    }
  }
}

bitset 提供了多种创立 BitSet 对象的办法。

首先 bitset.BitSet 零值可用，如果一开始不晓得有多少元素，能够应用这种形式创立：

var b bitset.BitSet

BitSet 在设置时主动调整大小。如果当时晓得长度，创立 BitSet 时可传入此值，能无效防止主动调整的开销：

b := bitset.New(100)

bitset 构造反对链式调用，大部分办法返回本身的指针，所以能够这样写：

b.Set(10).Set(11).Clear(12).Flip(13);

留神，bitset 的索引是从 0 开始的。

记得之前在网上看过一道题：

一个农夫带着一只狼、一头羊和一颗白菜来到河边。他须要用船把他们带到对岸。然而，这艘船只能容下农夫自己和另外一种货色（要么是狼，要么是羊，要么是白菜）。如果农夫不在场的话，狼就会吃掉羊，羊会吃掉白菜。请为农夫解决这个问题。

这其实是一个状态搜寻的问题，用回溯法就能解决。农夫、狼、羊、白菜都有两个状态，即在河左岸（假如刚开始农夫所处的是左岸）还是河右岸。这里实际上还有个船的状态，因为船肯定和农夫的状态是统一的，就不必额定思考了。这些状态咱们很容易用位汇合来示意：

const (
  FARMER = iota
  WOLF
  SHEEP
  CABBAGE
)

编写一个函数来判断状态是否非法。有两种状态不非法：

狼和羊在同一边，并且不和农夫在同一边。此时狼会吃掉羊
羊和白菜在同一边，并且不和农夫在同一边。此时羊会吃掉白菜

func IsStateValid(state *bitset.BitSet) bool {if state.Test(WOLF) == state.Test(SHEEP) &&
    state.Test(WOLF) != state.Test(FARMER) {
    // 狼和羊在同一边，并且不和农夫在同一边
    // 狼会吃掉羊，非法
    return false
  }

  if state.Test(SHEEP) == state.Test(CABBAGE) &&
    state.Test(SHEEP) != state.Test(FARMER) {
    // 羊和白菜在同一边，并且不和农夫在同一边
    // 羊会吃掉白菜，非法
    return false
  }

  return true
}

接下来编写搜寻函数：

func search(b *bitset.BitSet, visited map[string]struct{}) bool {if !IsStateValid(b) {return false}

  if _, exist := visited[b.String()]; exist {
    // 状态已遍历
    return false
  }

  if b.Count() == 4 {return true}

  visited[b.String()] = struct{}{}
  for index := uint(FARMER); index <= CABBAGE; index++ {if b.Test(index) != b.Test(FARMER) {
      // 与农夫不在一边，不能带上船
      continue
    }

    // 带到对岸去
    b.Flip(index)
    if index != FARMER {
      // 如果 index 为 FARMER，示意不带任何货色
      b.Flip(FARMER)
    }

    if search(b, visited) {return true}

    // 状态复原
    b.Flip(index)
    if index != FARMER {b.Flip(FARMER)
    }
  }

  return false
}

主函数：

func main() {b := bitset.New(4)

  visited := make(map[string]struct{})
  fmt.Println(search(b, visited))
}

初始时，所有状态为 0，都到对岸之后所有状态为 1，故 b.Count() == 4 示意都已达到对岸了。因为搜寻是自觉的，可能会有限循环：这次农夫将羊带到对岸，下次又将其从对岸带回来了。所以咱们须要做状态去重。bitset.String()返回以后位汇合的字符串示意，咱们以此来判断状态是否反复。

for 循环顺次尝试带各种物品，或什么也不带。驱动查找过程。

如果想得到农夫正确的动作序列，能够给 search 加一个参数，记录每一步的操作：

func search(b *bitset.BitSet, visited map[string]struct{}, path *[]*bitset.BitSet) bool {
  // 记录门路
  *path = append(*path, b.Clone())
  if b.Count() == 4 {return true}

  // ...
  *path = (*path)[:len(*path)-1]

  return false
}

func main() {b := bitset.New(4)

  visited := make(map[string]struct{})
  var path []*bitset.BitSet
  if search(b, visited, &path) {PrintPath(path)
  }
}

如果找到解，打印之：

var names = []string{"农夫", "狼", "羊", "白菜"}

func PrintState(b *bitset.BitSet) {fmt.Println("=======================")
  fmt.Println("河左岸：")
  for index := uint(FARMER); index <= CABBAGE; index++ {if !b.Test(index) {fmt.Println(names[index])
    }
  }

  fmt.Println("河右岸：")
  for index := uint(FARMER); index <= CABBAGE; index++ {if b.Test(index) {fmt.Println(names[index])
    }
  }
  fmt.Println("=======================")
}

func PrintMove(cur, next *bitset.BitSet) {for index := uint(WOLF); index <= CABBAGE; index++ {if cur.Test(index) != next.Test(index) {if !cur.Test(FARMER) {fmt.Printf("农夫将【%s】从河左岸带到河右岸 \n", names[index])
      } else {fmt.Printf("农夫将【%s】从河右岸带到河左岸 \n", names[index])

      }
      return
    }
  }

  if !cur.Test(FARMER) {fmt.Println("农夫单独从河左岸到河右岸")
  } else {fmt.Println("农夫单独从河右岸到河左岸")
  }
}

func PrintPath(path []*bitset.BitSet) {cur := path[0]
  PrintState(cur)

  for i := 1; i < len(path); i++ {next := path[i]
    PrintMove(cur, next)
    PrintState(next)
    cur = next
  }
}

运行：

=======================
河左岸：农夫
狼
羊
白菜

河右岸：=======================
农夫将【羊】从河左岸带到河右岸
=======================
河左岸：狼
白菜

河右岸：农夫
羊
=======================
农夫单独从河右岸到河左岸
=======================
河左岸：农夫
狼
白菜

河右岸：羊
=======================
农夫将【狼】从河左岸带到河右岸
=======================
河左岸：白菜

河右岸：农夫
狼
羊
=======================
农夫将【羊】从河右岸带到河左岸
=======================
河左岸：农夫
羊
白菜

河右岸：狼
=======================
农夫将【白菜】从河左岸带到河右岸
=======================
河左岸：羊

河右岸：农夫
狼
白菜
=======================
农夫单独从河右岸到河左岸
=======================
河左岸：农夫
羊

河右岸：狼
白菜
=======================
农夫将【羊】从河左岸带到河右岸
=======================
河左岸：河右岸：农夫
狼
羊
白菜
=======================

即农夫操作过程为：将羊带到右岸 -> 单独返回 -> 将白菜带到右岸 -> 再将羊带回左岸 -> 带上狼到右岸 -> 单独返回 -> 最初将羊带到右岸 -> 实现。

仿佛间接应用位运算就能够了，为什么要应用 bitset 库呢？

因为通用，下面列举的两个例子都是很小的整数值，如果整数值超过 64 位，咱们必然要通过切片来存储。此时手写操作就十分不便了，而且容易出错。

库的劣势体现在：

足够通用
继续优化
大规模应用

只有对外提供的接口放弃不变，它能够始终优化外部实现。尽管咱们也能够做，然而费时费力。而且有些优化波及到比较复杂的算法，本人实现的难度较高且易错。

有一个很典型的例子，求一个 uint64 的二进制示意中 1 的数量（popcnt，或 population count）。实现的办法有很多。

最间接的，咱们一位一位地统计：

func popcnt1(n uint64) uint64 {
  var count uint64

  for n > 0 {
    if n&1 == 1 {count++}

    n >>= 1
  }

  return count
}

思考空间换工夫，咱们能够事后计算 0-255 这 256 个数字的二进制示意中 1 的个数，而后每 8 位计算一次，可能将计算次数缩小到之前的 1/8。这也是规范库中的做法：

const pop8tab = ""+"\x00\x01\x01\x02\x01\x02\x02\x03\x01\x02\x02\x03\x02\x03\x03\x04"+"\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05"+"\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05"+"\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06"+"\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05"+"\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06"+"\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06"+"\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07"+"\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05"+"\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06"+"\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06"+"\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07"+"\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06"+"\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07"+"\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07"+"\x04\x05\x05\x06\x05\x06\x06\x07\x05\x06\x06\x07\x06\x07\x07\x08"

func popcnt2(n uint64) uint64 {
  var count uint64

  for n > 0 {count += uint64(pop8tab[n&0xff])
    n >>= 8
  }

  return count
}

最初是 bitset 库中的算法：

func popcnt3(x uint64) (n uint64) {x -= (x >> 1) & 0x5555555555555555
  x = (x>>2)&0x3333333333333333 + x&0x3333333333333333
  x += x >> 4
  x &= 0x0f0f0f0f0f0f0f0f
  x *= 0x0101010101010101
  return x >> 56
}

对以上三种实现进行性能测试：

goos: windows
goarch: amd64
pkg: github.com/darjun/go-daily-lib/bitset/popcnt
cpu: Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
BenchmarkPopcnt1-8         52405             24409 ns/op
BenchmarkPopcnt2-8        207452              5443 ns/op
BenchmarkPopcnt3-8       1777320               602 ns/op
PASS
ok      github.com/darjun/go-daily-lib/bitset/popcnt    4.697s

popcnt3 绝对 popcnt1 有 40 倍的性能晋升。在学习上咱们能够本人尝试造轮子，以此来加深本人对技术的了解。然而在工程上，通常更偏向于应用稳固的、高效的库。

本文借着 bitset 库介绍了位汇合的应用。并且利用 bitset 解决了农夫过河问题。最初咱们探讨了为什么要应用库？

大家如果发现好玩、好用的 Go 语言库，欢送到 Go 每日一库 GitHub 上提交 issue😄

我发现人的惰性切实是太可怕了。尽管这半年来没写文章一开始是因为工作上的起因，起初单纯是因为惯性，因为懒。而且总是“装着很忙”来回避须要花工夫、花精力的事件。在这种想动又不想动的角逐之间，工夫就这么一晃而过。

咱们总是在埋怨没有工夫，没有工夫。但认真想想，认真算算，咱们花在刷短视频，玩游戏上的工夫其实并不少。

上周我在阮一峰老师的周刊上看到一篇文章《人生不短》，看了之后深有触动。人总该有所保持，生存才有意义。

bitset GitHub：github.com/bits-and-blooms/bitset
Go 每日一库 GitHub：https://github.com/darjun/go-daily-lib

我的博客：https://darjun.github.io

欢送关注我的微信公众号【GoUpUp】，独特学习，一起提高~

关于godailylib:Go-每日一库之-bitset

简介

装置

应用

为什么要应用它？

总结

一点闲话

参考

我