Битовый вектор

В посте О битовых операциях были рассмотрены логические побитовые операции и побитовые сдвиги. В качестве примеров были взяты битовые флаги и множества.
Если применения битовых флагов вообщем то понятно, то для множества необходима структура данных и набор алгоритмов по работе с ней.
В книге Донован А. Керниган Б. - Язык программирования Go приведен пример битового вектора. Такая структура хорошо подходит для множества небольших положительных чисел над которым часто проводят операции объединения, пересечения, разность и пр.
Реализуем на Go структуру и основные методы.

Тип вектора имеет одно поле. Срез беззнаковых целочисленных значений, каждый бит которых представляет возможный элемент множества.

type IntSet struct {
       words []uint
}

Нам понадобится узнать размер слова

const sizeWord = 32 << (^uint(0) >> 63)

На 32 разрядных платформах sizeWord будет равен 32, на 64 соответственно 64.
Когда не часто работаешь с битовыми операциями может показаться что тут что то страшное и не понятное, но если разбить на 3 операции, то становится все достаточно просто.

Методы для работы с векторов

// Add добавляет неотрицательное значение x в множество
func (s *IntSet) Add(x int) {
 word, bit := x/sizeWord, uint(x%sizeWord)
 for word >= len(s.words) {
  s.words = append(s.words, 0)
 }
 s.words[word] |= 1 << bit
}

Предположим у нас sizeWord = 64 и хотим добавить элемент 10

• Находим индекс среза в котором должен хранится бит и номер бита от 0 до 64.
• word = 10 / 64=0 -индекс
• bit = 10 % 64 = 10
• Нужно найти элемент с индексом 0 и выставить ему 10й бит
• Если такого элемента в срезе нет, то добавляем его.
• Операцией ИЛИ выставляем 10 бит

// Has указывает, содержит ли множество неотрицательное значение x
func (s *IntSet) Has(x int) bool {
 word, bit := x/sizeWord, uint(x%sizeWord)
 return word < len(s.words) && s.words[word]&(1<<bit) != 0
}

Так же как в Add находим word и bit
Если после операции И число не равно 0, то бит включен и соответственно элемент содержится в множестве

// Remove удаляет x из множества
func (s *IntSet) Remove(x int) {
 word, bit := x/sizeWord, uint(x%sizeWord)
 if word < len(s.words) {
  s.words[word] = s.words[word] &^ (1 << bit)
 }
}

С помощью операции И НЕ снимаем нужный бит

// Len возвращает количество элементов в множестве
func (s *IntSet) Len() int {
 var cnt uint
 for _, word := range s.words {
  for word != 0 {
   cnt += word & 1
   word = word >> 1
  }
 }
 return int(cnt)
}

Нужно посчитать кол-во включенных битов в каждом слове. Тут приведен один из алгоритмов, он не самый эффективный, но достаточно простой. Проверяем младший бит и сдвигаем вправо.
Так же есть вариант добавить в IntSet поле cnt и актуализировать его при изменении среза, а функцию Len использовать как getter для него.

//String возвращает множество как строку вида {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 < sizeWord; j++ {
   if word&(1<<uint(j)) != 0 {
    if buf.Len() > len("{") {
     buf.WriteByte(' ')
    }
    fmt.Fprintf(&buf, "%d", sizeWord*i+j)
   }
  }
 }
 buf.WriteByte('}')
 return buf.String()
}

Используется тот же поиск включенных битов как и в Len. Немного иначе реализован.

// UnionWith делает множество s равным обьединению множеств s и 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)
  }
 }
}

С помощью ИЛИ включаем нужные биты

// UnionWith делает множество s равным обьединению множеств s и 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)
  }
 }
}

С помощью И оставляем пересечения

// DifferenceWith делат множество s равным разности s и t
func (s *IntSet) DifferenceWith(t *IntSet) {
 for i := range s.words {
  if i < len(t.words) {
   s.words[i] = s.words[i] &^ t.words[i]
  } else {
   break
  }
 }
}

С помощью И НЕ оставляем разность

// SymmetricDifference делает множество s равным
// симетрической разности s и t.
// Симметричная разность двух множеств содержит элементы,
// имеющиеся в одном из множеств, но не в обоих одновременно
func (s *IntSet) SymmetricDifference(t *IntSet) {
 for i, tword := range t.words {
  if i < len(s.words) {
   s.words[i] = s.words[i] ^ tword
  } else {
   s.words = append(s.words, tword)
  }
 }
}

Пример использования исключающего ИЛИ


Плюс набор полезных методов

// Elems возвращает срез []int, содержащий элементы множества
func (s *IntSet) Elems() []int {
 var list []int
 for i, word := range s.words {
  for j := 0; word != 0; j++ {
   if (word & 1) == 1 {
    list = append(list, (i*sizeWord + j))
   }
   word = word >> 1
  }
 }
 return list
}

// AddAll добавляет список значений в множество
func (s *IntSet) AddAll(list ...int) {
 for _, x := range list {
  s.Add(x)
 }
}

//Copy возвращает копию множества
func (s *IntSet) Copy() *IntSet {
 t := new(IntSet)
 t.words = append([]uint(nil), s.words...)
 return t
}

// Clear удаляет все элементы множества
func (s *IntSet) Clear() {
 s.words = nil
}