Войти
A битовый массив (также известный как битовая карта, набор бит, битовая строка или битовый вектор ) - это структура данных массива, в которой компактно хранятся биты. Его можно использовать для реализации простой структуры данных. Битовый массив эффективен при использовании аппаратного параллелизма на битовом уровне для быстрого выполнения операций. Типичный битовый массив хранит kw битов, где w - количество битов в единице хранения, например, byte или word, а k - некоторое неотрицательное целое число. Если w не делит количество хранимых битов, некоторое пространство теряется из-за внутренней фрагментации.
Битовый массив - это отображение некоторого домена (почти всегда диапазона целых чисел) на значения в наборе {0, 1}. Значения могут интерпретироваться как темный / светлый, отсутствующий / присутствующий, заблокированный / разблокированный, действительный / недействительный и т. Д. Дело в том, что возможных значений всего два, поэтому их можно хранить в одном бите. Как и в случае с другими массивами, доступом к одному биту можно управлять, применяя индекс к массиву. Предполагая, что его размер (или длина) равняется n битам, массив можно использовать для указания подмножества домена (например, {0, 1, 2,..., n-1}), где 1 бит указывает наличие и 0-битное отсутствие числа в наборе. Эта структура данных набора использует примерно n / w слов пространства, где w - количество битов в каждом машинном слове . Независимо от того, указывает ли младший бит (слова) или самый старший бит на наименьшее порядковое число, в значительной степени не имеет значения, но первый имеет тенденцию к предпочтению (на машинах little-endian ).
Хотя большинство машин не могут адресовать отдельные биты в памяти и не имеют инструкций для управления отдельными битами, каждый бит в слове можно выделить и управлять им с помощью побитовые операции. В частности:
Чтобы получить битовую маску, необходимую для этих операций, мы можем использовать оператор битового сдвига для сдвига числа 1 влево. на соответствующее количество разрядов, а также поразрядным отрицанием при необходимости.
Для двух битовых массивов одинакового размера, представляющих множества, мы можем вычислить их объединение, пересечение и теоретико-множественное различие, используя n / w простые битовые операции каждая (2n / w для разницы), а также дополнение любого из:
для i от 0 до n / w-1 complement_a [i]: = not a [ i] union [i]: = a [i] или b [i] пересечение [i]: = a [i] и b [i] разность [i]: = a [i] and (не b [i])
Если мы хотим перебрать биты битового массива, мы можем сделать это эффективно, используя дважды вложенный цикл, который перебирает каждое слово по одному. Требуются только n / w обращений к памяти:
для i от 0 до n / w-1 index: = 0 // если необходимо word: = a [i] for b от 0 до w-1 value: = word и 1 ≠ 0 word: = word shift right 1 // сделаем что-нибудь со значением index: = index + 1 // при необходимости
Оба этих примера кода демонстрируют идеальную локальность ссылки, которая впоследствии получит большой прирост производительности за счет кеширования данных. Если строка кэша состоит из k слов, произойдет только около n / wk промахов кэша.
Как и в случае символьных строк, легко определить длину, подстроку, лексикографическое сравнение, конкатенацию, обратные операции. Реализация некоторых из этих операций чувствительна к порядку байтов.
Если мы хотим найти количество 1 бит в битовом массиве, иногда называемое подсчетом совокупности или весом Хэмминга существуют эффективные алгоритмы без ветвлений, которые могут вычислять количество битов в слове с помощью серии простых битовых операций. Мы просто запускаем такой алгоритм для каждого слова и ведем промежуточный итог. Подсчет нулей аналогичен. См. Статью Вес Хэмминга для примеров эффективной реализации.
Вертикальное переворачивание изображения с разрешением один бит на пиксель или некоторые алгоритмы БПФ требуют переворачивания битов отдельных слов (поэтому b31 b30... b0становится b0... b30 b31). Когда эта операция недоступна в процессоре, все еще можно продолжить последовательные проходы, в этом примере на 32 битах:
обмен двумя 16-битными полусловами обмен байтами парами (0xddccbbaa ->0xccddaabb)... обмен битами парами перестановка битов (b31 b30... b1 b0 ->b30 b31... b0 b1) Последняя операция может быть записана ((x 0x55555555) <<1) | (x0xaaaaaaaa)>>1)).
Операция найти первый набор или найти первую операцию идентифицирует индекс или позицию 1-бита с наименьшим индексом в массиве и имеет широкую аппаратную поддержку (для массивов не более одного слова) и эффективные алгоритмы его вычисления. Когда очередь приоритета хранится в битовом массиве, поиск первого может использоваться для идентификации элемента с наивысшим приоритетом в очереди. Чтобы расширить поиск первого слова размером с более длинные массивы, можно найти первое ненулевое слово, а затем выполнить команду find first для этого слова. Связанные операции находят первый ноль, подсчитывают начальные нули, подсчитывают начальные нули, подсчитывают конечные нули, подсчитывают конечные единицы и логарифмическую базу 2 (см. найти первый набор ) также могут быть расширены до битового массива простым манера.
Битовый массив - это наиболее плотное хранилище для «случайных» битов, то есть, где каждый бит с равной вероятностью равен 0 или 1, и каждый из них независим. Но большинство данных не случайны, поэтому их можно будет хранить более компактно. Например, данные типичного изображения факса не случайны и могут быть сжаты. Кодирование длин серий обычно используется для сжатия этих длинных потоков. Однако к большинству форматов сжатых данных не так просто получить произвольный доступ; Кроме того, слишком агрессивно сжимая битовые массивы, мы рискуем потерять преимущества из-за параллелизма на битовом уровне (векторизация ). Таким образом, вместо сжатия битовых массивов как потоков битов мы могли бы сжать их как потоки байтов или слов (см. Индекс Bitmap (сжатие) ).
Битовые массивы, несмотря на свою простоту, имеют ряд заметных преимуществ перед другими структурами данных для тех же проблем:
Однако битовые массивы - это не решение всего. В частности:
Из-за своей компактности битовые массивы имеют количество приложений в областях, где пространство или эффективность имеют решающее значение. Чаще всего они используются для представления простой группы булевых флагов или упорядоченной последовательности логических значений.
Битовые массивы используются для очередей приоритета, где бит с индексом k устанавливается тогда и только тогда, когда k находится в очереди; эта структура данных используется, например, ядром Linux и сильно выигрывает от аппаратной операции поиска первого нуля.
Битовые массивы могут использоваться для выделения страниц памяти, индексных дескрипторов, секторов диска и т. Д. В таких случаях может использоваться термин битовая карта. Однако этот термин часто используется для обозначения растровых изображений, которые могут использовать несколько битов на пиксель.
Еще одним применением битовых массивов является фильтр Блума, вероятностный установить структуру данных, которая может хранить большие наборы в небольшом пространстве в обмен на небольшую вероятность ошибки. Также возможно построить вероятностные хэш-таблицы на основе битовых массивов, которые принимают либо ложные срабатывания, либо ложные отрицания.
Битовые массивы и операции с ними также важны для построения сжатых структур данных, которые используют минимально возможное пространство. В этом контексте становятся важными такие операции, как нахождение n-го 1-го бита или подсчет количества 1-го бит до определенной позиции.
Битовые массивы также являются полезной абстракцией для исследования потоков сжатых данных, которые часто содержат элементы, занимающие части байтов или не выровненные по байтам. Например, сжатое представление кодирования Хаффмана одного 8-битного символа может иметь длину от 1 до 255 бит.
В поиске информации битовые массивы являются хорошим представлением для очень часто встречающихся терминов. Если мы вычислим промежутки между соседними значениями в списке строго возрастающих целых чисел и закодируем их, используя унарное кодирование, результатом будет битовый массив с 1 битом в n-й позиции тогда и только тогда, когда n находится в список. Подразумеваемая вероятность разрыва n равна 1/2. Это также частный случай кодирования Голомба, где параметр 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 ++, хотя отдельные boolобычно занимают то же место, что и байт или целое число, STL тип векторявляется частичной специализацией шаблона, в которой биты упакованы в целях оптимизации эффективности использования пространства. Поскольку байты (а не биты) являются наименьшей адресуемой единицей в C ++, оператор не возвращает ссылку на элемент, а вместо этого возвращает ссылку прокси . Это может показаться второстепенным, но это означает, что vectorне является стандартным контейнером STL, поэтому использование vectorобычно не рекомендуется. Другой уникальный класс STL, bitset, создает вектор битов, фиксированный в определенном размере во время компиляции, и по своему интерфейсу и синтаксису больше напоминает идиоматическое использование слов как битовых наборов программистами на C. Он также обладает некоторыми дополнительными возможностями, такими как возможность эффективного подсчета количества установленных битов. Библиотеки Boost C ++ предоставляют класс dynamic_bitset, размер которого указывается во время выполнения.
Язык программирования D предоставляет битовые массивы в своей стандартной библиотеке Phobos в std.bitmanip. Как и в C ++, оператор не возвращает ссылку, поскольку отдельные биты не имеют прямой адресации на большинстве аппаратных средств, а вместо этого возвращает bool.
. В Java класс BitSet создает битовый массив, который затем обрабатывается функциями, названными в честь побитовых операторов, знакомых программистам на C. В отличие от битового наборав C ++, Java BitSetне имеет состояния «размер» (он имеет фактически бесконечный размер, инициализированный 0 битами); бит можно установить или проверить по любому индексу. Кроме того, существует класс EnumSet , который представляет Набор значений перечислимого типа внутри как битовый вектор, как более безопасную альтернативу битовым полям..
.NET Framework предоставляет класс коллекции BitArray. Он хранит логические значения, поддерживает произвольный доступ и побитовые операторы, его можно перебирать, а его свойство 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: бит (и n)переменный бит (, где n)n- положительное целое число.
языки описания оборудования, такие как VHDL, Verilog и SystemVerilog изначально поддерживают битовые векторы, поскольку они используются для моделирования таких элементов хранения, как триггеры, аппаратные шины и сигналы оборудования в целом. В языках проверки оборудования, таких как OpenVera, e и SystemVerilog, битовые векторы используются для выборки значений из моделей оборудования и для представления данных, которые передаются на оборудование во время моделирования..
