Install and use of the bitset library related operations

Introduction

We all know that computers are based on binary, and bit operations are the basic operations of computers. The advantages of bit operations are obvious, and CPU instructions are natively supported and fast. Replacing the set of set data structures in a limited scenario can achieve unexpected effects.bitsetThe library implements bit sets and related operations, so it may be used as soon as possible.

Install

This article's code uses Go Modules.

Create a directory and initialize:

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

InstallbitsetLibrary:

$ go get -u /bits-and-blooms/bitset

use

The basic operations of bit sets are:

Check bit (Test): Check whether an index is 1. Analogy checks whether an element is in a collection
Set bit (Set): Set an index to 1. Analogy to add elements to a collection
Clear: Clear an index, set to 0. Analogy to remove elements from a collection
Flip: If an index is 1, set to 0, otherwise set to 1
Union: Two sets of bits perform and operate. Analogous to the set of
Intersection: Two bit sets perform the interception operation. Analogy of the intercourse of the set

Bit sets are generally used in scenarios where non-negative integers with decimal values. Take the simple sign-in in the game as an example. Many games have sign-in activities, the shortest ones are 7 days and the longest ones are 30 days. This is very suitable for using bit sets. The value of each bit indicates whether there is a check-in on the day corresponding to its index position.

type Player struct {
  sign *
}
func NewPlayer(sign uint) *Player {
  return &amp;amp;Player{
    sign: ([]uint64{uint64(sign)}),
  }
}
func (this *Player) Sign(day uint) {
  (day)
}
func (this *Player) IsSigned(day uint) bool {
  return (day)
}
func main() {
  player := NewPlayer(1) // Sign in on the first day  for day := uint(2); day &amp;lt;= 7; day++ {
    if (100)&amp;amp;1 == 0 {
      (day - 1)
    }
  }
  for day := uint(1); day &amp;lt;= 7; day++ {
    if (day - 1) {
      ("day:%d signed\n", day)
    }
  }
}

bitset provides a variety of ways to create BitSet objects.

First, zero values are available. If you don't know how many elements there are at the beginning, you can create them in this way:

var b

BitSet automatically resizes when set. If the length is known in advance, this value can be passed in when creating a BitSet, which can effectively avoid the overhead of automatic adjustment:

b := (100)

The bitset structure supports chain calls, and most methods return their own pointers, so you can write it like this:

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

Note that the index of bitset starts at 0.

I remember reading a question online before:

A farmer came to the river with a wolf, a sheep and a cabbage. He needs to take them to the other side with a boat. However, the ship can only accommodate the farmer himself and another thing (either a wolf, a sheep, or a cabbage). If the farmer is not present, the wolf will eat the sheep and the sheep will eat the cabbage. Please solve this problem for the farmer.

This is actually a state search problem, which can be solved by using backtracking. Farmer, wolf, sheep, and cabbage all have two states: on the left bank of the river (assuming that the farmer was on the left bank at the beginning) or on the right bank of the river. There is actually a ship's state here. Since the ship must be consistent with the farmer's state, there is no need to consider it extra. These states are easily represented by bit sets:

const (
  FARMER = iota
  WOLF
  SHEEP
  CABBAGE
)

Write a function to determine whether the state is legal. There are two states that are illegal:

The wolf and the sheep are on the same side, and they are not on the same side as the farmer. At this time the wolf will eat the sheep
The sheep and cabbage are on the same side and are not on the same side as the farmer. At this time the sheep will eat cabbage

func IsStateValid(state *) bool {
  if (WOLF) == (SHEEP) &amp;amp;&amp;amp;
    (WOLF) != (FARMER) {
    // The wolf and the sheep are on the same side, and they are not on the same side as the farmer    // Wolves will eat sheep, it's illegal    return false
  }
  if (SHEEP) == (CABBAGE) &amp;amp;&amp;amp;
    (SHEEP) != (FARMER) {
    // Sheep and cabbage are on the same side, and not on the same side as the farmer    // Sheep will eat cabbage, which is illegal    return false
  }
  return true
}

Next, write a search function:

func search(b *, visited map[string]struct{}) bool {
  if !IsStateValid(b) {
    return false
  }
  if _, exist := visited[()]; exist {
    // The status has been traversed    return false
  }
  if () == 4 {
    return true
  }
  visited[()] = struct{}{}
  for index := uint(FARMER); index &amp;lt;= CABBAGE; index++ {
    if (index) != (FARMER) {
      // Not with the farmer, you can't take it on the boat      continue
    }
    // Take it to the other side    (index)
    if index != FARMER {
      // If index is FARMER, it means nothing is included      (FARMER)
    }
    if search(b, visited) {
      return true
    }
    // Status recovery    (index)
    if index != FARMER {
      (FARMER)
    }
  }
  return false
}

Main function:

func main() {
  b := (4)
  visited := make(map[string]struct{})
  (search(b, visited))
}

At the beginning, all states are 0, and all states are 1 after reaching the other side, so() == 4It means that they have arrived on the other side. Since searching is blind, there may be an infinite cycle: this time the farmer takes the sheep to the other side and brings it back from the other side next time. So we need to deduplicate the state.()Returns the string representation of the current set of bits, and we use this to determine whether the state is repeated.

for loop try to bring various items in turn, or nothing. Drive the search process.

If you want to get the correct action sequence of the farmer, you can add a parameter to search and record the operation of each step:

func search(b *, visited map[string]struct{}, path *[]*) bool {
  // Record path  *path = append(*path, ())
  if () == 4 {
    return true
  }
  // ...
  *path = (*path)[:len(*path)-1]
  return false
}
func main() {
  b := (4)
  visited := make(map[string]struct{})
  var path []*
  if search(b, visited, &amp;path) {
    PrintPath(path)
  }
}

If the solution is found, print it:

var names = []string{"farmer", "Wolf", "sheep", "Chinese cabbage"}
func PrintState(b *) {
  ("=======================")
  ("Left Bank of the River:")
  for index := uint(FARMER); index &lt;= CABBAGE; index++ {
    if !(index) {
      (names[index])
    }
  }
  ("Right Bank of the River:")
  for index := uint(FARMER); index &lt;= CABBAGE; index++ {
    if (index) {
      (names[index])
    }
  }
  ("=======================")
}
func PrintMove(cur, next *) {
  for index := uint(WOLF); index &lt;= CABBAGE; index++ {
    if (index) != (index) {
      if !(FARMER) {
        ("The farmer brings [%s] from the left bank of the river to the right bank of the river\n", names[index])
      } else {
        ("The farmer brings [%s] from the right bank of the river to the left bank of the river\n", names[index])
      }
      return
    }
  }
  if !(FARMER) {
    ("The farmer goes from the left bank of the river to the right bank of the river alone")
  } else {
    ("The farmer goes from the right bank of the river to the left bank of the river alone")
  }
}
func PrintPath(path []*) {
  cur := path[0]
  PrintState(cur)
  for i := 1; i &lt; len(path); i++ {
    next := path[i]
    PrintMove(cur, next)
    PrintState(next)
    cur = next
  }
}

Running results:

=======================
Left bank of the river:
farmer
Wolf
sheep
Chinese cabbage

Right bank of the river:
=======================
The farmer takes the [sheep] from the left bank of the river to the right bank of the river
=======================
Left bank of the river:
Wolf
Chinese cabbage

Right bank of the river:
farmer
sheep
=======================
The farmer alone from the right bank of the river to the left bank of the river
=======================
Left bank of the river:
farmer
Wolf
Chinese cabbage

Right bank of the river:
sheep
=======================
The farmer takes the [wolf] from the left bank of the river to the right bank of the river
=======================
Left bank of the river:
Chinese cabbage

Right bank of the river:
farmer
Wolf
sheep
=======================
The farmer takes the [sheep] from the right bank of the river to the left bank of the river
=======================
Left bank of the river:
farmer
sheep
Chinese cabbage

Right bank of the river:
Wolf
=======================
The farmer brings [cabbage] from the left bank of the river to the right bank of the river
=======================
Left bank of the river:
sheep

Right bank of the river:
farmer
Wolf
Chinese cabbage
=======================
The farmer alone from the right bank of the river to the left bank of the river
=======================
Left bank of the river:
farmer
sheep

Right bank of the river:
Wolf
Chinese cabbage
=======================
The farmer takes the [sheep] from the left bank of the river to the right bank of the river
=======================
Left bank of the river:

Right bank of the river:
farmer
Wolf
sheep
Chinese cabbage
=======================

That is, the farmer's operation process is: take the sheep to the right bank -> return alone -> take the cabbage to the right bank -> then bring the sheep back to the left bank -> take the wolf to the right bank -> return alone -> finally take the sheep to the right bank -> complete.

Why use it?

It seems that just use bit operations directly, why use the bitset library?

Because it is general, the two examples listed above are small integer values. If the integer value exceeds 64 bits, we must store it through slices. At this time, handwriting operations are very inconvenient and errors are prone to occur.

The advantages of the library are reflected in:

Enough universal
Continuous optimization
Large-scale use

As long as the interface provided to the outside remains unchanged, it can always optimize the internal implementation. Although we can do it, it is time-consuming and labor-intensive. Moreover, some optimizations involve relatively complex algorithms, which are more difficult to implement and are prone to errors.

There is a very typical example, find the number of 1 in a binary representation of uint64 (popcnt, or population count). There are many ways to implement it.

The most direct thing is that we count one by one:

func popcnt1(n uint64) uint64 {
  var count uint64
  for n > 0 {
    if n&1 == 1 {
      count++
    }
    n >>= 1
  }
  return count
}

Considering the space-for-time time, we can pre-calculate the number of 1 in the binary representation of these 256 numbers 0-255, and then calculate it every 8 bits, which may reduce the number of calculations to 1/8 of the previous one. This is also what is done in the standard library:

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
}

Finally, there is the algorithm in the bitset library:

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
}

Perform performance testing of the above three implementations:

goos: windows
goarch: amd64
pkg: /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      /darjun/go-daily-lib/bitset/popcnt    4.697s

popcnt3 has a 40-fold performance improvement over popcnt1. In learning, we can try to build wheels by ourselves to deepen our understanding of technology. However, in engineering, stable and efficient libraries are usually preferred.

Summarize

This article uses the bitset library to introduce the use of bitsets. And applying bitset solves the problem of farmers crossing the river. Finally, we discussed why we should use libraries?

If you find a fun and useful Go language library, welcome to submit an issue on the Go daily library GitHub

A little gossip

I found that human laziness is really terrible. Although I haven't written an article in the past six months at first because of work reasons, but later it's simply because of inertia and laziness. And they always "pretend to be very busy" to escape things that require time and energy. In this kind of competition that wants to move but doesn't want to move, time flies by.

We always complain about not having time, not having time. But if you think about it carefully and calculate carefully, we actually spend a lot of time playing games when we watch short videos.

Last week, I saw an article "Life is Not Short" in Teacher Ruan Yifeng's weekly magazine. I was deeply touched after reading it. People should always stick to it before life can be meaningful.

refer to

bitset GitHub：/bits-and-blooms/bitset
Go daily library GitHub:/darjun/go-daily-lib

The above is the detailed content of the installation and use of the bitset library related to the Go bitset library. For more information about the Go bitset library, please pay attention to my other related articles!