Битовый массив (также известный как битовая маска , [1] битовая карта , набор бит , битовая строка или битовый вектор ) — это структура данных массива , в которой компактно хранятся биты . Его можно использовать для реализации простой структуры набора данных . Битовый массив эффективен при использовании аппаратного параллелизма на уровне битов для быстрого выполнения операций. Типичный битовый массив хранит kw бит, где w — количество битов в единице хранения, например байте или слове , а k — некоторое неотрицательное целое число. Если w не делит количество сохраняемых битов, некоторое пространство теряется из-за внутренней фрагментации .
Битовый массив — это отображение некоторого домена (почти всегда диапазона целых чисел) на значения в наборе {0, 1}. Значения можно интерпретировать как темный/светлый, отсутствующий/присутствующий, заблокированный/разблокированный, действительный/недействительный и т. д. Дело в том, что возможных значений всего два, поэтому их можно хранить в одном бите. Как и в случае с другими массивами, доступом к одному биту можно управлять путем применения индекса к массиву. Предполагая, что его размер (или длина) равен n битам, массив можно использовать для указания подмножества домена (например, {0, 1, 2, ..., n −1}), где 1 бит указывает наличие и 0-бит отсутствие числа в наборе. Эта структура набора данных использует около n / w слов пространства, где w — количество битов в каждом машинном слове . Указывает ли младший бит (слова) или самый старший бит наименьшее число индекса, в значительной степени не имеет значения, но первый имеет тенденцию быть предпочтительнее (на машинах с прямым порядком байтов ).
Конечное двоичное отношение может быть представлено битовым массивом, называемым логической матрицей . В исчислении отношений эти массивы составляются с помощью матричного умножения , где арифметика является логической, и такая композиция представляет собой композицию отношений . [2]
Хотя большинство машин не способны обращаться к отдельным битам памяти и не имеют инструкций для манипулирования отдельными битами, каждый бит в слове можно выделить и манипулировать им с помощью побитовых операций . В частности:
Чтобы получить битовую маску , необходимую для этих операций, мы можем использовать оператор битового сдвига для сдвига числа 1 влево на соответствующее количество мест, а также побитовое отрицание, если необходимо.
Учитывая два битовых массива одинакового размера, представляющие множества, мы можем вычислить их объединение , пересечение и теоретико-множественную разницу , используя n / w простых битовых операций каждая (2 n / w для разности), а также дополнение любого из них:
для меня от 0 до n/w-1 дополнение_a[i] := не a[i] объединение[i] := a[i] или b[i] пересечение[i] := a[i] и b[i] разница[i] := a[i] и ( не b[i])
Если мы хотим перебрать биты битового массива, мы можем сделать это эффективно, используя двойной вложенный цикл, который проходит по каждому слову по одному. Требуется только доступ к памяти n / w :
для меня от 0 до n/w-1 индекс := 0 // если необходимо слово := а[я] для b от 0 до w-1 значение := слово и 1 ≠ 0 слово := сдвиг слова вправо 1 // делаем что-то со значением индекс := индекс + 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) | (x&0xaaaaaaaa) >> 1)).Операция «найти первый набор» или «найти первый один» идентифицирует индекс или позицию 1-бита с наименьшим индексом в массиве и имеет широкую аппаратную поддержку (для массивов размером не больше слова) и эффективные алгоритмы его вычисления. Когда очередь с приоритетом хранится в битовом массиве, функцию find first можно использовать для определения элемента с наивысшим приоритетом в очереди. Чтобы расширить размер слова find first one до более длинных массивов, можно найти первое ненулевое слово, а затем запустить find first one для этого слова. Соответствующие операции найти первый ноль , подсчитать ведущие нули , подсчитать ведущие единицы , подсчитать конечные нули , подсчитать конечные единицы и записать в журнал базу 2 (см. найти первый набор ) также можно простым образом расширить до битового массива.
Битовый массив — это наиболее плотное хранилище для «случайных» битов, то есть где каждый бит с равной вероятностью может быть равен 0 или 1, и каждый из них независим. Но большинство данных не случайны, поэтому их можно хранить более компактно. Например, данные типичного изображения факса не случайны и могут быть сжаты. Кодирование длины серии обычно используется для сжатия этих длинных потоков. Однако к большинству форматов сжатых данных не так легко получить произвольный доступ; также, слишком агрессивно сжимая битовые массивы, мы рискуем потерять преимущества из-за параллелизма на уровне битов ( векторизации ). Таким образом, вместо сжатия битовых массивов в потоки битов мы могли бы сжать их в потоки байтов или слов (см. Индекс растрового изображения (сжатие) ).
Битовые массивы, несмотря на свою простоту, имеют ряд заметных преимуществ перед другими структурами данных для тех же задач:
Однако битовые массивы не являются решением всех проблем. В частности:
Из-за своей компактности битовые массивы находят множество применений в областях, где пространство или эффективность имеют большое значение. Чаще всего они используются для представления простой группы логических флагов или упорядоченной последовательности логических значений.
Битовые массивы используются для очередей с приоритетом , где бит с индексом 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 также часто используют слова как небольшие битовые массивы и получают доступ к их битам с помощью битовых операторов. Широко доступный заголовочный файл, включенный в систему X11 , xtrapbits.h, представляет собой «переносимый способ для систем определять манипуляции с битовыми полями массивов битов». Более подробное описание вышеупомянутого подхода можно найти в FAQ по comp.lang.c.
В C++ , хотя отдельные bools обычно занимают то же пространство, что и байт или целое число, тип STLvector<bool> представляет собой частичную специализацию шаблона , в которой биты упаковываются в целях оптимизации использования пространства. Поскольку байты (а не биты) являются наименьшей адресной единицей в C++, оператор [] не возвращает ссылку на элемент, а вместо этого возвращает ссылку на прокси . Это может показаться незначительным моментом, но это означает, что vector<bool>это не стандартный контейнер STL, поэтому использование vector<bool>обычно не рекомендуется. Другой уникальный класс STL, bitset, [3] создает вектор битов, фиксированного определенного размера во время компиляции, и по своему интерфейсу и синтаксису больше напоминает идиоматическое использование слов в качестве наборов битов программистами на языке C. Он также имеет некоторые дополнительные возможности, такие как способность эффективно подсчитывать количество установленных бит. Библиотеки Boost C++ предоставляют dynamic_bitsetкласс [4] , размер которого указывается во время выполнения.
Язык программирования D предоставляет битовые массивы в своей стандартной библиотеке Phobos в формате std.bitmanip. Как и в C++, оператор [] не возвращает ссылку, поскольку на большинстве аппаратных средств отдельные биты не адресуются напрямую, а вместо этого возвращает bool.
В Java класс BitSetсоздает битовый массив, которым затем манипулируют с помощью функций, названных в честь побитовых операторов, знакомых программистам на C. В отличие от bitsetC++, Java BitSetне имеет состояния «размера» (он имеет фактически бесконечный размер, инициализируемый 0 битами); бит может быть установлен или проверен по любому индексу. Кроме того, существует класс EnumSet, который представляет набор значений перечислимого типа внутри как битовый вектор, как более безопасную альтернативу битовым полям.
.NET Framework предоставляет BitArrayкласс коллекции. Он хранит биты, используя массив типов int(каждый элемент массива обычно представляет 32 бита). [5] Класс поддерживает произвольный доступ и побитовые операторы, его можно перебирать, а его Lengthсвойство можно изменить для увеличения или усечения.
Хотя Standard ML не поддерживает битовые массивы, Standard ML of New Jersey имеет расширение, структуру BitArray, в своей библиотеке SML/NJ. Его размер не фиксирован и поддерживает операции над множествами и битовые операции, включая, что необычно, операции сдвига.
В Haskell также в настоящее время отсутствует стандартная поддержка побитовых операций, но и GHC , и Hugs предоставляют Data.Bitsмодуль с различными побитовыми функциями и операторами, включая операции сдвига и поворота, а для моделирования битового массива можно использовать «распакованный» массив с логическими значениями, хотя это отсутствует поддержка со стороны предыдущего модуля.
В Perl строки можно использовать как расширяемые битовые массивы. Ими можно манипулировать с помощью обычных побитовых операторов ( ~ | & ^), [6] , а отдельные биты можно проверять и устанавливать с помощью функции vec . [7]
В Ruby вы можете получить доступ (но не установить) к биту целого числа ( Fixnumили Bignum), используя оператор квадратных скобок ( []), как если бы это был массив битов.
Библиотека Apple Core Foundation содержит структуры CFBitVector и CFMutableBitVector.
PL/I поддерживает массивы битовых строк произвольной длины, которые могут быть фиксированной или переменной длины. Элементы массива могут быть выровнены (каждый элемент начинается на границе байта или слова) или невыровнены (элементы сразу следуют друг за другом без заполнения).
PL/pgSQL и SQL PostgreSQL поддерживают битовые строки как собственный тип. Существует два типа битов SQL: и , где – положительное целое число. [8]bit(n)bit varying(n)n
Языки описания оборудования, такие как VHDL , Verilog и SystemVerilog, изначально поддерживают битовые векторы, поскольку они используются для моделирования элементов хранения, таких как триггеры , аппаратные шины и аппаратные сигналы в целом. В языках проверки оборудования, таких как OpenVera , e и SystemVerilog , битовые векторы используются для выборки значений из моделей оборудования и для представления данных, которые передаются на оборудование во время моделирования.
Common Lisp предоставляет одномерную bit-vectorреализацию как частный случай встроенного array, действуя в двойном качестве как класс и спецификатор типа. [9] Будучи производным от массива, он опирается на общую make-arrayфункцию, конфигурируемую с типом элемента bit, который опционально позволяет обозначить битовый вектор как динамически изменяемый размер. bit-vectorОднако масштабы не бесконечны . Существует более ограниченный simple-bit-vectorтип, который явно исключает динамические характеристики. [10] Битовые векторы представлены в виде макроса считывателя и могут быть построены в более краткой форме . [11] В дополнение к общим функциям, применимым ко всем массивам, существуют специальные операции для битовых векторов. Доступ к отдельным битам и их изменение можно осуществлять с помощью функций и [12] , поддерживается большое количество логических операций. [13]#*bitsbitsbit