Что такое битовая маска

Работа с битовой маской

Доброго времени суток всем!
Часто возникает необходимость хранить данные логического типа для определенных таблиц. Например, таблица пользователей, такими данными могут быть поля активация пользователя, блокирование пользователя и др. Для таких полей удобно использовать битовую маску, при которой все данные хранятся в одном поле таблицы. Последнее время работаю с фреймверком Yii. Мне он нравится и во всем устраивает. Так вот, в процессе работы над несколькими проектами у меня появилось ряд наработок для работы с битовой маской под этот фреймверк.
Ими и хочу поделиться.

И так, создаем модель, наследуя от ActiveRecord:

Объявляем флаги. Для базового класса задаем флаг блокировки, который может быть использован для большинства моделей.

Значение константы соответствует номеру бита. Если биты будут одинаковые, флаги будут перетираться.
Дальше пишем методы для работы с флагами:

Модели, которые должны работать с флагами делаем наследниками этого класса и добавляем в таблицу поле flags.
Теперь, например, чтобы проверить, заблокирована ли новость, можно выполнить:

или чтобы заблокировать новость:

или, например, чтобы отфильтровать незаблокированные новости:

В модель можно добавить столько флагов, сколько позволяет разрядность типа поля в базе данных.

Если материал оказался полезным, я буду рад опубликовать продолжение данной темы, рассказав о готовых средствах администрирования флагов через CgridView и экшн с базовыми средствами настройки.

Источник

СОДЕРЖАНИЕ

Общие функции битовой маски

Биты маскировки в 1

Пример: Маскировка на чем выше полубайте (биты 4, 5, 6, 7) нижняя часть байта (биты 0, 1, 2, 3) без изменений.

Биты маскировки в 0

Пример: Маскировка от высших полубайт (биты 4, 5, 6, 7) нижней части байта (биты 0, 1, 2, 3) без изменений.

Запрос статуса бита

Пример: запрос состояния 4-го бита

Переключение битовых значений

Пример: переключение битовых значений

Чтобы записать произвольные единицы и нули в подмножество битов, сначала запишите 0 в это подмножество, а затем установите старшие биты:

Использование битовых масок

Аргументы к функциям

Тогда вызов функции выглядит так

Внутренне функция, принимающая подобное битовое поле, может использовать двоичный файл and для извлечения отдельных битов. Например, реализация glClear() может выглядеть так:

Обратные маски

сетевой адрес (трафик, который нужно обработать): 192.0.2.0

сетевой адрес (двоичный): 11000000.00000000.00000010.00000000

маска (двоичная): 00000000.00000000.00000000.11111111

Исходный / исходный-подстановочный знак 0.0.0.0 / 255.255.255.255 означает «любой».

Источник / подстановочный знак 198.51.100.2 / 0.0.0.0 совпадает с «хостом 198.51.100.2 «

Маски изображения

Хотя прозрачные цвета и альфа-каналы связаны (поскольку используются для одних и тех же целей), это методы, которые не включают смешение пикселей изображения путем двоичного маскирования.

Хеш-таблицы

Пример как по модулю, так и маскировки в C:

Источник

Битовые маски. Динамическое программирование по маскам

Битовые маски

Чаще всего массивы bool небольшого размера испольуются для обозначения некоторого подмножества объектов, выбранного из множества. Например, для обозначения элементов с индексами \(1\) и \(4\) (0-индексация), выбранных из множества из пяти элементов используется массив \(\\), или \(\<0, 1, 0, 0, 1\>\). Его можно представить в виде значения типа int : \(10010_2\) (индексация обычно начинается с младших битов числа, записываемых справа).

Операции с битовыми масками

Для работы с масками используются побитовые операции \(and, or, xor\), и битовые сдвиги.

int c = a & b; // маска c равна пересечению масок a и b

int c = a | b; // маска c равна объединению масок a и b

Для получения значения индивидуального бита используется комбинация битового сдвига вправо и операции \(and\). Сначала нам нужно сдвинуть биты маски так, чтобы нужный бит оказался самым младшим (находился справа). Затем нам нужно откинуть все остальные биты маски. Реализуется это следующим образом:

int bit = (a >> idx) & 1; // bit равен значению idx-го бита в маске a

Для установки значения определённого бита маски в true мы должны применить к нему операцию \(or\ true\). Реализуется это так (ко всем остальным битам применяется \(or\ false\), не имеющая никакого эффекта):

Для изменения значения определённого бита на противоположное, нужно применить к нему операцию \(xor\ true\). Ко всем остальным битам применяется \(xor\ false\), также не имеющая никакого эффекта:

Это самые распространённые операции, выполняемые с масками. Существует множество других, здесь не приведённых, но все они основаны на \(and, or, xor\), и сдвигах.

Динамическое программирование по подмножествам

Битовые маски часто используются как параметры для динамического программирования. Такой вид ДП называется ДП по маскам, или ДП по подмножествам.

Существует \(N\) городов, между некоторыми из которых есть дороги. Требуется обойти все города, вернувшись в первый, так, чтобы длина пути была минимальной.

Для простоты реализации примем, что города являются точками на геометрической плоскости, и между каждой парой есть путь, длина которого равна расстоянию между точками.

Запись \(\<0\>\) обозначает маску, обозначающую множество, состоящее только из элемента \(0\).

Формула перехода для ДП выглядит так:

Запись \(mask \backslash i\) обозначает множество \(mask\) без элемента \(i\).

Формула перехода обозначает следующее: чтобы попасть в вершину \(i\), нужно перейти в неё из какой-либо другой вершины \(j\), также входящей в \(mask\). Из всех таких вершин нужно выбрать такую, что общая длина пути в \(i\) будет наименьшей. Общая длина пути рассчитывается как длина пути в \(j\) (\(dp[mask \backslash i][j]\)) плюс длина пути из \(j\) в \(i\) (\(dst(j, i)\)).

Запись \(\mathbb\) обозначает множество всех вершин.

Может показаться, что порядок пересчёта такого ДП будет достаточно сложным. На самом деле это не так: заметьте что для пересчета \(dp[mask][i]\) нам нужно, чтобы уже был посчитан ответ для маски \(mask \backslash i\). Можно легко доказать, что в численном выражении \(mask \backslash i\) будет гарантированно меньше \(mask\), так как на некоторой позиции в \(mask\) будет находиться бит \(1\), а в \(mask \backslash i\) бит \(0\). Значит, можно просто пересчитывать ДП в порядке возрастания значения \(mask\) в численном выражении.

Источник

O.3 – Битовые манипуляции с побитовыми операторами и битовыми масками

В предыдущем уроке о побитовых операторах (O.2 – Побитовые операторы) мы обсудили, как различные побитовые операторы применяют логические операции к каждому биту в операндах. Теперь, когда мы понимаем, как они работают, давайте посмотрим, как они чаще всего используются.

Битовые маски

Чтобы управлять отдельными битами (например, устанавливать их в 1 или сбрасывать в 0), нам нужен способ идентифицировать конкретные биты, которыми мы хотим манипулировать. К сожалению, побитовые операторы не умеют работать с битовыми позициями. Вместо этого они работают с битовыми масками.

Битовая маска – это предопределенный набор битов, который используется для выбора того, какие конкретные биты будут изменены при последующих операциях.

Рассмотрим случай из реальной жизни, когда вы хотите покрасить оконную раму. Если не проявить осторожность, вы рискуете покрасить не только оконную раму, но и само стекло. Вы можете купить малярный скотч и приклеить его к стеклу и другим частям, которые не нужно красить. Затем, когда вы будете красить, малярный скотч будет блокировать попадание краски на всё, что вы не хотите красить. В конце концов, окрашиваются только немаскированные части (те части, которые вы хотите покрасить).

Битовая маска, по сути, выполняет ту же функцию для битов – битовая маска блокирует побитовые операторы от прикосновения к битам, которые мы не хотим изменять, и позволяет получить доступ к тем, которые мы действительно хотим изменить.

Давайте сначала узнаем, как определять простые битовые маски, а затем мы покажем, как их использовать.

Определение битовых масок в C++14

Самый простой набор битовых масок – это определение одной битовой маски для каждой битовой позиции. Мы используем нули, чтобы замаскировать биты, которые нам не нужны, и единицы, чтобы обозначить биты, которые мы хотим изменить.

Хотя битовые маски могут быть литералами, их часто определяют как символьные константы, поэтому им можно дать осмысленное имя и легко использовать повторно.

Поскольку C++14 поддерживает двоичные литералы, определить эти битовые маски очень просто:

Теперь у нас есть набор символьных констант, представляющих каждую битовую позицию. Мы можем использовать их для манипулирования битами (вскоре мы покажем, как это сделать).

Определение битовых масок в C++11 или в более ранних версиях

Поскольку C++11 не поддерживает двоичные литералы, то для установки символьных констант мы должны использовать другие методы. Для этого есть два хороших способа. Менее понятным, но более распространенным является использование шестнадцатеричных чисел. Если вам нужно напомнить о шестнадцатеричной системе счисления, еще раз посмотрите урок «4.13 – Литералы».

Это может быть трудно читать. Один из способов упростить задачу – использовать оператор сдвига влево, чтобы сместить бит в нужное место:

Проверка бита (чтобы узнать, установлен ли он в 1, или нет)

Теперь, когда у нас есть набор битовых масок, мы можем использовать их вместе с переменной битовых флагов для управления этими битовыми флагами.

Чтобы определить, установлен ли бит в 1 (включен, on) или сброшен в 0 (выключен, off), мы используем побитовое И в сочетании с битовой маской для соответствующего бита:

Эта программа напечатает:

Установка бита в 1

Чтобы установить бит в 1, мы используем присваивание с побитовым ИЛИ (оператор |= ) в сочетании с битовой маской для соответствующего бита:

Эта программа напечатает:

Мы также можем установить в 1 несколько бит одновременно, используя побитовое ИЛИ:

Сброс бита в 0

Чтобы сбросить бит в 0, мы используем побитовое И и побитовое НЕ вместе:

Эта программа напечатает:

Мы можем сбросить в 0 несколько бит одновременно:

Инвертирование бита

Чтобы инвертировать (переключить на противоположное) состояние бита, мы используем побитовое исключающее ИЛИ:

Эта программа напечатает:

Мы можем инвертировать несколько бит одновременно:

Битовые маски и std::bitset

Зачем это нужно? Функции позволяют изменять только отдельные биты. Побитовые операторы позволяют изменять сразу несколько битов.

Эта программа напечатает:

Делаем битовые маски более осмысленными

Присвоение нашим битовым маскам имен » mask1 » или » mask2 » говорит нам, какой бит обрабатывается, но не дает нам никакой индикации, для чего на самом деле используется этот битовый флаг.

Лучше всего давать вашим битовым маскам полезные имена, чтобы документировать значение ваших битовых флагов. Вот пример из игры, которую мы могли бы написать:

Вот тот же пример, реализованный с использованием std::bitset :

Когда битовые флаги наиболее полезны?

Проницательные читатели могут заметить, что приведенные выше примеры на самом деле не экономят память. 8 логических значений обычно занимают 8 байтов. Но в приведенных выше примерах используется 9 байтов (8 байтов для определения битовых масок и 1 байт для переменной флага)!

Битовые флаги имеют наибольший смысл, когда у вас много идентичных переменных-флагов. Например, в приведенном выше примере представьте, что вместо одного человека ( me ) у вас было бы 100. Если вы использовали 8 логических значений на человека (по одному для каждого возможного состояния), вы использовали бы 800 байт памяти. С битовыми флагами вы должны использовать 8 байт для битовых масок и 100 байт для переменных битовых флагов, в общей сложности 108 байт памяти – примерно в 8 раз меньше памяти.

Для большинства программ объем памяти, сэкономленный с помощью битовых флагов, не стоит дополнительного усложнения. Но в программах, где есть десятки тысяч или даже миллионы похожих объектов, использование битовых флагов может существенно сократить использование памяти. Это полезный способ оптимизации, если она вам понадобится.

Есть еще один случай, когда использование битовых флагов и битовых масок может иметь смысл. Представьте, что у вас есть функция, которая может принимать любую комбинацию из 32 различных параметров. Один из способов написать эту функцию – использовать 32 отдельных логических параметра:

Надеюсь, вы дадите своим параметрам более информативные имена, но суть здесь в том, чтобы показать вам, насколько плох длинный список параметров.

Если вместо этого вы определили функцию, используя битовые флаги, например:

Вы сможете использовать битовые флаги для передачи только тех параметров, которые вам нужны:

Это не только намного удобнее для чтения, но и, вероятно, будет более производительным, поскольку включает всего 2 операции (одно побитовое ИЛИ и одно копирование параметра).

Это одна из причин, по которой OpenGL, хорошо зарекомендовавшая себя библиотека трехмерной графики, решила использовать параметры битовых флагов вместо последовательностей множества логических параметров.

Вот пример вызова функции из OpenGL:

GL_COLOR_BUFFER_BIT и GL_DEPTH_BUFFER_BIT – это битовые маски, определенные следующим образом (в gl2.h ):

Битовые маски, включающие несколько битов

Хотя битовые маски часто используются для выбора одного бита, их также можно использовать для выбора нескольких битов. Давайте посмотрим на немного более сложный пример, в котором мы это делаем.

Цветные дисплеи, такие как телевизоры и мониторы, состоят из миллионов пикселей, каждый из которых может отображать точку цвета. Точка цвета состоит из трех световых лучей: красного, зеленого и синего (RGB – red, green, blue). Изменяя интенсивность этих цветов, можно получить любой цвет в цветовом спектре. Обычно яркость R, G и B для пикселя представлена 8-битовым целочисленным типом без знака. Например, красный пиксель будет иметь R = 255, G = 0, B = 0. У фиолетового пикселя R = 255, G = 0, B = 255. Средне-серый пиксель будет иметь R = 127, G = 127, B = 127.

При присвоении значений цвета пикселю, помимо R, G и B, часто используется 4-е значение, называемое A. «A» означает «альфа», и оно определяет, насколько прозрачным будет цвет. Если A = 0, цвет полностью прозрачный. Если A = 255, цвет непрозрачный.

R, G, B и A обычно хранятся как одно 32-битное целое число, в котором для каждого компонента используется 8 бит:

32-битное значение RGBA

биты 31-24	биты 23-16	биты 15-8	биты 7-0
RRRRRRRR	GGGGGGGG	BBBBBBBB	AAAAAAAA
красный	зеленый	синий	альфа

Следующая программа просит пользователя ввести 32-битное шестнадцатеричное значение, а затем извлекает из него 8-битные цветовые значения для R, G, B и A.

Эта программа дает следующий результат:

В приведенной выше программе мы используем побитовое И для запроса интересующего нас набора из 8 бит, а затем сдвигаем их вправо в 8-битное значение, чтобы мы могли распечатать его как шестнадцатеричное значение.

Резюме

Обобщим, как устанавливать, сбрасывать, инвертировать и запрашивать битовые флаги:

Чтобы запросить состояния битов, мы используем побитовое И:

Для установки битов в 1 (включения) используем побитовое ИЛИ:

Чтобы сбросить биты в 0 (очистить, выключить), мы используем побитовое И с побитовым НЕ:

Чтобы инвертировать состояния битов, мы используем побитовое исключающее ИЛИ:

Небольшой тест

Вопрос 1

Для заданной программы:

a) Напишите строку кода, чтобы сделать статью просматриваемой (включить флаг option_viewed ).

b) Напишите строку кода, чтобы проверить, была ли удалена статья (флаг option_deleted ).

c) Напишите строку кода, чтобы сбросить у статьи статус избранная (сбросить флаг option_favorited ).

Ожидаемый результат (при условии, что вы выполнили задание (а):

Вопрос 2

Дополнительное задание: почему следующие две строки идентичны?

Закон Де Моргана гласит, что если мы распространяем НЕ, нам нужно поменять ИЛИ на И, и наоборот. Поэтому,

Источник

Практическое применение (Битовые маски. )

Еще хотел бы рассказать про битовые маски и XOR.

Ты уже знаешь, что числа состоят из битов и над этими битами можно производить различные операции. Битовая маска – это когда мы храним много различных логических значений (true/false) в виде одного целого числа. При этом каждому boolean-значению соответствует определенный бит. Вот как это можно делать:

Числа-степени двойки (1,2,4,8,16,32,…) занимают в двоичном представлении числа всего по одному биту:

Число	Двоичное представление
1	0000 0001
2	0000 0010
4	0000 0100
8	0000 1000
16	0001 0000
19 (не степень двойки)	0001 0011
31 (не степень двойки)	0001 1111

Поэтому любое целое число можно рассматривать, как массив бит или массив boolean.

Вот как можно хранить различные логические значения в одном числе:

Теперь каждый бит равен 1, если соответствующая ему логическая переменная была true.

В нашем случае true были переменные a и c, значит число result равно 1+4 ==5

— Вроде понятно, что происходит.

— Ну, раз понятно, то пошли дальше.

В числе int 32 бита, один из них используется для знака, а еще 31 можно использовать для хранения значений 31-й булевской переменной.

— А в числе long 64 бита. Мы там можем хранить 63 логических переменных.

— Полсотни переменных в одном числе. Немало.

А где такое применяется?

— В основном там, где надо компактно хранить много информации об объектах. Когда хранишь много информации об объекте, всегда наберется пара десятков логических переменных. Вот их всех удобно хранить в одном числе.

Именно хранить. Т.к. пользоваться им в работе не так уж удобно.

— Кстати, как раз хотел спросить. А как нам обратно получить логические значение их числа?

— Это совсем не сложно. Вот допустим тебе нужно узнать, установлен ли 5-й бит числа в единицу или нет (2 в пятой степени – это 32). Вот как это можно проверить:

Т.е. фактически, для работы с битовыми масками нужны три операции:

1) Установить определенный бит в 0

2) Установить определенный бит в 1

3) Проверить, какое значение определенного бита.

Возьмем, например, бит номер 6.

Как установить в 1 бит 6?

Код	Описание
Как установить в 1 бит 6?
Как установить в 0 бит 6?
Как получить значение 6-го бита?

— Очень необычно, но не сложно. Я ж теперь уже крутой программист.

— И теперь еще маленькая подсказка. Как легко получить числа со снятым или установленным определенным битом: 01000000 или 10111111.

Для этого у нас есть операции сдвига >> и .

Вот 1 – это 2 в нулевой степени. Т.е. число с установленным нулевым битом. Нам надо число с установленным 6-м битом.

— Круто! Действительно полезная вещь для таких дел.

А если мне нужно число, где все биты 1, а один определенный – 0?

— Это тоже не сложно:

Т.е. все очень просто:

Код	Описание
Как установить в 1 бит 6?
Как установить в 0 бит 6?
Как получить значение 6-го бита?

— Выглядит не очень сложно. Но так сразу — не запомню.

— Зато, если встретишь где-то в чужом коде такое страшное выражение:

(1 — Само запомнится… Хорошо звучит. Спасибо за лекцию.

Источник