Битовый массив
 | Эта статья нуждается в дополнительных ссылок для проверки . ( декабрь 2010 г. ) |
Битовый массив (также известный как битовая маска , [1] битовая карта , набор битов , битовая строка или битовый вектор ) — это структура данных массива , в которой компактно хранятся биты . Его можно использовать для реализации простой структуры набора данных . Битовый массив эффективен при использовании параллелизма на уровне битов аппаратного для быстрого выполнения операций. Типичный битовый массив хранит kw бит, где w — количество битов в единице хранения, например байте или слове , а k — некоторое неотрицательное целое число. Если w не делит количество сохраняемых битов, некоторое пространство теряется из-за внутренней фрагментации .
Определение [ править ]
Битовый массив — это отображение некоторого домена (почти всегда диапазона целых чисел) на значения в наборе {0, 1}. Значения можно интерпретировать как темный/светлый, отсутствующий/присутствующий, заблокированный/разблокированный, действительный/недействительный и т. д. Дело в том, что возможных значений всего два, поэтому их можно хранить в одном бите. Как и в случае с другими массивами, доступом к одному биту можно управлять путем применения индекса к массиву. Предполагая, что его размер (или длина) равен n битам, массив можно использовать для указания подмножества домена (например, {0, 1, 2, ..., n −1}), где 1 бит указывает наличие и 0-бит отсутствие числа в наборе. Эта структура набора данных использует около n / w слов пространства, где w — количество битов в каждом машинном слове . Указывает ли младший бит (слова) или самый старший бит наименьшее число индекса, в значительной степени не имеет значения, но первый имеет тенденцию быть предпочтительнее (на машинах с прямым порядком байтов ).
Конечное двоичное отношение может быть представлено битовым массивом, называемым логической матрицей . В исчислении отношений эти массивы составляются с помощью умножения матриц , где арифметика является логической, и такая композиция представляет собой композицию отношений . [2]
Основные операции [ править ]
Хотя большинство машин не способны обращаться к отдельным битам памяти и не имеют инструкций для манипулирования отдельными битами, каждый бит в слове можно выделить и манипулировать им с помощью побитовых операций . В частности:
- ИЛИ, чтобы установить бит в единицу: 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 для разности), а также дополнение любого из них:
для меня от 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 произойдет промахов кэша.
Более сложные операции [ править ]
Как и в случае со строками символов, здесь легко определить длину , подстроку , лексикографическое сравнение , конкатенацию и обратные операции. Реализация некоторых из этих операций чувствительна к порядку байтов .
Население Хэмминга вес /
Если мы хотим найти количество битов в битовом массиве, иногда называемое подсчетом совокупности или весом Хэмминга, существуют эффективные алгоритмы без ветвей, которые могут вычислить количество битов в слове, используя серию простых битовых операций. Мы просто запускаем такой алгоритм для каждого слова и сохраняем текущий итог. Подсчет нулей аналогичен. см. в статье о весе Хэмминга Примеры эффективной реализации .
Инверсия [ править ]
Вертикальное переворачивание изображения (один бит на пиксель) или некоторые алгоритмы БПФ требуют переворачивания битов отдельных слов (поэтому 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, и каждый из них независим. Но большинство данных не случайны, поэтому их можно хранить более компактно. Например, данные типичного изображения факса не случайны и могут быть сжаты. Кодирование длины серии обычно используется для сжатия этих длинных потоков. Однако к большинству форматов сжатых данных не так легко получить произвольный доступ; также, слишком агрессивно сжимая битовые массивы, мы рискуем потерять преимущества из-за параллелизма на уровне битов ( векторизации ). Таким образом, вместо сжатия битовых массивов в потоки битов мы могли бы сжать их в потоки байтов или слов (см. Индекс растрового изображения (сжатие) ).
Преимущества и недостатки [ править ]
Битовые массивы, несмотря на свою простоту, имеют ряд заметных преимуществ перед другими структурами данных для тех же задач:
- Они чрезвычайно компактны; никакие другие структуры данных не могут хранить n независимых фрагментов данных в n / w словах.
- Они позволяют хранить небольшие массивы битов и манипулировать ими в наборе регистров в течение длительных периодов времени без доступа к памяти.
- Благодаря своей способности использовать параллелизм на битовом уровне, ограничивать доступ к памяти и максимально использовать кэш данных , они часто превосходят многие другие структуры данных на практических наборах данных, даже те, которые более асимптотически эффективны.
Однако битовые массивы не являются решением всех проблем. В частности:
- Без сжатия они представляют собой расточительные структуры данных наборов для разреженных наборов (с небольшим количеством элементов по сравнению с их диапазоном) как во времени, так и в пространстве. Для таких приложений сжатые битовые массивы, массивы Джуди , попытки или даже фильтры Блума . вместо этого следует рассматривать
- Доступ к отдельным элементам может быть дорогостоящим и трудным для выражения на некоторых языках. Если произвольный доступ более распространен, чем последовательный, и массив относительно невелик, байтовый массив может быть предпочтительнее на машине с байтовой адресацией. Однако массив слов, вероятно, не оправдан из-за огромных накладных расходов на пространство и дополнительных промахов в кэше, которые он вызывает, если только машина не имеет только словесную адресацию.
Приложения [ править ]
Из-за своей компактности битовые массивы находят множество применений в областях, где пространство или эффективность имеют большое значение. Чаще всего они используются для представления простой группы логических флагов или упорядоченной последовательности логических значений.
Битовые массивы используются для очередей с приоритетом , где бит с индексом 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 также часто используют слова как небольшие битовые массивы и получают доступ к их битам с помощью битовых операторов. Широко доступный заголовочный файл, включенный в систему X11 , xtrapbits.h, представляет собой «переносимый способ для систем определять манипуляции с битовыми полями массивов битов». Более подробное описание вышеупомянутого подхода можно найти в FAQ по comp.lang.c.
В C++ , хотя и индивидуально boolобычно занимают то же пространство, что и байт или целое число, STL тип vector<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) с помощью оператора скобки ( []), как если бы это был массив битов.
Библиотека Apple Core Foundation содержит структуры CFBitVector и CFMutableBitVector .
PL/I поддерживает массивы битовых строк произвольной длины, которые могут быть фиксированной или переменной длины. Элементы массива могут быть выровнены (каждый элемент начинается на границе байта или слова) или невыровнены (элементы сразу следуют друг за другом без заполнения).
PL/pgSQL и SQL PostgreSQL поддерживают битовые строки как собственный тип. Существует два типа битов SQL: bit( и n)bit varying(, где n)n является положительным целым числом. [8]
Языки описания оборудования, такие как VHDL , Verilog и SystemVerilog , изначально поддерживают битовые векторы, поскольку они используются для моделирования элементов хранения, таких как триггеры , аппаратные шины и аппаратные сигналы в целом. В языках проверки оборудования, таких как OpenVera , e и SystemVerilog , битовые векторы используются для выборки значений из моделей оборудования и для представления данных, которые передаются на оборудование во время моделирования.
Common Lisp обеспечивает одномерную bit-vector реализация как частный случай встроенного array, действующий одновременно как класс и спецификатор типа. [9] Будучи производной массива, он опирается на общее make-array функция, которая будет настроена с типом элемента bit, что дополнительно позволяет обозначить битовый вектор как динамически изменяемый. bit-vector, однако, не является бесконечным по размеру. Более ограниченный simple-bit-vector тип существует, что явно исключает динамические характеристики. [10] Битовые векторы представлены в виде макроса считывателя и могут быть построены в более краткой форме. #*bits. [11] В дополнение к общим функциям, применимым ко всем массивам, существуют специальные операции для битовых векторов. К отдельным битам можно получить доступ и изменить их с помощью bit и sbit функции [12] поддерживается большое количество логических операций. [13]
См. также [ править ]
- Арифметико-логическое устройство
- Бинарный код
- Двоичная система счисления
- Bitboard Chess и подобные игры.
- Битовое поле
- Индекс растрового изображения
- Битстрим
- Конечное поле из 2 элементов или GF(2)
- Массив Джуди
- Код переменной длины
Ссылки [ править ]
- ^ «Хаки ключей магической системы Linux» . Кернел.орг .
- ^ Ирвинг Копиловиш (декабрь 1948 г.) «Матричное развитие исчисления отношений», Журнал символической логики 13 (4): 193–203 Jstor link
- ^ «Ресурсы технического архива SGI.com больше не используются» . СГИ . 2 января 2018 г.
- ^ «dynamic_bitset<Блок, Распределитель> — 1.66.0» . www.boost.org .
- ^ «Исходный код .NET mscorlib» . github.com/microsoft . 15 октября 2021 г.
- ^ «perlop — perldoc.perl.org» . perldoc.perl.org .
- ^ "vec-perldoc.perl.org" . perldoc.perl.org .
- ^ «8.10. Типы битовых строк» . 30 сентября 2021 г.
- ^ «CLHS: Системный класс БИТ-ВЕКТОР» . www.lispworks.com .
- ^ «CLHS: Тип ПРОСТОЙ-БИТ-ВЕКТОР» . www.lispworks.com .
- ^ «CLHS: Раздел 2.4.8.4» . www.lispworks.com .
- ^ «CLHS: Аксессор BIT, SBIT» . www.lispworks.com .
- ^ «CLHS: Функция БИТ-И, БИТ-ИC1, БИТ-ИC2…» www.lispworks.com .