Битовая маска
Битовая маска — определённые данные, которые используются для маскирования — выбора отдельных битов или полей из нескольких битов из двоичной строки или числа.
Применение
Например, для получения значения пятого бита (считая слева) числа 10111011 нужно использовать маску 00001000 и применить операцию побитового логического «И» (конъюнкцию). В результате получится:
Подобное число на языках, использующих вместо логического типа числовые типы, например в Си, будет означать истину или ложь, если этот бит принимает соответствующее значение. На языках, например, C++, имеющие логические типы, необходимо произвести приведение типа.
Использование
Основные плюсы и недостатки:
Сфера использования в основном в интерфейсах, где приоритет отдаётся экономии памяти:
См. также
Полезное
Смотреть что такое «Битовая маска» в других словарях:
Маска (значения) — Маска: В Викисловаре есть статья «маска» Маска предмет, накладка на лицо, который надевается, чтобы не быть узнанным либо для защиты лица … Википедия
Битовая карта — (англ. bitmap, bitset, bit array) набор последовательно записанных двоичных разрядов, то есть последовательность (массив) битов. Содержание 1 Применение 1.1 В цифровых изображениях … Википедия
Маска подсети — В терминологии сетей TCP/IP маской подсети или маской сети называется битовая маска, определяющая, какая часть IP адреса узла сети относится к адресу сети, а какая к адресу самого узла в этой сети. Например, узел с IP адресом 12.34.56.78 и… … Википедия
Маска сети — В терминологии сетей TCP/IP маской подсети или маской сети называется битовая маска, определяющая, какая часть IP адреса узла сети относится к адресу сети, а какая к адресу самого узла в этой сети. Например, узел с IP адресом 12.34.56.78 и маской … Википедия
адресная маска — Битовая маска, используемая для выбора битов из адреса IP для адресации подсети. Маска имеет размер 32 бита и выделяет адреса IP сети и один или несколько битов адреса хоста. Иногда называется маской подсети. … … Справочник технического переводчика
Битовый вектор — Битовая карта (англ. bitmap, bitset, bit array) набор последовательно записанных двоичных разрядов, то есть последовательность (массив) битов. Содержание 1 Применение 1.1 В цифровых изображениях 1.2 … Википедия
Битовый массив — Битовая карта (англ. bitmap, bitset, bit array) набор последовательно записанных двоичных разрядов, то есть последовательность (массив) битов. Содержание 1 Применение 1.1 В цифровых изображениях 1.2 … Википедия
Вихрь Мерсенна — (англ. Mersenne twister, MT) генератор псевдослучайных чисел (ГПСЧ), разработанный в 1997 году японскими учёными Макото Мацумото (яп. 松本 眞) и Такудзи Нисимура (яп. 西村 拓士). Вихрь Мерсенна основывается на свойствах простых чисел Мерсенна… … Википедия
SSE4 — SSE4 новый набор команд микроархитектуры Intel Core, впервые реализованный в процессорах серии Penryn (не следует путать с SSE4A от AMD)[1]. Он был анонсирован 27 сентября 2006 года, однако детальное описание стало доступно только весной… … Википедия
SSE4.1 — SSE4 это новый набор команд Intel Core микроархитектуры, впервые реализованный в процессорах серии Penryn (не следует путать с SSE4A от AMD). Он был анонсирован 27 Сентября 2006, однако детальное описание стало доступно только весной 2007, свежее … Википедия
Использование битовых флагов и масок
В этой статье я постараюсь рассказать, как можно использовать биты и операции над ними. Я выбрал php для демонстрации, так как тем кто знает другие языки, понять примеры не должно составить труда.
Для чего можно использовать биты?
А использовать их можно как хранилище состояний. То есть что то вроде переключателей.
Можно сказать, что это 8 переменных типа boolean в 1 байте.
Многие компиляторы, сами приводят тип boolean к 1 биту, так что это не всегда позволит экономить место в памяти, но это и не единственная цель. Ещё это добавляет удобство, сгруппированность данных, проверки сразу нескольких состояний по так называемым маскам.
Битовые маски
Маской называют какой то набор бит, который используют для того что бы выбрать определённые биты из набора (переменной).
Например: 1 (0000 0001), 2 (0000 0010), 4 (0000 0100), 32 (0010 0000).
Можно конечно напрямую использовать числа, и составлять условия, но гораздо удобней давать каждому биту имя.
Как установить бит в числе не затрагивая другие?
Очень просто, вспомним операцию OR из предыдущей статьи.
Она вернёт установленный бит, если хотя бы в одном из операндов бит установлен.
В результате в $MyVar мы получим установленный бит, из FLAG_TWO
Давайте установим ещё один бит
И так, устанавливая 1 флаг, мы не затрагиваем другие.
Как проверить установлен ли бит?
Теперь вспомним операцию &. Операция вернёт установленный бит только если он установлен в обоих операндах.
То есть, сколько бы не было установленных бит, в нашей переменной, у нас вернётся либо 1 установленный бит либо не одного.
Что нам это даёт?
Если бит не установлен, то мы получим 0. Во многих языках 0 в условии расцениваеться как false.
Установленный же бит наоборот, вернёт какое то, не нулевое число. А во многих языках это true.
Значит можно проверять просто
Как проверить сразу несколько бит
Здесь нужно понимать очень важный момент. Проверка с помощью & может сработать не так как Вы ожидаете.
Условие выполнится если хотя бы один из битов маски установлен.
А что делать, если нужно проверить что бы все биты были установлены?
Нужно просто сравнить результат с маской.
Условие выполнится если все биты маски установлены.
Возможно, Вам понадобится проверить что только биты маски установлены, и больше не какие.
Тогда наоборот, сравните результат с самой переменной. Но особого смысла в этом нет, так как можно просто сравнить переменную и маску на равенство между собой.
Многие могли заметить, что после операции OR мы просто получаем сложившиеся числа. И часто это совпадает:
Но это не так.
Рассмотрим пример ниже
Так что не нужно путать OR и +.
Как сбросить бит?
Здесь немного сложнее.
Нам нужно получить все биты которые установлены в числе, кроме указанных.
Операция & вернёт биты установленные в обоих числах.
То есть если мы сделаем так
Мы получим то же самое число, так как в маске у нас все биты установлены, а значит если и в переменной бит установлен, то мы получим его установленным в результате.
Что бы отбросить в результате бит TWO, нам нужно просто сделать маску, в которой этот бит сброшен. То есть вот такую 1111 1101
И мы получим, что бит TWO в результате у нас сброшен.
Смотрим на разницу, между флагом, который нужно сбросить и маской, по которой сбрасываем
И видим что маска, это просто инверсия нашего бита, а команда инверсии у нас
Эта статья немного затянулась, поэтому на сегодня всё
Битовые маски. Динамическое программирование по маскам
Битовые маски
Чаще всего массивы bool небольшого размера испольуются для обозначения некоторого подмножества объектов, выбранного из множества. Например, для обозначения элементов с индексами \(1\) и \(4\) (0-индексация), выбранных из множества из пяти элементов используется массив \(\
Операции с битовыми масками
Для работы с масками используются побитовые операции \(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\) в численном выражении.
СОДЕРЖАНИЕ
Общие функции битовой маски
Биты маскировки в 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:
Практическое применение (Битовые маски. )
Еще хотел бы рассказать про битовые маски и 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 — Само запомнится… Хорошо звучит. Спасибо за лекцию.
