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)
}
}
}
所以，對於words中的一個元素，要轉換為具體的值時：首先取到其位置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(' ')
}
fmt.Fprintf(&buf, "%d", bitNum*i+j)
}
}
}
buf.WriteByte('}')
return buf.String()
}
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
}
