Golang で Bit 配列を実装する方法 (コード例)

次のコラム Golang チュートリアル では、Golang での Bit 配列の実装方法を紹介しますので、困っている方の参考になれば幸いです。

Go 言語ビット配列を実装するための一般的なメソッド

Go 言語のコレクションでは通常、map[T]bool In を使用します。この形式では、T は要素の種類を表します。コレクションはマップ タイプを使用して表現され、非常に柔軟ですが、より良い形式で表現することもできます。たとえば、データ フロー分析の分野では、セット要素は通常非負の整数であり、セットには多くの要素が含まれ、セットでは和集合演算や交差演算が実行されることがよくあります。この場合、ビット配列はより多くの演算を実行します。理想的には地図よりも。

ビット配列は通常、符号なしの数値または「ワード」と呼ばれるスライスで表され、各要素の各ビットがセット内の値を表します。セットの i 番目のビットが設定されている場合、そのセットには要素 i が含まれていると言います。次のプログラムは、単純なビット配列タイプを示し、このビット配列を操作する 3 つの関数を実装しています。

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

各ワードには 64 バイナリ ビットがあるため、x ビットを見つけるには、x/64 の商を使用します。をワードの添え字として使用し、xd で取得した値をワード内のビットの位置として使用します。

たとえば、数値 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}

つまり、単語については各要素に格納できる値は 64 個あり、値が 64 を超えるたびに桁上げ、つまり要素が追加されます。 (0 も 1 ビットを占めるため、64 を運ぶ必要があり、最初の要素には 0 ～ 63 を格納できることに注意してください)。

したがって、単語内の要素について、特定の値に変換したい場合は、まずその位置 i を取得し、桁上げの数として 64 * i を使用します (10 桁ごとに桁上げするのと同様)。 then この要素を 2 進数に変換します 右から左に数えると桁数が 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(&#39; &#39;)
				}
				fmt.Fprintf(&buf, "%d", bitNum*i+j)
			}
		}
	}
	buf.WriteByte(&#39;}&#39;)
	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未出现在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
}

これで、ビット配列の共通メソッド関数が実装され、使用できるようになりました。

えええええ

以上がGolang で Bit 配列を実装する方法 (コード例)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。