Битовая маска (от ), или просто маска, — двоичное число, применяемое для работы с отдельными битами или группами битов другого числа с помощью побитовых операций. Единицы в маске отмечают разряды, которые требуется прочитать или изменить, а нулевые разряды оставляют соответствующие биты нетронутыми (в некоторых операциях роли единиц и нулей меняются местами); саму операцию наложения маски называют маскированием. Маскирование опирается на побитовые конъюнкцию (И), дизъюнкцию (ИЛИ), исключающее ИЛИ и сдвиги, каждая из которых обрабатывает пару чисел поразрядно, поэтому подобранной маской можно затронуть в точности нужные биты, не влияя на соседние.
Битовые маски широко применяются в системном и прикладном программировании. С их помощью в одном числе компактно хранят набор логических признаков (флагов), представляют множества и их операции, читают и изменяют отдельные разряды аппаратных регистров, маскируют прерывания, задают права доступа к файлам, выделяют из IP-адреса адрес сети (маска подсети), управляют обработкой элементов в векторных процессорах и накладывают изображения в растровой графике. Отдельный класс образуют «битовые трюки» — компактные комбинации побитовых операций, решающие такие задачи, как подсчёт единичных битов или поиск младшего установленного бита.
Основные понятия В памяти компьютера целые числа хранятся как последовательности битов фиксированной длины — байты, полубайты, машинные слова. Каждый бит принимает значение 0 или 1; разряды нумеруют справа налево, начиная с нуля, так что младший (крайний правый) бит имеет номер 0, а его вес равен единице. Отдельные разряды или их группы нередко наделяют самостоятельным смыслом — например, одному биту сопоставляют признак «включено/выключено», а группе соседних битов (битовому полю) — небольшое целое значение.
Обычные арифметические операции затрагивают число целиком и не позволяют адресовать конкретный разряд. Эту задачу решают побитовые операции, которые применяют логическую функцию к каждой паре одноимённых битов двух операндов независимо от остальных разрядов. Конъюнкция (И, AND) даёт в разряде 1 только если единицы стоят в обоих операндах; дизъюнкция (ИЛИ, OR) — если хотя бы в одном; исключающее ИЛИ (XOR) — если операнды в этом разряде различны; отрицание (НЕ, NOT) инвертирует каждый бит. Битовая маска — это второй операнд такой операции, разряды которого подобраны так, чтобы результат зависел лишь от выбранных битов первого операнда.
Построение масок Простейшая маска содержит единственный установленный бит и служит для адресации одного разряда. Её получают сдвигом единицы влево на позиций; в записи языка Си и родственных ему языков это выражение 1 << n, задающее число с единицей в разряде и нулями в остальных. Маску из подряд идущих младших единиц даёт выражение (1 << n) - 1: вычитание единицы из числа 1 << n превращает единственную единицу в младших единиц. Маску для группы битов, начинающейся не с нулевого разряда, дополнительно сдвигают влево.
Отрицание переводит маску в дополнительную: операция ~m заменяет в маске каждый 0 на 1 и наоборот, что используют, когда нужно, наоборот, сохранить все разряды, кроме выбранных. Составные маски, охватывающие несколько несмежных разрядов, собирают дизъюнкцией простых масок. На практике маски обычно не записывают числовыми константами, а определяют именованными константами (например, FLAG_A, FLAG_B), что делает код нагляднее и устойчивее к ошибкам.
Основные операции Ниже в примерах используется восьмиразрядное число ; разряды нумеруются с нуля справа налево.
Проверка состояния бита Конъюнкция числа с маской, содержащей единственную единицу в разряде , обнуляет все прочие разряды, поэтому результат отличен от нуля тогда и только тогда, когда бит установлен. Само численное значение результата при этом несущественно — проверяется лишь его равенство нулю. Проверка бита 4: 10110010 & 00010000 = 00010000
Установка бита Дизъюнкция числа с маской переводит в 1 те разряды, которым в маске соответствует единица, и не меняет остальные, поскольку для них операция сводится к «ИЛИ 0». Так отдельный бит включается независимо от его прежнего значения. Установка бита 3: 10110010 | 00001000 = 10111010
Сброс бита Обнуление разряда выполняется конъюнкцией с инвертированной маской x & ~(1 << n). В инвертированной маске единицы стоят во всех разрядах, кроме выбранного, поэтому все они сохраняются («И 1»), а единственный нулевой разряд обнуляет нужный бит. Сброс бита 5: 10110010 & 11011111 = 10010010
Переключение бита Исключающее ИЛИ даёт в разряде 1, когда биты операндов различны. Поэтому «XOR 1» инвертирует бит, а «XOR 0» оставляет его прежним, и операция с маской переключает выбранные разряды на противоположные, не затрагивая остальные. Переключение бита 1: 10110010 ^ 00000010 = 10110000
Выделение битового поля Группу соседних битов (битовое поле) считывают в два действия: конъюнкция с маской отбрасывает посторонние разряды, а сдвиг вправо переносит поле в младшие разряды, где оно интерпретируется как обычное целое число (порядок действий может быть обратным). Извлечение трёхразрядного поля из битов 5—3: (10110010 >> 3) & 00000111 = 00010110 & 00000111 = 00000110
Замена группы битов Чтобы записать в выбранные разряды значения из другого числа, не трогая прочие, объединяют два действия — сброс поля и запись нового значения: приёмник = (приёмник & ~маска) | (источник & маска). Здесь маска содержит единицы в замещаемых разрядах и нули в сохраняемых: конъюнкция с ~маска обнуляет поле приёмника, конъюнкция источника с маской оставляет только нужные биты источника, а дизъюнкция объединяет результаты.
Битовые трюки Комбинации нескольких побитовых операций образуют компактные идиомы, известные как битовые трюки (или broadword-приёмы, когда операция над машинным словом обрабатывает сразу все его биты). Классический пример — выражение x & (x - 1), обнуляющее младший установленный бит числа: вычитание единицы превращает младший единичный бит в ноль, а все нули правее него — в единицы, после чего конъюнкция с исходным числом гасит именно этот бит. Для числа : 10110010 & 10110001 = 10110000
Многие такие идиомы решают типовые задачи. Повторное применение x & (x - 1) с подсчётом числа итераций до обнуления даёт подсчёт единичных битов числа (), причём число проходов равно количеству единиц. Существуют и более быстрые способы подсчёта, использующие маски с чередующимися группами разрядов и работающие за фиксированное число операций независимо от числа единиц. Аналогичными приёмами находят младший или старший установленный бит, выделяют младший единичный бит выражением x & (-x), определяют, является ли число степенью двойки, и решают другие задачи. Значительная часть этих приёмов была собрана ещё в 1972 году в отчёте HAKMEM Лаборатории искусственного интеллекта Массачусетского технологического института.
Применение Флаги и наборы логических признаков Распространённое применение битовых масок — упаковка набора признаков «да/нет» (флагов) в одно целое число, где каждому признаку отведён отдельный бит. Проверку, установку и сброс отдельных флагов выполняют описанными выше операциями, а сами признаки задают именованными масками-константами. Так компактно хранят наборы настроек, атрибуты объектов или права доступа.
Многие языки программирования предоставляют для этого специальные средства. В языке Си группу битовых полей можно объявить внутри структуры, указав ширину каждого поля в битах (unsigned flag : 1;); компилятор сам генерирует нужные маскирование и сдвиги при обращении к полю. В платформе .NET перечисления, помеченные атрибутом [Flags], задают значениями-степенями двойки и объединяют побитовым ИЛИ, а принадлежность флага проверяют побитовым И; значение 0 по соглашению именуют None. В стандартной библиотеке C++ произвольный набор битов фиксированного размера представляет шаблон std::bitset, поддерживающий как побитовые операторы, так и обращение к отдельным битам и подсчёт единиц.
Представление множеств Целое число, в котором каждый бит соответствует одному элементу небольшого универсального множества, служит компактным представлением подмножества — битовым вектором (или характеристическим вектором): установленный бит означает наличие элемента. Теоретико-множественные операции при таком представлении сводятся к побитовым: пересечению соответствует конъюнкция, объединению — дизъюнкция, симметрической разности — исключающее ИЛИ, а проверка принадлежности элемента выполняется конъюнкцией с маской этого элемента. Представление экономно и позволяет обрабатывать сразу все элементы одной машинной командой, но применимо, лишь когда универсальное множество невелико.
На переборе подмножеств битового вектора основан класс методов динамического программирования «по подмножествам», где состоянием служит множество уже обработанных элементов, закодированное битовой маской. Такой подход применяют, например, в задаче коммивояжёра и других переборных задачах на множествах небольшой мощности. По этому же принципу позицию в настольной игре кодируют набором битов машинного слова () и выполняют запросы к ней побитовыми операциями.
Аппаратное и системное программирование При взаимодействии с оборудованием отдельные биты управляющих регистров и слов состояния отвечают за независимые функции устройства. Маскирование позволяет прочитать или изменить нужный разряд, не затрагивая остальные, что необходимо, поскольку запись в регистр целиком затронула бы и посторонние управляющие биты. Частный случай — маскирование прерываний: в регистре маски контроллера прерываний каждый бит разрешает или запрещает соответствующий источник прерывания, и установка бита исключает этот источник из обработки.
В Unix-подобных системах маской задаётся и то, какие права по умолчанию получают вновь создаваемые файлы. Маска режима создания файлов (umask) содержит единицы в тех разрядах прав, которые следует запретить: итоговые права вычисляются как конъюнкция запрошенных прав с инверсией маски. Так, при типичном значении маски и запросе прав файл получает права , поскольку (то есть ).
Векторные вычисления В векторных и SIMD-процессорах маска управляет тем, над какими элементами вектора выполняется операция. Биты специального регистра-маски сопоставлены элементам обрабатываемого вектора: там, где бит установлен, операция применяется, а где сброшен — элемент пропускается. Такой механизм называют и используют, в частности, для обработки условных ветвлений без переходов.
В расширении AVX-512 архитектуры x86 для этого выделены восемь регистров-масок k0—k7 разрядностью 64 бита; семь из них (k1—k7) могут служить операндом-предикатом инструкций, тогда как k0 обозначает безусловную обработку всех элементов. Поддерживаются два режима: при слиянии (принят по умолчанию) элементы результата, которым соответствует нулевой бит маски, сохраняют прежнее значение, а при обнулении — сбрасываются в ноль.
Компьютерные сети В IP-адресации маска подсети разделяет адрес на номер сети и номер узла: конъюнкция адреса с маской оставляет разряды сети и обнуляет разряды узла. Маска состоит из идущих подряд единиц, за которыми следуют нули, поэтому её задают также префиксной записью — числом единиц после косой черты (например, /24). Маски переменной длины (VLSM) и бесклассовая адресация (CIDR) позволяют делить адресное пространство на подсети разного размера.
В списках контроля доступа сетевого оборудования применяют — по смыслу инверсию обычной: её нулевые биты требуют точного совпадения соответствующих разрядов адреса, а единичные разрешают любое значение. В отличие от маски подсети, обратная маска может содержать чередующиеся нули и единицы, что позволяет задавать более гибкие правила отбора адресов. Так, маске подсети соответствует обратная маска .
Компьютерная графика