Битовый массив c что это
Битовые коллекции
Если требуется иметь дело с множеством битов, можно применить класс BitArray и структуру BitVector32. Класс BitArray расположен в пространстве имен System.Collections, a BitVector32 — в пространстве System.Collections.Specialized. Наиболее важное отличие между этими двумя типами состоит в том, что BitArray имеет изменяемый размер, а это удобно, когда необходимое количество бит известно заранее, и оно велико. Структура BitVector32 основана на стеке, и потому работает быстрее. BitVector32 содержит только 32 бита, которые хранятся в целом числе.
Класс BitArray
Класс BitArray служит для хранения отдельных битов в коллекции. А поскольку в коллекции этого класса хранятся биты, а не объекты, то своими возможностями он отличается от классов других коллекций. Тем не менее в классе BitArray реализуются интерфейсы ICollection и IEnumerable как основополагающие элементы поддержки всех типов коллекций. Кроме того, в классе BitArray реализуется интерфейс ICloneable.
В классе BitArray определено несколько конструкторов. Так, с помощью приведенного ниже конструктора можно сконструировать объект типа BitArray из массива логических значений:
В данном случае каждый элемент массива values становится отдельным битом в коллекции. Это означает, что каждому элементу массива values соответствует отдельный бит в коллекции. Более того, порядок расположения элементов в массиве values сохраняется и в коллекции соответствующих им битов. Коллекцию типа BitArray можно также составить из массива байтов, используя следующий конструктор:
Здесь битами в коллекции становится уже целый их набор из массива bytes, причем элемент bytes [0] обозначает первые 8 битов, элемент bytes [1] — вторые 8 битов и т.д.
Коллекции типа BitArray подлежат индексированию. По каждому индексу указывается отдельный бит в коллекции, причем нулевой индекс обозначает младший бит.
В классе BitArray определяется ряд собственных методов, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Методы этого класса приведены ниже. Обратите внимание на то, что в классе BitArray не поддерживается метод Synchronized(). Это означает, что для коллекций данного класса синхронизированная оболочка недоступна, а свойство IsSynchronized всегда имеет логическое значение false. Тем не менее для управления доступом к коллекции типа BitArray ее можно синхронизировать для объекта, предоставляемого упоминавшимся ранее свойством SyncRoot.
Выполняет операцию логического умножения (И) битов вызывающего объекта и коллекции value. Возвращает коллекцию типа BitArray, содержащую результат
Возвращает значение бита, указываемого по индексу
Выполняет операцию поразрядного логического отрицания (НЕ) битов вызывающей коллекции и возвращает коллекцию типа BitArray, содержащую результат
Выполняет операцию логического сложения (ИЛИ) битов вызывающего объекта и коллекции value. Возвращает коллекцию типа BitArray, содержащую результат
Устанавливает бит, указываемый по индексу index, равным значению value
SetAll()
Устанавливает все биты равными значению value
Выполняет логическую операцию исключающее (ИЛИ) над битами вызывающего объекта и коллекции value. Возвращает коллекцию типа BitArray, содержащую результат
В классе BitArray определяется также собственное свойство, помимо тех, что указаны в интерфейсах, которые в нем реализуются:
позволяет установить или получить количество битов в коллекции. Следовательно, оно возвращает такое же значение, как и стандартное свойство Count, определяемое для всех коллекций. В отличие от свойства Count, свойство Length доступно не только для чтения, но и для записи, а значит, с его помощью можно изменить размер коллекции типа BitArray.
Давайте рассмотрим пример использования класса BitArray:
Структура BitVector32
Если необходимое количество бит известно заранее, то вместо BitArray можно использовать структуру BitVector32. Структура BitVector32 более эффективна, поскольку это тип значения, хранящий биты в стеке внутри целого числа. В единственном целом числе имеется место для 32 бит. Если нужно больше, можно применять множество значений BitVector32 или же BitArray. Класс BitArray при необходимости может расти, а структура BitVector32 лишена такой возможности.
Ниже перечислены члены структуры BitVector32, которые существенно отличаются от BitArray:
Data
Свойство Data возвращает данные BitVector32 в виде целого числа.
Item
Значение BitVector32 может быть установлено с использованием целого числа. Индексатор перегружен: получать и устанавливать значения можно с использованием маски или секции типа BitVector32.Section.
CreateMask()
Статический метод, который позволяет создавать маску для доступа к определенным битам Bitvector32.
CreateSelection()
Статический метод, который позволяет создавать несколько секций внутри 32 бит.
В приведенном ниже примере создается структура BitVector32 с помощью конструктора по умолчанию, при этом все 32 бита инициализируются false. Затем создаются маски для доступа к битам внутри битового вектора. Первый вызов CreateMask() создает маску для доступа к первому биту. После вызова CreateMask() значение bitl равно 1. Еще один вызов CreateMask() возвращает маску для доступа ко второму биту, которая равна 2. bit3 имеет значение 4 для доступа к биту номер 3. bit4 имеет значение 8 для доступа к биту номер 4.
Затем маски используются с индексатором для доступа к битам внутри вектора бит и соответствующей установки полей:
C Урок 32. Битовые поля
Продолжаем работать со структурами.
Оказывается, кроме полей размером, кратным байту, мы можем в структурах (а также, конечно, и в объединениях) работать с битами, то есть мы можем объявить поле в какое-то количество бит. Хотя язык C не предусматривает операции с отдельным битом, но с помощью битовых полей это ограничение можно обойти. Это, конечно же, не является полной заменой битовых операций ассемблера, но для удобства работы с кодом, для его читабельности, мы это вполне можем применять.
Также, если мы и не будем в своих кодах применять битовые поля, то нам такое может попасться в чужих кодах, и после данного урока мы будем хотя бы знать, что это такое.
Также битовые поля нам могут потребоваться для каких-то флагов, для каких-то значений, диапазон которых отличается от диапазона стандартных типов.
Битовое поле в структуре объявляется следующим образом
В различной литературе я читал про разные ограничения типов для битовых полей. Видимо, всё это исходит из различных стандартов, выходящих время от времени. Поэкспериментировав немного, я понял, что самое главное, чтобы этот тип был целочисленным.
Если в структуре есть и битовые поля и обычные поля, то лучше битовые поля располагать подряд и стараться их не чередовать с обычными для того, чтобы меньше потребовалось памяти под структуру. Также по возможности выравнивание полей тоже лучше отключить. Можно и оставить, если, конечно, у нас в сумме размер всех битовых полей, идущих подряд в структуре будет стремиться к 32.
Вот пример объявления битовых полей в структуре, которой есть и обычные поля
#pragma pack(push, 1)
typedef struct
unsigned char diad0 :2;
unsigned char tri0 :3;
unsigned char bit0 :1;
unsigned char bit1 :1;
unsigned char a ;
unsigned short b ;
> my_arg_t ;
#pragma pack(pop)
Так как мы отключили выравнивание, то под переменную такой структуры будет выделена память в 4 байта.
Небольшое выравнивание в данном случае все равно произойдёт, так как если посчитать суммарное количество битов в битовых полях, то их у нас 7, а не 8, то есть если количество битов в непрерывно следующих битовых полях в структуре не кратно восьми, то следующее за ним небитовое обычное поле будет выравниваться по биту следующего адреса, так как адресоваться в битах мы не можем.
В случае конкретной структуры, которую мы только что объявили поля её расположатся в памяти следующим образом
Самые младшие два бита младшего байта заняло битовое поле (диада) diad0, следующие три бита этого же байта заняло битовое поле (триада) tri0, следующий бит этого байта – битовое поле размером в 1 бит bit0, следующий бит – такое же поле bit1. 7-й бит данного байта у нас не участвует в данных вообще, так как следующее поле не битовое. Поэтому следующее поле заняло следующий байт, а последнее поле – следующие 2 байта, сначала – младший байт поля, а затем – старший.
Думаю, теперь немного прояснилась картина по битовым полям.
Ну а чтобы она совсем прояснилась, давайте поработаем с ними на практике.
Поэтому давайте приступим к проекту, который мы сделаем, как всегда, из проекта прошлого урока с именем MYPROG31 и присвоим ему имя MYPROG32.
Откроем наш проект в Eclipse, произведём его первоначальную настройку и удалим весь наш код из функции main() за исключением возврата. Функция main() приобретёт вот такой вид
int main()
return 0; //Return an integer from a function
Глобальное объединение my_arg_t и одноимённую закомментированную структуру также удалим и добавим вместо них структуру с битовыми полями, точь в точь такую же, как в теоретической части
СОДЕРЖАНИЕ
Определение
Основные операции
Чтобы получить битовую маску, необходимую для этих операций, мы можем использовать оператор битового сдвига, чтобы сдвинуть число 1 влево на соответствующее количество разрядов, а также побитовое отрицание, если необходимо.
Если мы хотим перебрать биты битового массива, мы можем сделать это эффективно, используя дважды вложенный цикл, который перебирает каждое слово по одному. Требуются только n / w доступы к памяти:
Более сложные операции
Население / Вес Хэмминга
Если мы хотим найти количество 1 бит в битовом массиве, иногда называемом подсчетом совокупности или весом Хэмминга, существуют эффективные алгоритмы без ветвлений, которые могут вычислить количество бит в слове, используя серию простых битовых операций. Мы просто запускаем такой алгоритм для каждого слова и ведем промежуточный итог. Подсчет нулей аналогичен. См. Статью о весах Хэмминга, где приведены примеры эффективной реализации.
Инверсия
Найдите первый
Сжатие
Преимущества и недостатки
Битовые массивы, несмотря на их простоту, имеют ряд заметных преимуществ перед другими структурами данных для тех же проблем:
Приложения
Из-за своей компактности битовые массивы находят множество применений в областях, где пространство или эффективность имеют решающее значение. Чаще всего они используются для представления простой группы логических флагов или упорядоченной последовательности логических значений.
Битовые массивы также являются полезной абстракцией для изучения потоков сжатых данных, которые часто содержат элементы, занимающие части байтов или не выровненные по байтам. Например, сжатое кодовое представление Хаффмана одного 8-битного символа может иметь длину от 1 до 255 бит.
Языковая поддержка
.NET Framework поставляет BitArray класс коллекции. Он хранит биты с использованием массива типа int (каждый элемент в массиве обычно представляет 32 бита). Класс поддерживает произвольный доступ и побитовые операторы, его можно повторять, а его Length свойство можно изменять, увеличивая или усекая его.
Хотя Standard ML не поддерживает битовые массивы, Standard ML из Нью-Джерси имеет расширение, BitArray структуру, в своей библиотеке SML / NJ. Он не имеет фиксированного размера и поддерживает операции с наборами и битовые операции, включая, что необычно, операции сдвига.
В Haskell в настоящее время также отсутствует стандартная поддержка поразрядных операций, но и GHC, и Hugs предоставляют Data.Bits модуль с различными побитовыми функциями и операторами, включая операции сдвига и поворота, а «распакованный» массив над логическими значениями может использоваться для моделирования битового массива, хотя это не поддерживает прежний модуль.
В Perl строки могут использоваться как расширяемые битовые массивы. Им можно управлять с помощью обычных побитовых операторов (
В Ruby вы можете получить доступ (но не установить) бит целого числа ( Fixnum или Bignum ) с помощью оператора скобки ( [] ), как если бы это был массив бит.
СОДЕРЖАНИЕ
Определение
Основные операции
Чтобы получить битовую маску, необходимую для этих операций, мы можем использовать оператор битового сдвига, чтобы сдвинуть число 1 влево на соответствующее количество разрядов, а также побитовое отрицание, если необходимо.
Если мы хотим перебрать биты битового массива, мы можем сделать это эффективно, используя дважды вложенный цикл, который перебирает каждое слово по одному. Требуются только n / w доступы к памяти:
Более сложные операции
Население / Вес Хэмминга
Если мы хотим найти количество 1 бит в битовом массиве, иногда называемом подсчетом совокупности или весом Хэмминга, существуют эффективные алгоритмы без ветвлений, которые могут вычислить количество бит в слове, используя серию простых битовых операций. Мы просто запускаем такой алгоритм для каждого слова и ведем промежуточный итог. Подсчет нулей аналогичен. См. Статью о весах Хэмминга, где приведены примеры эффективной реализации.
Инверсия
Найдите первый
Сжатие
Преимущества и недостатки
Битовые массивы, несмотря на их простоту, имеют ряд заметных преимуществ перед другими структурами данных для тех же проблем:
Приложения
Из-за своей компактности битовые массивы находят множество применений в областях, где пространство или эффективность имеют решающее значение. Чаще всего они используются для представления простой группы логических флагов или упорядоченной последовательности логических значений.
Битовые массивы также являются полезной абстракцией для изучения потоков сжатых данных, которые часто содержат элементы, занимающие части байтов или не выровненные по байтам. Например, сжатое кодовое представление Хаффмана одного 8-битного символа может иметь длину от 1 до 255 бит.
Языковая поддержка
.NET Framework поставляет BitArray класс коллекции. Он хранит биты с использованием массива типа int (каждый элемент в массиве обычно представляет 32 бита). Класс поддерживает произвольный доступ и побитовые операторы, его можно повторять, а его Length свойство можно изменять, увеличивая или усекая его.
Хотя Standard ML не поддерживает битовые массивы, Standard ML из Нью-Джерси имеет расширение, BitArray структуру, в своей библиотеке SML / NJ. Он не имеет фиксированного размера и поддерживает операции с наборами и битовые операции, включая, что необычно, операции сдвига.
В Haskell в настоящее время также отсутствует стандартная поддержка поразрядных операций, но и GHC, и Hugs предоставляют Data.Bits модуль с различными побитовыми функциями и операторами, включая операции сдвига и поворота, а «распакованный» массив над логическими значениями может использоваться для моделирования битового массива, хотя это не поддерживает прежний модуль.
В Perl строки могут использоваться как расширяемые битовые массивы. Им можно управлять с помощью обычных побитовых операторов (
В Ruby вы можете получить доступ (но не установить) бит целого числа ( Fixnum или Bignum ) с помощью оператора скобки ( [] ), как если бы это был массив бит.
Битовый массив
СОДЕРЖАНИЕ
Определение [ править ]
Основные операции [ править ]
Чтобы получить битовую маску, необходимую для этих операций, мы можем использовать оператор битового сдвига, чтобы сдвинуть число 1 влево на соответствующее количество разрядов, а также побитовое отрицание, если необходимо.
Если мы хотим перебрать биты битового массива, мы можем сделать это эффективно, используя дважды вложенный цикл, который перебирает каждое слово по одному. Требуются только n / w доступы к памяти:
Более сложные операции [ править ]
Население / Вес Хэмминга [ править ]
Если мы хотим найти количество 1 бит в битовом массиве, иногда называемом подсчетом популяции или весом Хэмминга, существуют эффективные алгоритмы без ветвлений, которые могут вычислить количество бит в слове, используя серию простых битовых операций. Мы просто запускаем такой алгоритм для каждого слова и ведем промежуточный итог. Подсчет нулей аналогичен. См. Статью о весах Хэмминга, где приведены примеры эффективной реализации.
Инверсия [ править ]
Найдите первый [ править ]
Сжатие [ править ]
Преимущества и недостатки [ править ]
Битовые массивы, несмотря на их простоту, имеют ряд заметных преимуществ перед другими структурами данных для тех же проблем:
Приложения [ править ]
Из-за своей компактности битовые массивы находят множество применений в областях, где пространство или эффективность имеют решающее значение. Чаще всего они используются для представления простой группы логических флагов или упорядоченной последовательности логических значений.
Битовые массивы также являются полезной абстракцией для изучения потоков сжатых данных, которые часто содержат элементы, занимающие части байтов или не выровненные по байтам. Например, сжатое представление кодирования Хаффмана одного 8-битного символа может иметь длину от 1 до 255 бит.
Языковая поддержка [ править ]
Хотя Standard ML не поддерживает битовые массивы, Standard ML из Нью-Джерси имеет расширение, BitArray структуру, в своей библиотеке SML / NJ. Он не имеет фиксированного размера и поддерживает операции с наборами и битовые операции, включая, что необычно, операции сдвига.
В Haskell в настоящее время также отсутствует стандартная поддержка поразрядных операций, но и GHC, и Hugs предоставляют Data.Bits модуль с различными побитовыми функциями и операторами, включая операции сдвига и поворота, а «распакованный» массив над логическими значениями может использоваться для моделирования битового массива, хотя это не поддерживает прежний модуль.
В Perl строки могут использоваться как расширяемые битовые массивы. Им можно управлять с помощью обычных побитовых операторов (
В Ruby вы можете получить доступ (но не установить) бит целого числа ( Fixnum или Bignum ) с помощью оператора скобки ( [] ), как если бы это был массив бит.