So implementieren Sie ein Bit-Array in Golang (Codebeispiel)

藏色散人

Freigeben： 2020-08-11 13:21:55

nach vorne

3452 Leute haben es durchsucht

Die folgende Kolumne „Golang-Tutorial“ stellt Ihnen die Implementierungsmethode des Bit-Arrays in Golang vor. Ich hoffe, dass sie Freunden in Not hilfreich sein wird!

Go-Sprache So implementieren Sie ein Bit-Array in Golang (Codebeispiel) Gemeinsame Methoden zum Implementieren von Bit-Arrays

Sammlungen in der Go-Sprache werden im Allgemeinen in der Form von map[T]bool ausgedrückt, wobei T den Elementtyp darstellt. Sammlungen werden als Kartentypen dargestellt. Obwohl sie sehr flexibel sind, können wir sie besser ausdrücken. Im Bereich der Datenflussanalyse ist das Mengenelement beispielsweise normalerweise eine nicht negative Ganzzahl, die Menge enthält viele Elemente und die Menge führt häufig Vereinigungs- und Schnittoperationen aus. In diesem Fall führt das Bitarray mehr aus idealerweise als die Karte. Ein Bit-Array wird normalerweise durch eine vorzeichenlose Zahl oder ein Segment namens „Wort“ dargestellt. Jedes Bit jedes Elements stellt einen Wert in der Menge dar. Wenn das i-te Bit einer Menge gesetzt ist, sagen wir, dass die Menge das Element i enthält. Das folgende Programm zeigt einen einfachen Bit-Array-Typ und implementiert drei Funktionen zur Bearbeitung dieses Bit-Arrays:

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 << (^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)
		}
	}
}

Nach dem Login kopieren

Da jedes Wort 64 Binärbits hat, verwenden wir zum Lokalisieren des Bits von x den Quotienten von x/64 als Index des Wortes und verwenden Sie den durch x%64 erhaltenen Wert als Position des Bits innerhalb des Wortes.

Fügen Sie beispielsweise die Zahl 1 zum Bit-Array hinzu:

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}

Nach dem Login kopieren

Ähnlich gilt, wenn wir 66 zum Bit-Array hinzufügen:

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}

Nach dem Login kopieren

Bei Wörtern kann also jedes Element 64 Werte speichern. 64 ist ein Übertrag , also das Hinzufügen eines Elements. (Beachten Sie, dass 0 auch ein Bit belegt, sodass 64 übertragen werden muss und das erste Element 0-63 speichern kann.)

Wenn Sie also ein Element in Worten in einen bestimmten Wert umwandeln möchten: Ermitteln Sie zuerst seine Position i, verwenden Sie 64 * i als Anzahl der Überträge (ähnlich dem Übertrag alle 10 Ziffern) und konvertieren Sie dann dieses Element Bei Binärzahlen beträgt die Anzahl der Ziffern von rechts nach links 1, was bedeutet, dass es einen entsprechenden Wert gibt. Die Anzahl der Ziffern x+64 *i ist der Wert, den wir speichern.

Entsprechend kann es die folgende String()-Funktion geben

// String returns the set as a string of the form "{1 2 3}".
func (s *IntSet) String() string {
	var buf bytes.Buffer
	buf.WriteByte(&#39;{&#39;)
	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(&#39; &#39;)
				}
				fmt.Fprintf(&buf, "%d", bitNum*i+j)
			}
		}
	}
	buf.WriteByte(&#39;}&#39;)
	return buf.String()
}

Nach dem Login kopieren

Nachdem beispielsweise 1 und 66 zuvor gespeichert wurden, lautet der Konvertierungsprozess:

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

Nach dem Login kopieren

Andere Methodenfunktionen zum Implementieren von Bitarrays

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未出现在B
func (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没有出现在A
func (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
}

Nach dem Login kopieren

Bisher die gängigen Methoden von Bit-Arrays Die Funktion wurde implementiert und Sie können sie nun verwenden.

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
	}
}

Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonSo implementieren Sie ein Bit-Array in Golang (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!