Skip to content

BitArray.md

Latest commit

 

History

History
104 lines (73 loc) · 5.26 KB

BitArray.md

File metadata and controls

104 lines (73 loc) · 5.26 KB

🔢 BitArray

Битовый массив для компактного хранения и моментальных манипуляций с булевыми значениями. 🚀

🔥 Основные методы

⚡ Методы имеют сложность O(1), если не сказано иное.

  • AllTrue() — проверяет, все ли биты равны true.
  • HasTrue() — проверяет, есть ли хотя бы один бит true.
  • TrueCount() — возвращает количество битов, равных true.
  • Flip(unsigned long long index) — инвертирует бит по указанному индексу.
  • Flip() — инвертирует все биты.
  • Set(unsigned long long index, bool value) — устанавливает значение бита по индексу.
  • Set(bool value) — устанавливает одно значение для всех битов. Сложность: O(n) (на деле O(n/64), где n - количество битов, так как итерация идет по словам unsigned long long, а не по битам).
  • Size() — возвращает количество битов.
  • IsTrue(unsigned long long index) — Возвращает булево значение бита.
  • ToString() — возвращает строковое представление массива (0/1). Операция затратная: O(n).
  • ToNumber() — преобразует массив битов в число (один бит - одна цифра). Операция затратная: O(n).

🛠️ Операторы

  • [] — доступ к биту по индексу (чтение или запись через BitReference). В этой коллекции отрицательная индексация не поддерживается.
  • bool() — возвращает true, если есть хотя бы один бит true (аналог HasTrue()).
  • << — выводит строковое представление через ToString().

🎯 Пример

#include "cs/types.h"

int main() {
    BitArray bits = {false, true, true, false, false}; // 01100
    
    bits.Set(true); // 11111
    bits[3] = false; // 11101
    
    bits.Flip(); // 00010
    std::cout << bits << std::endl; // 00010
    std::cout << bits.TrueCount() << std::endl; // 1
    return 0;
}

🔗 Работа с BitReference

Оператор [] для записи возвращает BitReference, позволяющий изменять бит. Для чтения используется operator[] const, возвращающий bool.

❓ Почему BitReference?

В C++ operator[] для изменения должен возвращать ссылку на элемент, но отдельный бит в unsigned long long нельзя представить как ссылку. Решение — BitReference, объект, который:

  • Хранит ссылку на слово и смещение бита.
  • Перегружает operator= для изменения бита.
  • Обеспечивает чтение через преобразование в bool.

Это позволяет интуитивно работать с битами, обходя ограничения языка.

BitArray bits(4);    // 0000
bits[2] = true;      // 0010
std::cout << bits[2]; // 1
#include "cs/types.h"

int main() {
    BitArray bits(4); // 0000
    
    bits[2] = true; // 0010
    std::cout << bits[2] << std::endl; // 1
    
    bits.Flip(2); // 0000
    std::cout << bits << std::endl; // 0000
    return 0;
}

💡 Особенности

  • Компактное хранение: Биты упакованы в массив unsigned long long (по 64 бита на слово), что минимизирует использование памяти.
  • Гибкая индексация: Доступ через [] интуитивен, с поддержкой чтения и записи.
  • Эффективность: Подсчёт TrueCount кэшируется, чтобы избежать лишних проходов по массиву.
  • Перегрузка оператора вывода: Через << выводится строка из 0 и 1.
  • Ограничения: BitReference не копируется, чтобы избежать неопределённого поведения. Для пользовательских операций с битами используйте Set или Flip.

🛠️ Внутренние детали

  • _numbers: Внутренний List<unsigned long long> хранит биты, разбитые на 64-битные слова.
  • _word_size: Размер слова (64 бита).
  • _bit_offset(pos): Вычисляет смещение бита внутри слова.
  • _word_index(pos): Вычисляет индекс слова для заданной позиции.
  • _isReversed: Флаг для отслеживания инверсии (чтобы не перебирать все биты).