Битовый массив - Bit array

Битовый массив (также известный как битовая карта , набор бит , битовая строка , или битового вектор ) представляет собой массив , что компактно хранит биты . Его можно использовать для реализации простой структуры набора данных . Битовый массив эффективен при использовании аппаратного параллелизма на битовом уровне для быстрого выполнения операций. Типичный битовый массив хранит kw битов, где w - количество битов в единице хранения, такой как байт или слово , а k - некоторое неотрицательное целое число. Если w не делит количество хранимых битов, некоторое пространство теряется из-за внутренней фрагментации .

Определение

Битовый массив - это отображение некоторого домена (почти всегда диапазона целых чисел) на значения в наборе {0, 1}. Значения можно интерпретировать как темный / светлый, отсутствующий / присутствующий, заблокированный / разблокированный, действительный / недействительный и т. Д. Дело в том, что возможных значений всего два, поэтому их можно хранить в одном бите. Как и в случае с другими массивами, доступом к одному биту можно управлять, применяя индекс к массиву. Предполагая, что его размер (или длина) равняется n битам, массив можно использовать для указания подмножества домена (например, {0, 1, 2, ..., n −1}), где 1 бит указывает наличие и 0-битное отсутствие номера в наборе. Эта структура данных набора использует около n / w слов пространства, где w - количество бит в каждом машинном слове . Независимо от того, указывает ли младший бит (слова) или самый старший бит на наименьшее число индекса, в значительной степени не имеет значения, но первый имеет тенденцию быть предпочтительным (на машинах с прямым порядком байтов ).

Основные операции

Хотя большинство машин не могут адресовать отдельные биты в памяти и не имеют инструкций по манипулированию отдельными битами, каждый бит в слове может быть выделен и обработан с помощью побитовых операций . Особенно:

  • ИЛИ можно использовать для установки бита в единицу: 11101010 ИЛИ 00000100 = 11101110
  • И может использоваться для установки бита в ноль: 11101010 И 11111101 = 11101000
  • И вместе с нулевым тестированием может использоваться, чтобы определить, установлен ли бит:
    11101010 И 00000001 = 00000000 = 0
    11101010 И 00000010 = 00000010 ≠ 0
  • XOR можно использовать для инвертирования или небольшого переключения:
    11101010 XOR 00000100 = 11101110
    11101110 XOR 00000100 = 11101010
  • НЕ может использоваться для инвертирования всех битов.
    НЕ 10110010 = 01001101

Чтобы получить битовую маску, необходимую для этих операций, мы можем использовать оператор битового сдвига, чтобы сдвинуть число 1 влево на соответствующее количество разрядов, а также побитовое отрицание, если необходимо.

Учитывая два битовых массива одинакового размера, представляющих множества, мы можем вычислить их объединение , пересечение и теоретико-множественную разницу, используя n / w простых битовых операций каждый (2 n / w для разницы), а также дополнение любого из:

for i from 0 to n/w-1
    complement_a[i] := not a[i]
    union[i]        := a[i] or b[i]
    intersection[i] := a[i] and b[i]
    difference[i]   := a[i] and (not b[i])

Если мы хотим перебрать биты битового массива, мы можем сделать это эффективно, используя дважды вложенный цикл, который перебирает каждое слово по одному. Требуются только n / w доступы к памяти:

for i from 0 to n/w-1
    index := 0    // if needed
    word := a[i]
    for b from 0 to w-1
        value := word and 1 ≠ 0
        word := word shift right 1
        // do something with value
        index := index + 1    // if needed

Оба этих образца кода демонстрируют идеальную локальность ссылки , которая впоследствии получит большой прирост производительности от кэша данных. Если строка кэша состоит из k слов, будет происходить только около n / wk промахов в кэше.

Более сложные операции

Как и в случае с символьными строками, легко определить длину , подстроку , лексикографическое сравнение , конкатенацию , обратные операции. Реализация некоторых из этих операций чувствительна к порядку байтов .

Население / Вес Хэмминга

Если мы хотим найти количество 1 бит в битовом массиве, иногда называемом подсчетом совокупности или весом Хэмминга, существуют эффективные алгоритмы без ветвлений, которые могут вычислить количество бит в слове, используя серию простых битовых операций. Мы просто запускаем такой алгоритм для каждого слова и ведем промежуточный итог. Подсчет нулей аналогичен. См. Статью о весах Хэмминга, где приведены примеры эффективной реализации.

Инверсия

Вертикальное переворачивание изображения с одним битом на пиксель или некоторые алгоритмы БПФ требуют переворачивания битов отдельных слов (так b31 b30 ... b0становится b0 ... b30 b31). Когда эта операция недоступна в процессоре, все еще можно продолжить последовательными проходами, в этом примере на 32 бита:

exchange two 16-bit halfwords
exchange bytes by pairs (0xddccbbaa -> 0xccddaabb)
...
swap bits by pairs
swap bits (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1)

The last operation can be written ((x&0x55555555) << 1) | (x&0xaaaaaaaa) >> 1)).

Найдите первый

Операция find first set или find first one идентифицирует индекс или позицию 1-бита с наименьшим индексом в массиве и имеет широко распространенную аппаратную поддержку (для массивов не более одного слова) и эффективные алгоритмы для его вычисления. Когда очередь с приоритетом хранится в битовом массиве, функция find first может использоваться для определения элемента с наивысшим приоритетом в очереди. Чтобы расширить поиск первого слова размером с более длинные массивы, можно найти первое ненулевое слово, а затем выполнить команду find first для этого слова. Связанные операции поиска первого нуля , подсчета начальных нулей , подсчета начальных нулей , подсчета конечных нулей , подсчета конечных единиц и логической базы 2 (см. Поиск первого набора ) также могут быть расширены до битового массива простым способом.

Сжатие

Битовый массив - это наиболее плотное хранилище для «случайных» битов, то есть где каждый бит с равной вероятностью равен 0 или 1, и каждый из них независим. Но большинство данных не случайны, поэтому их можно хранить более компактно. Например, данные типичного изображения факса не случайны и могут быть сжаты. Кодирование длин серий обычно используется для сжатия этих длинных потоков. Однако к большинству форматов сжатых данных не так легко получить произвольный доступ; Кроме того, слишком агрессивно сжимая битовые массивы, мы рискуем потерять преимущества из-за параллелизма на битовом уровне ( векторизации ). Таким образом, вместо сжатия битовых массивов как потоков битов мы могли бы сжимать их как потоки байтов или слов (см. Индекс Bitmap (сжатие) ).

Преимущества и недостатки

Битовые массивы, несмотря на их простоту, имеют ряд заметных преимуществ перед другими структурами данных для тех же проблем:

  • Они чрезвычайно компактны; никакие другие структуры данных не могут хранить n независимых частей данных в n / w словах.
  • Они позволяют хранить небольшие массивы битов и манипулировать ими в наборе регистров в течение длительных периодов времени без доступа к памяти.
  • Благодаря своей способности использовать параллелизм на уровне битов, ограничивать доступ к памяти и максимально использовать кэш данных , они часто превосходят многие другие структуры данных на практических наборах данных, даже если они более асимптотически эффективны.

Однако битовые массивы - это не решение всего. Особенно:

  • Без сжатия они представляют собой бесполезные структуры данных для разреженных наборов (с небольшим количеством элементов по сравнению с их диапазоном) как во времени, так и в пространстве. Для таких приложений следует рассматривать сжатые битовые массивы, массивы Джуди , попытки или даже фильтры Блума .
  • Доступ к отдельным элементам может быть дорогостоящим, и его трудно выразить на некоторых языках. Если произвольный доступ более распространен, чем последовательный, и массив относительно невелик, байтовый массив может быть предпочтительнее на машине с байтовой адресацией. Однако массив слов, вероятно, не оправдан из-за огромных накладных расходов на пространство и дополнительных пропусков кеша, которые он вызывает, если только машина не имеет только адресацию слов.

Приложения

Из-за своей компактности битовые массивы находят множество применений в областях, где пространство или эффективность имеют решающее значение. Чаще всего они используются для представления простой группы логических флагов или упорядоченной последовательности логических значений.

Битовые массивы используются для очередей с приоритетом , где бит с индексом k устанавливается тогда и только тогда, когда k находится в очереди; эта структура данных используется, например, ядром Linux и сильно выигрывает от аппаратной операции поиска первого нуля.

Битовые массивы могут использоваться для выделения страниц памяти , индексных дескрипторов , секторов диска и т. Д. В таких случаях может использоваться термин битовая карта . Однако этот термин часто используется для обозначения растровых изображений , в которых может использоваться несколько битов на пиксель .

Еще одно применение битовых массивов - это фильтр Блума , структура данных вероятностного набора, которая может хранить большие наборы в небольшом пространстве в обмен на небольшую вероятность ошибки. Также возможно построить вероятностные хеш-таблицы на основе битовых массивов, которые принимают либо ложные срабатывания, либо ложные отрицания.

Битовые массивы и операции с ними также важны для построения лаконичных структур данных , которые используют минимально возможное пространство. В этом контексте становятся важными такие операции, как поиск n- го 1-го бита или подсчет количества 1-го бит до определенной позиции.

Битовые массивы также являются полезной абстракцией для изучения потоков сжатых данных, которые часто содержат элементы, занимающие части байтов или не выровненные по байтам. Например, сжатое кодовое представление Хаффмана одного 8-битного символа может иметь длину от 1 до 255 бит.

При поиске информации битовые массивы являются хорошим представлением для списков рассылки очень часто встречающихся терминов. Если мы вычислим промежутки между соседними значениями в списке строго возрастающих целых чисел и закодируем их с использованием унарного кодирования , результатом будет битовый массив с 1 битом в n- й позиции тогда и только тогда, когда n находится в списке. Подразумеваемая вероятность разрыва n равна 1/2 n . Это также частный случай кодирования Голомба, когда параметр M равен 1; этот параметр обычно выбирается только тогда, когда -log (2- p ) / log (1- p ) ≤ 1, или примерно этот термин встречается как минимум в 38% документов.

Языковая поддержка

Язык программирования APL полностью поддерживает битовые массивы произвольной формы и размера как логический тип данных, отличный от целых чисел. Все основные реализации ( Dyalog APL, APL2, APL Next, NARS2000, Gnu APL и т. Д.) Плотно упаковывают биты в машинное слово любого размера. Доступ к битам можно получить индивидуально через обычную нотацию индексации (A [3]), а также через все обычные примитивные функции и операторы, где они часто используются с использованием специального алгоритма, такого как суммирование битов посредством поиска байтов в таблице. .

В языке программирования C «сек битовых полей , псевдо-объекты , найденные в структурах с размером , равным некоторому числу битов, в действительности являются небольшими битовыми массивами; они ограничены тем, что не могут охватывать слова. Хотя они предоставляют удобный синтаксис, доступ к битам по-прежнему осуществляется с помощью побайтовых операторов на большинстве машин, и они могут быть определены только статически (как и статические массивы C, их размеры фиксируются во время компиляции). Программисты на C также часто используют слова как небольшие битовые массивы и обращаются к ним с помощью битовых операторов. Широко доступный заголовочный файл xtrapbits.h, включенный в систему X11 , представляет собой «переносимый способ для систем определять манипуляции с битовыми полями массивов битов». Более пояснительная описание вышеупомянутого подхода можно найти в comp.lang.c FAQ .

В C ++ , хотя отдельные bools обычно занимают то же пространство, что и байт или целое число, тип STLvector<bool> является частичной специализацией шаблона, в которой биты упаковываются в целях оптимизации эффективности использования пространства. Поскольку байты (а не биты) являются наименьшей адресуемой единицей в C ++, оператор [] не возвращает ссылку на элемент, а вместо этого возвращает ссылку прокси . Это может показаться второстепенным, но это означает, что vector<bool>это не стандартный контейнер STL, поэтому его использование vector<bool>обычно не рекомендуется. Другой уникальный класс STL bitsetсоздает вектор битов, фиксированный в определенном размере во время компиляции, и по своему интерфейсу и синтаксису больше напоминает идиоматическое использование слов как битовых наборов программистами на C. Он также обладает некоторыми дополнительными возможностями, такими как возможность эффективного подсчета количества установленных битов. Библиотеки Boost C ++ предоставляют dynamic_bitsetкласс, размер которого указывается во время выполнения.

Язык программирования D предоставляет битовые массивы в своей стандартной библиотеке Phobos в формате std.bitmanip. Как и в C ++, оператор [] не возвращает ссылку, поскольку отдельные биты не имеют прямой адресации на большинстве аппаратных средств, а вместо этого возвращает bool.

В Java класс BitSetсоздает битовый массив, который затем обрабатывается функциями, названными в честь побитовых операторов, знакомых программистам на C. В отличие от bitsetC ++, Java BitSetне имеет состояния «размер» (он имеет фактически бесконечный размер, инициализированный 0 битами); бит может быть установлен или протестирован по любому индексу. Кроме того, существует класс EnumSet, который представляет набор значений перечислимого типа внутри как битовый вектор, как более безопасную альтернативу битовым полям.

.NET Framework поставляет BitArrayкласс коллекции. Он хранит биты с использованием массива типа int(каждый элемент в массиве обычно представляет 32 бита). Класс поддерживает произвольный доступ и побитовые операторы, его можно повторять, а его Lengthсвойство можно изменять, увеличивая или усекая его.

Хотя Standard ML не поддерживает битовые массивы, Standard ML из Нью-Джерси имеет расширение, BitArrayструктуру, в своей библиотеке SML / NJ. Он не имеет фиксированного размера и поддерживает операции с наборами и битовые операции, включая, что необычно, операции сдвига.

В Haskell в настоящее время также отсутствует стандартная поддержка поразрядных операций, но и GHC, и Hugs предоставляют Data.Bitsмодуль с различными побитовыми функциями и операторами, включая операции сдвига и поворота, а «распакованный» массив над логическими значениями может использоваться для моделирования битового массива, хотя это не поддерживает прежний модуль.

В Perl строки могут использоваться как расширяемые битовые массивы. Им можно управлять с помощью обычных побитовых операторов ( ~ | & ^), а отдельные биты можно проверять и устанавливать с помощью функции vec .

В Ruby вы можете получить доступ (но не установить) бит целого числа ( Fixnumили Bignum) с помощью оператора скобки ( []), как если бы это был массив бит.

Библиотека Apple Core Foundation содержит структуры CFBitVector и CFMutableBitVector .

PL / I поддерживает массивы битовых строк произвольной длины, которая может быть фиксированной или переменной длины. Элементы массива могут быть выровнены - каждый элемент начинается на границе байта или слова - или невыровненными - элементы сразу следуют друг за другом без заполнения.

PL / pgSQL и PostgreSQL SQL поддерживают битовые строки как собственный тип. Существует два типа битов SQL: и , где - положительное целое число. bit(n)bit varying(n)n

Языки описания оборудования, такие как VHDL , Verilog и SystemVerilog, изначально поддерживают битовые векторы, поскольку они используются для моделирования таких элементов хранения, как триггеры , аппаратные шины и аппаратные сигналы в целом. В языках проверки оборудования, таких как OpenVera , e и SystemVerilog , битовые векторы используются для выборки значений из моделей оборудования и для представления данных, которые передаются на оборудование во время моделирования.

Common Lisp предоставляет одномерную bit-vectorреализацию как частный случай встроенного array, действуя в двойном качестве как класс и спецификатор типа. Будучи производным от массива, он полагается на общую make-arrayфункцию, которая должна быть сконфигурирована с типом элемента bit, который дополнительно позволяет обозначать битовый вектор как динамически изменяемый размер. bit-vector, Однако, не бесконечна в степени. Существует более ограниченный simple-bit-vectorтип, который явно исключает динамические характеристики. Битовые векторы представлены в виде макроса считывателя и могут быть сконструированы в более сжатой форме . В дополнение к общим функциям, применимым ко всем массивам, существуют специальные операции для битовых векторов. Одиночные биты могут быть доступны и изменены с помощью и функции и обширное число логических операций поддерживаются. #*bitsbitsbit

Смотрите также

использованная литература

внешние ссылки