Golang에서 비트 배열을 구현하는 방법(코드 예)

다음 Golang Tutorial 칼럼에서는 Golang의 비트 배열 구현 방법을 소개하겠습니다. 도움이 필요한 친구들에게 도움이 되길 바랍니다!

Go 언어비트 배열 구현을 위한 일반적인 방법

Go 언어의 컬렉션은 일반적으로 map[T]bool 형식으로 표현됩니다. 여기서 T는 요소 유형을 나타냅니다. 컬렉션은 매우 유연하기는 하지만 지도 유형으로 표현되지만 더 나은 방식으로 표현할 수 있습니다. 예를 들어, 데이터 흐름 분석 분야에서 집합 요소는 일반적으로 음수가 아닌 정수이고 집합에는 많은 요소가 포함되며 집합은 종종 합집합 및 교차 연산을 수행합니다. 이 경우 비트 배열이 더 많은 작업을 수행합니다. 이상적으로는 지도보다요.

비트 배열은 일반적으로 부호 없는 숫자 또는 "단어"라는 조각으로 표시됩니다. 각 요소의 각 비트는 집합의 값을 나타냅니다. 집합의 i번째 비트가 설정되면 집합에 요소 i가 포함되어 있다고 말합니다. 다음 프로그램은 간단한 비트 배열 유형을 보여주고 이 비트 배열에서 작동하는 세 가지 기능을 구현합니다.

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의 몫을 단어의 첨자를 사용하고 x%64에서 얻은 값을 단어 내 비트 위치로 사용합니다.

예를 들어, 숫자 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개의 값을 저장할 수 있습니다. , 즉 요소를 추가하는 것입니다. (0도 1비트를 차지하므로 64를 담아야 하며 첫 번째 요소는 0~63을 저장할 수 있다는 점에 유의하세요.)

즉, 단어로 된 요소의 경우 특정 값으로 변환하려는 경우: 먼저 해당 위치 i를 얻은 다음 64 * i를 캐리 수로 사용한 다음(10비트마다 캐리하는 것과 유사) 이 요소를 변환합니다. 이진수는 오른쪽에서 왼쪽으로 세어보면 자릿수가 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
}

지금까지 일반적인 메소드는 비트 배열 기능이 구현되었으며 이제 사용할 수 있습니다.

rreee

위 내용은 Golang에서 비트 배열을 구현하는 방법(코드 예)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!