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

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

Определение

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

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

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

  • ИЛИ можно использовать для установки бита в единицу: 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 влево на соответствующее количество разрядов, а также побитовое отрицание если необходимо.

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

для i от 0 до n / w-1 complement_a [i]: = не [i] union [i]: = a [i] или b [i] пересечение [i]: = a [i] и b [i] ] разность [i]: = a [i] и (не b [i])

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

для i от 0 до n / w-1 index: = 0 // если необходимо слово: = a [i] для b от 0 до w-1 значение: = слово и 1 ≠ 0 слово: = сдвиг слова вправо 1 // сделаем что-нибудь со значением index: = index + 1 // если необходимо

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

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

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

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

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

Инверсия

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

обмен два 16кусочек полусловаобмен байты к пары (0xddccbbaa -> 0xccddaabb)...замена биты к парызамена биты (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1)В последний операция может быть написано ((Икс&0x55555555)<<1) | (Икс&0xaaaaaaaa)>>1)).

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

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

Сжатие

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Apple Основной фундамент библиотека содержит CFBitVector и CFMutableBitVector конструкции.

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

PL / pgSQL и поддержка SQL в PostgreSQL битовые строки как родной тип. Есть два типа битов SQL: кусочек(п) и немного меняется (п), куда п положительное целое число.[5]

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

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

Рекомендации

  1. ^ "Ресурсы технического архива SGI.com удалены". SGI. 2 января 2018.
  2. ^ "dynamic_bitset <Блок, Распределитель> - 1.66.0". www.boost.org.
  3. ^ "perlop - perldoc.perl.org". perldoc.perl.org.
  4. ^ "vec - perldoc.perl.org". perldoc.perl.org.
  5. ^ https://www.postgresql.org/docs/current/datatype-bit.html

внешняя ссылка