以下由Golang教學欄位來介紹Golang中Bit陣列的實作方法，希望對需要的朋友有幫助！
Go語言裡的集合一般會用map[T]bool這種形式來表示，T代表元素類型。集合用map類型來表示雖然非常靈活，但我們可以以更好的形式來表示它。例如在資料流分析領域，集合元素通常是一個非負整數，集合會包含很多元素，並且集合會經常進行並集、交集操作，這種情況下，bit數組會比map表現更加理想。
一個bit陣列通常會用一個無符號數或稱為「字」的slice來表示，每一個元素的每一位都表示集合裡的一個值。當集合的第i位元被設定時，我們才說這個集合包含元素i。下面的這個程式展示了一個簡單的bit數組類型，並且實作了三個函數來對這個bit數組來進行操作：
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的bit位，我們用了x/64的商作為字的下標，並且用xd得到的值作為這個字內的bit的所在位置。
例如，對於數字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}所以，對於words，每個元素可儲存的值有64個，每超過64個則進位，即增加一個元素。 （注意，0也佔了一位，所以64才要進位，第一個元素可儲存0-63）。
所以，對於words中的一個元素，要轉換為具體的值時：首先取到其位置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
}至此，位元數組的常用方法函數都已實現，現在可以來使用它。
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
}
}
以上是Golang中Bit數組如何實作（程式碼範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
