Битовая маска
Битовая маска — определённые данные, которые используются для маскирования — выбора отдельных битов или полей из нескольких битов из двоичной строки или числа.
Применение
Например, для получения значения пятого бита (считая слева) числа 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, свежее … Википедия
СОДЕРЖАНИЕ
Общие функции битовой маски
Биты маскировки в 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:
Битовое представление чисел
Так как на уровне схем почти вся логика бинарная, ровно такое представление и используется для хранения чисел в компьютерах: каждая целочисленная переменная указывает на какую-то ячейку из 8 ( char ), 16 ( short ), 32 ( int ) или 64 ( long long ) бит.
Эндианность
Единственная неоднозначность в таком формате возникает с порядком хранения битов — также называемый эндианностью. Зависимости от архитектуры он может быть разным:
Хотя big-endian более естественный для понимания — на бумаге мы ровно так обычно и записываем бинарные числа — по разным причинам на большинстве современных процессоров по умолчанию используется little endian.
Иными словами, «$i$-тый бит» означает «$i$-тый младший» или «$i$-тый справа», но на бумаге мы ничего не инвертируем и записываем двоичные числа стандартным образом.
Битовые операции
Помимо арифметических операций, с числами можно делать и битовые, которые интерпретируют их просто как последовательность битов.
Сдвиги
Битовую запись числа можно «сдвигать» влево ( x ) или вправо ( x >> y ), что эквивалентно умножению или делению на степень двойки с округлением вниз.
Обычное умножение и деление — не самые быстрые операции, однако все битовые сдвиги всегда работают ровно за один такт. Как следствие, умножение и деление на какую-то фиксированную степень двойки всегда работает быстро — даже если вы не используете сдвиги явно, компилятор скорее всего будет проводить подобную оптимизацию.
Побитовые операции
Все побитовые операции тоже работают за один такт, вне зависимости от типа данных. Для больших не вмещающихся в один регистр битовых последовательностей существует битсет.
Маски
Битовые операции таким образом часто используются операций над множествами, представляемыми битовыми мазками — например, в задачах на полный перебор или динамическое программирование.
Выделить i-й бит числа
Напомним, что нумерация идет с младших бит и начинается с нуля.
Получить число, состоящее из k единиц
Инвертировать все биты числа
Добавить i-й элемент в множество
Удалить i-й элемент из множества, если он есть
Также добавляет этот элемент, если его нет.
Знаковые числа
Целочисленные переменные делятся на два типа — знаковые (signed) и беззнаковые (unsigned).
Упражнение. Каких чисел больше: положительных или отрицательных?
Осторожно. В стандарте C/C++ прописано, что переполнение знаковых переменных приводит к undefined behavior, поэтому полагаться на описанную логику переполнения нельзя, хотя равно это скорее всего и произойдет.
128-битные числа
Общих регистров размера больше 64 в процессорах нет, однако умножение и несколько смежных инструкций могут использовать два последовательных регистра как один большой. Это позволяет быстро перемножать два 64-битных числа и получать 128-битный результат, разделенный на нижние биты и верхние.
Это весьма специфичная операция, и поэтому в языках программирования нет полноценной поддержки 128-битных переменных. В C++ однако есть «костыль» — тип __int128_t — который фактически просто оборачивает пару из двух 64-битных регистров и поддерживает арифметические операции с ними.
Базовые арифметические операции с ним чуть медленнее, его нельзя напрямую печатать, и деление и прочие сложные операции будут вызывать отдельную библиотеку и поэтому работать очень долго, однако в некоторых ситуациях он оказывается очень полезен.
Сегодня хочу поднять очень полезную, но не самую популярную в последнее время тему — использование поразрядных операций над двоичными числами, работа с битовыми масками и, соответственно, флагами. По сути всё вышеперечисленное — это звенья одной цепи и истории: как прятать хранить несколько значений (т.н. флагов) в одной численной переменной, а также как именно и где это использовать. К сожалению, всё чаще наблюдаю, что много современных программистов из «нового поколения» не работают с данным типом представлений вообще и, что ещё хуже, практически не знакомы или не слышали об этой идее. Всё дело в том, что подход достаточно низкоуровневый и по сегодняшним меркам весьма не прост с позиции высокой точки входа. Надеюсь, что эта небольшая статья поможет вам понять, разобраться или же просто вспомнить этот важный битовый навык.
Перед тем как начать, хочется сделать небольшое вступление и напомнить, что все десятичные числа могут быть представлены в двоичном виде, в котором каждый разряд является минимальной и неделимой единицей информации — битом; т.е. такая маленькая коробочка, в которую можно положить либо ноль (ложь), либо единицу (правда). Только так и ничего другого. Как перевести число из десятичной в двоичную систему (или любую другую) в интернете написано масса информации и повторяться смысла нет. Это самый базовый и начальный курс computer science, школьная программа информатики. Поэтому я подразумеваю, что читатель уже умеет это делать. В конечном итоге из десятичного числа у вас должен получиться ряд из нулей и единиц. К примеру, для десятичного числа 91 ряд будет выглядеть примерно следующим образом (рисовал на планшете, авторское исполнение 🙂 но, я уверен, в этом есть некоторая определённая прелесть):
Теперь про саму идею — мы будем хранить одно или множество значений в одном числе (переменной), где каждый бит будет прикреплён к какому-либо заранее предетерминированному флагу\значению\смыслу. Возьмём, к примеру классическую задачу организации доступа юзера и примем, что у нас на сайте есть абстрактные группы, в которых есть следующие виды «допусков»: чтение статей, создание статей, удаление статей, чтение комментариев, написание комментариев, удаление комментариев, создание юзеров и блокировка юзеров. Всего 8 штук и это число я взял не случайно — именно столько бит в байте, а значит все возможные комбинации этих групп мы можем уместить всего-лишь в одном байте. Выглядит это следующий образом:
Или вот пример из личного опыта — совсем недавно занимался обработкой изображений и по долгу службы работал с CMYK системой цветов. По задаче мне необходимо было обрабатывать цветовые каналы отдельно друг от друга или же вместе. В любых комбинациях, соответственно, для CMYK это 15 всевозможных комбинаций. Подобное множество запрограммировать «просто и быстро» — не просто и не быстро 🙂 Но, если применить битовые маски, где, скажем, 4й бит это С, 3й бит — М, 2й — Y и 1й — K, всё становится на порядок легче и проще! Можно передавать всевозможные комбинации используя всего-лишь один байт (и то, займём там только половину «полезной площади»).
Таблица истинности
Итого, мы умеем переводить числа в двоичное представление. Теперь необходимо вспомнить таблицу истинности (хотя, конечно, это не про «вспомнить», а про элементарную логику, которая обычно выводится — ничего запоминать не нужно). О таблице, которая описывает все логические функции — какие аргументы поступают на входе, какая применяется операция и какой результат на выходе. Всё это в сокращённом виде (для базовых функций AND, OR, XOR) выглядит так:
| A | B | AND | OR | XOR |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
Таблица истинности
Логические операторы
Как правило все вышеописанные логические функции представлены во всех языках программирования в том или ином виде и конкретно для «си-подобной» группы языков это, как правило, абсолютно всегда одинаковый синтаксис. Вы встретите это в C, С++, C#, PHP, JavaScript, Python и ещё много где. Это всё в некотором роде уже стало стандартом синтаксиса для битовых (bitwise) операций.
Оператор & для AND
Логическое И или же конъюнкция. Результатом работы данной логической операции является множество (т.к. на вход поступает два операнда из множеств нулей и единиц), вычисляемое по таблице истинности, т.е. если оба бита в текущем столбце строки являются единицами (или true ), то возвращаем тоже единицу. Так проходим по всем элементам нашей строки.
Вот ещё несколько примеров логического И (биты, которые «отработали» положительно я выделил жирным):
| dec | bin | AND | dec | bin | Result | dec | bin |
|---|---|---|---|---|---|---|---|
| 111 | 01101111 | & | 222 | 11011110 | = | 78 | 01001110 |
| 43 | 00101011 | & | 96 | 01100000 | = | 32 | 00100000 |
| 131 | 10000011 | & | 87 | 01010111 | = | 3 | 00000011 |
| 47 | 00101111 | & | 255 | 11111111 | = | 47 | 00101111 |
Примеры конъюнкции
Оператор | для OR
Логическое ИЛИ или же дизъюнкция. Здесь, в отличии от AND, нам для «положительного» результата необходимо, чтобы хотя бы один из операндов равнялся единицы. Без разницы левый, правый или оба — возвращаем 1, в противном случае — 0. Как видно из таблицы истинности для логического ИЛИ мы почти всегда будет получать единицу, кроме случая, когда оба операнда слева и справа равны нулю.
Также, как и в предыдущем примере, добавляю таблицу примером логического ИЛИ:
| dec | bin | OR | dec | bin | Result | dec | bin |
|---|---|---|---|---|---|---|---|
| 111 | 01101111 | | | 222 | 11011110 | = | 255 | 11111111 |
| 43 | 00101011 | | | 96 | 01100000 | = | 107 | 01101011 |
| 131 | 10000011 | | | 87 | 01010111 | = | 215 | 11010111 |
| 47 | 00101111 | | | 255 | 11111111 | = | 255 | 11111111 |
Примеры дизъюнкции
Оператор ^ для XOR
Исключающее ИЛИ или строгая дизъюнкция — моя любимая логическая операция, если, конечно, можно испытывать чувства к этому. Также известная как XOR или сложение по модулю 2, поразрядное дополнение, инвертирование по маске, жегалкинское сложение, логическое вычитание или логическая неравнозначность. Эта прекрасная операция вернёт вам единицу или true в том случае, если строго один (любой, но только один) операнд равен нулю.
| dec | bin | XOR | dec | bin | Result | dec | bin |
|---|---|---|---|---|---|---|---|
| 111 | 01101111 | ^ | 222 | 11011110 | = | 177 | 10110001 |
| 43 | 00101011 | ^ | 96 | 01100000 | = | 75 | 01001011 |
| 131 | 10000011 | ^ | 87 | 01010111 | = | 212 | 11010100 |
| 47 | 00101111 | ^ | 255 | 11111111 | = | 208 | 11010000 |
Примеры строгой дизъюнкции
Оператор битового смещения (сдвига) вправо >>
Самый простой оператор
, работающий с одним операндом (т.е. унарная операция) — это логическое НЕ, которое инвертирует наши входные данные на противоположные ( true на false и наоборот), т.е. если есть 1 — то возвращаем 0 и, соответственно, если 0 — то 1. Здесь без таблиц, всё более менее должно быть очевидно.
Есть только один ньюанс — инвертирование изменяет также знак числа. К примеру
Работа с битами
| n | dec | B7 | B6 | B5 | B4 | B3 | B2 | B1 | B0 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 2 | 4 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 3 | 8 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 4 | 16 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 5 | 32 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 6 | 64 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | 128 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Всего две эти операции дают нам возможность включать или отключать в нужном нам порядке нужные флаги. Как в массиве булевых переменных — зная индекс можно легко и просто получить доступ к значению: прочитать его или изменить. С разницей лишь в том, что занимать в память это будет на порядок меньше и оперирование такой структурой можно уместить в меньшее количество строк кода.
.NET C# пример перечисления
Давайте перенесём наш изначальный пример с ACL в код и создадим стандартый enum на языке C#:
Данная структура позволяет нам создавать перечисления с типом uint и организовать примитивный и очень легковесный ACL (access control list), т.е. систему доступов. Обратите также внимание, что каждый бит у нас пронумерован согласно степени двойки и увеличивается в два раза для каждого последующего элемента. Также важно оставлять первый элемент None с значением нуля, т.к. по-умолчанию структура принимает значение 0 — это считается хорошей и правильной практикой. Последним элементом идёт ALL равный инверсией None (т.е. заполнены все биты, все возможные варианты значений).
Здесь же вы можете заметить, что все последующие элементы «привязаны» к значениям степени двойки (1, 2, 4, 8, 16, 32…) — это те самые биты, которые мы и будем «устанавливать». К слову, записывать эти значения можно разными способами:
Обратите внимание на последний способ записи — очень удобно маркировать значения в бинарном представлении чисел просто отделяя дополнительными нулями.
В остальном Flags особо никак нам не помогает и даже не контролирует то, что мы можем ввести элемент НЕ из ряда степени двойки, а любой другой какой захотим — ошибки не будет.
.NET C# пример битовых манипуляций
Рассмотрим следующий пример. Для того, чтобы «разрешить» все операции на чтение, нам необходимо «нанизать» нужные доступы через ИЛИ, т.е. каждый элемент который начинается с строки READ_ :
И чтобы удалить, к примеру, возможность чтение комментариев, воспользуемся XOR:
Для того, чтобы проверить включен ли нужный нам флаг — используем следующую конструкцию из логического И и сравнения:
Все эти операции (добавить, проверить, удалить) для наглядности и тренировки можно завернуть в специальный враппер-оболочку, чтобы абстрагировать нашу работу с AccessLevels и получить более высокоуровневый подход. Создадим класс BitOperations :
Данный код вы можете найти в моём «блогерском» репозитории здесь.
Дополнительно
Для тренировки и самоконтроля битовых калькуляций можно использовать разнообразные бесплатные инструменты. К примеру, в онлайне есть прекрасный инструмент bitwisecmd, которые позволяет проводить любые битовые операции над числами (AND, OR, XOR, битовые смещения и т.д.). А также, вы можете посмотреть мой старый проект BitJuggling на GitHub, который позволяет делать всё то же самое, но только как стандартное приложение Windows:
Выводы
Надеюсь, что данная статья поможет вам разобраться или вспомнить о битовых операциях, тонкостях работы и использования. Порой этот простой и невероятно быстрый способ может очень сильно облегчить жизнь и решить сложные и объёмные вещи — малой кровью. Спасибо за чтение, жду ваших комментариев и хорошего вам времени суток! 🙂
Использование битовых флагов и масок
В этой статье я постараюсь рассказать, как можно использовать биты и операции над ними. Я выбрал 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 в результате у нас сброшен.
Смотрим на разницу, между флагом, который нужно сбросить и маской, по которой сбрасываем
И видим что маска, это просто инверсия нашего бита, а команда инверсии у нас
Эта статья немного затянулась, поэтому на сегодня всё