Битовый массив (также известный как битовая маска , [1] битовая карта , битовый набор , битовая строка или битовый вектор ) — это структура данных массива , которая компактно хранит биты . Его можно использовать для реализации простой структуры данных набора . Битовый массив эффективен при использовании параллелизма на уровне битов в оборудовании для быстрого выполнения операций. Типичный битовый массив хранит kw бит, где w — количество битов в единице хранения, такой как байт или слово , а k — некоторое неотрицательное целое число. Если w не делит количество битов для хранения, часть пространства тратится впустую из-за внутренней фрагментации .
Битовый массив — это отображение некоторого домена (почти всегда диапазона целых чисел) в значения в наборе {0, 1}. Значения могут быть интерпретированы как темный/светлый, отсутствующий/присутствующий, заблокированный/разблокированный, действительный/недействительный и т. д. Дело в том, что существует только два возможных значения, поэтому они могут быть сохранены в одном бите. Как и в случае с другими массивами, доступ к одному биту можно контролировать, применяя индекс к массиву. Предполагая, что его размер (или длина) составляет n бит, массив можно использовать для указания подмножества домена (например, {0, 1, 2, ..., n −1}), где бит 1 указывает на наличие, а бит 0 — на отсутствие числа в наборе. Эта структура данных набора использует около n / w слов пространства, где w — количество бит в каждом машинном слове . Не имеет значения, указывает ли младший или старший бит на наименьший индексный номер, но первый вариант, как правило, предпочтительнее (на машинах с прямым порядком байтов ).
Конечное бинарное отношение может быть представлено битовым массивом, называемым логической матрицей . В исчислении отношений эти массивы составляются с помощью умножения матриц , где арифметика является булевой, и такая композиция представляет собой композицию отношений . [2]
Хотя большинство машин не могут адресовать отдельные биты в памяти и не имеют инструкций для манипулирования отдельными битами, каждый бит в слове может быть выделен и обработан с помощью побитовых операций . В частности:
Используйте ORдля установки бита в единицу:
11101 0 10ИЛИ 00000 1 00 = 11101 1 10
ANDчтобы установить бит в ноль:
111010 1 0И 111111 0 1 = 111010 0 0
ANDчтобы определить, установлен ли бит, проверив его на ноль:
1110101 0 111010 1 0 И 0000000 1 И 000000 1 0 = 0000000 0 = 000000 1 0(=0 ∴ бит не установлен) (≠0 ∴ бит установлен)
XORчтобы инвертировать или переключить немного:
11101 0 10 11101 1 10Исключающее ИЛИ 00000 1 00 Исключающее ИЛИ 00000 1 00 = 11101 1 10 = 11101 0 10
NOTдля инвертирования всех битов:
НЕ 10110010 = 01001101
Чтобы получить битовую маску, необходимую для этих операций, мы можем использовать оператор битового сдвига , чтобы сдвинуть число 1 влево на соответствующее количество разрядов, а также побитовое отрицание, если необходимо.
Если даны два битовых массива одинакового размера, представляющих множества, мы можем вычислить их объединение , пересечение и теоретико-множественную разность, используя n / w простых битовых операций для каждого (2 n / w для разности), а также дополнение любого из них:
для i от 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 доступ к памяти:
для i от 0 до n/w-1 индекс := 0 // если необходимо слово := а[i] для b от 0 до w-1 значение := слово и 1 ≠ 0 слово := слово сдвиг вправо на 1 // сделать что-то со значением индекс := индекс + 1 // если необходимо
Оба этих примера кода демонстрируют идеальную локальность ссылок , которая впоследствии получит большой прирост производительности от кэша данных. Если строка кэша составляет k слов, произойдет только около n / wk промахов кэша.
Как и в случае со строками символов, здесь легко определить операции length , substring , lexicographical compare , concatenation , reverse . Реализация некоторых из этих операций чувствительна к порядку байтов .
Если мы хотим найти количество единичных битов в битовом массиве, иногда называемое подсчетом популяции или весом Хэмминга, существуют эффективные алгоритмы без ветвлений, которые могут вычислить количество битов в слове с помощью серии простых битовых операций. Мы просто запускаем такой алгоритм для каждого слова и ведем промежуточный итог. Подсчет нулей аналогичен. См. статью о весе Хэмминга для примеров эффективной реализации.
Вертикальное переворачивание изображения с одним битом на пиксель или некоторые алгоритмы FFT требуют переворачивания битов отдельных слов (поэтому b31 b30 ... b0становится b0 ... b30 b31). Когда эта операция недоступна на процессоре, все равно можно продолжить последовательными проходами, в этом примере на 32 битах:
обмен двумя 16-битными полусловамиобмен байтами попарно (0xddccbbaa -> 0xccddaabb)...поменять биты местами попарнопоменять биты местами (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1)Последнюю операцию можно записать так: ((x&0x55555555) << 1) | (x&0xaaaaaaaa) >> 1)).Операция find first set или find first one определяет индекс или позицию 1-бита с наименьшим индексом в массиве и имеет широкую аппаратную поддержку (для массивов не больше слова) и эффективные алгоритмы для его вычисления. Когда приоритетная очередь хранится в битовом массиве, find first one можно использовать для определения элемента с наивысшим приоритетом в очереди. Чтобы расширить размер слова find first one до более длинных массивов, можно найти первое ненулевое слово, а затем запустить find first one для этого слова. Связанные операции find first zero , count leading zeros , count leading one , count trailing zeros , count trailing one и log base 2 (см. find first set ) также можно расширить до битового массива простым способом.
Битовый массив является наиболее плотным хранилищем для «случайных» битов, то есть, где каждый бит с равной вероятностью может быть 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. В отличие от bitsetв C++, в 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), используя оператор скобок ( []), как если бы это был массив битов.
Библиотека Core Foundation компании Apple содержит структуры 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