다음 Golang Tutorial 칼럼에서는 Golang의 비트 배열 구현 방법을 소개하겠습니다. 도움이 필요한 친구들에게 도움이 되길 바랍니다!
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 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(' ')
}
fmt.Fprintf(&buf, "%d", bitNum*i+j)
}
}
}
buf.WriteByte('}')
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
