Битовые маски – Учебник

6.3

О чём этот урок

В приложении есть настройки-переключатели: уведомления, тёмная тема, автосохранение, звук. Каждая – это «включено» или «выключено», то есть ровно один бит информации, поэтому все четыре удобно хранить не четырьмя переменными, а одним числом. Пусть сейчас settings = 165, то есть 10100101:

бит:    7  6  5  4  3  2  1  0
знач:   1  0  1  0  0  1  0  1
смысл:  ?  ?  ?  ?  зв ас тт ув

Нижняя строка – наша договорённость: бит 0 хранит уведомления, бит 1 – тёмную тему, бит 2 – автосохранение, бит 3 – звук. Такая договорённость называется раскладкой битов и существует только в голове у программиста: само число о ней ничего не знает, 165 остаётся обычным числом 165.

Читаем по раскладке: уведомления включены (бит 0 = 1), тёмная тема выключена (бит 1 = 0), автосохранение включено (бит 2 = 1), звук выключен (бит 3 = 0).

Теперь главное – четыре вопросительных знака слева. Число мы взяли восьмибитное, разрядов в нём восемь, а настроек всего четыре, поэтому смысл назначен только младшим четырём разрядам. У битов 4–7 никакой инструкции нет, и что там лежит – сейчас неважно: может, это запас под будущие настройки, может, чужие данные, упакованные в то же число, может, просто мусор. Мы за них не отвечаем и не пытаемся их толковать.

Но раз мы за них не отвечаем – мы обязаны их сохранить. Любая наша операция должна оставить 1010 в старшей половине ровно таким, каким его нашла. Отсюда и требование «не тронув остальное», которое дальше встретится в каждой формуле: это не придирка, а единственный способ работать с числом, часть которого принадлежит не тебе.

Четыре вопроса, на которые программа должна уметь отвечать:

включена ли тёмная тема?
включить звук, не тронув остальное;
выключить уведомления, не тронув остальное;
переключить автосохранение – было включено, стало выключено, и наоборот.

Главная трудность видна сразу: settings – это число, а не список. Написать settings[1] нельзя, обратиться к «биту номер 1» напрямую язык не даёт. Значит, нужен приём, который выделяет из числа один разряд и оставляет остальные в покое, – битовая маска.

В этом уроке: что такое маска и как её строят из 1 << k; четыре формулы – проверить, включить (|), выключить (& ~) и переключить (^) бит; почему флаги нельзя складывать и вычитать; чем отличаются вопросы «включён хотя бы один бит маски» и «включены все»; как достать из числа целое поле из нескольких битов и как перебрать все флаги циклом.

Разминка. Прежде чем читать дальше, попробуйте составить выражение хотя бы для первого вопроса, пользуясь только &, |, ^, ~ и сдвигами.

Маска: трафарет для битов

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

Отсюда главная мысль урока, которую дальше мы будем только раскрывать:

Маска отвечает на вопрос «какие биты трогаем», а операция – на вопрос «что мы с ними делаем».

Одна и та же маска 00000100 с операцией & проверяет автосохранение, с | – включает его, с ^ – переключает. Меняется не маска, а операция рядом с ней.

Строятся маски из идиом прошлого урока:

один бит – 1 << k: 1 << 3 даёт 8, то есть 00001000;
несколько битов – объединяем по ИЛИ: (1 << 1) | (1 << 3) даёт 10, то есть 00001010;
младшие n битов – (1 << n) - 1.

Последняя формула выглядит загадочно, но объясняется в одну строку. 1 << 4 – это 00010000; вычитаем единицу, заём проходит по всем нулям справа и превращает их в единицы: 00001111. Отсюда и знакомое 0xFF – это (1 << 8) - 1, маска младшего байта, которой мы уже пользовались в уроках 5.2 и 6.1, не называя её маской.

Маска работает как трафарет: сквозь единицы биты числа видны, нули закрывают всё остальное. Что именно произойдёт с открытыми битами, решает операция рядом с маской.

Проверка: включён ли бит

Два способа, и оба стоит знать:

(x >> k) & 1 – подвинуть бит в младший разряд и отрезать остальное; результат ровно 0 или 1;
x & (1 << k) – ничего не двигать, просто погасить всё, кроме нужного разряда.

У второго способа есть нюанс, на котором спотыкаются: он возвращает не единицу, а вес разряда. 165 & (1 << 2) равно 4, а не 1. Для if это неважно – любое ненулевое число истинно (блок 3), и запись if x & MASK: встречается в реальном коде чаще всех прочих. А вот сравнивать с единицей нельзя: условие x & 4 == 1 ложно всегда, при любом x. Нужен именно 0/1 – берите первый способ или пишите явное != 0.

Проверим тёмную тему, это бит 1:

  10100101   (165)
& 00000010   (маска 1 << 1)
= 00000000   (0)

Ноль – тёмная тема выключена. Первый вопрос закрыт.

Установка: включить бит

Формула – x | (1 << k), и следует она прямо из свойств ИЛИ из урока 6.1: бит | 1 = 1, бит | 0 = бит. В разряде маски бит поднимается принудительно, во всех остальных остаётся как был.

Включаем звук, это бит 3:

  10100101   (165)
| 00001000   (маска 1 << 3)
= 10101101   (173)

Полезное свойство: включить уже включённый бит безопасно, число просто не изменится. Повторный вызов ничего не ломает, и проверять текущее состояние перед установкой не нужно.

Именно этим | отличается от +, и разница здесь не косметическая. 165 + 8 тоже даст 173 – кажется, что сложение работает. Но 173 + 8 даст уже 181: бит был поднят, сложение дало перенос, и единица уехала в чужой разряд, включив настройку, которую никто не просил. Флаги нельзя складывать, маски можно только объединять.

Сброс: выключить бит

Здесь нужна «маска наоборот» – x & ~(1 << k). Разберём по шагам: 1 << 0 даёт 00000001, оператор ~ переворачивает все биты и получается 11111110. Это маска «сохранить всё, кроме нулевого бита»: там, где единицы, & оставляет биты в покое (бит & 1 = бит), а единственный ноль гасит выбранный разряд.

Выключаем уведомления, это бит 0:

  10100101   (165)
& 11111110   (маска ~(1 << 0))
= 10100100   (164)

Оговорка про Python, прямо из урока 6.1: print(~1) выведет -2, и это пугает. Но работает всё правильно – у int нет фиксированной ширины, слева у ~1 бесконечная цепочка единиц, а она как раз и означает «все прочие разряды сохранить, сколько бы их ни было». Ограничивать маску до 0xFF не нужно.

И типичная ошибка, которую стоит увидеть заранее: сбросить бит вычитанием, x - (1 << k). Если бит был поднят, ответ совпадёт – и код будет выглядеть рабочим сколько угодно долго. А если бит уже сброшен, вычитание уйдёт в заём и испортит соседей: 164 - 1 даёт 163, то есть 10100011 – уведомления снова включились, а заодно включилась и тёмная тема, которую не трогали. Запись x & ~маска безопасна при любом исходном состоянии.

Переключение: XOR

Третья операция – x ^ (1 << k), и она снова следует из таблицы истинности: бит ^ 1 – инверсия бита, бит ^ 0 – бит без изменений.

Переключаем автосохранение, это бит 2:

  10100101   (165)
^ 00000100   (маска 1 << 2)
= 10100001   (161)

Автосохранение было включено – выключилось. Применим ту же операцию ещё раз, и вернётся 165. Это ровно обратимость XOR из урока 6.1, (x ^ k) ^ k = x, только теперь у неё появился бытовой смысл: переключатель.

Разница между тремя операциями в одну фразу: | и & ~ знают, каким бит должен стать, и приводят его к этому состоянию независимо от текущего; ^ этого не знает – ему важно лишь, чтобы состояние сменилось на противоположное.

Три операции, одна маска

Ниже – тот же виджет, что в уроке 6.1, но заряженный нашими настройками: a – это 165, b – маска бита звука. Что стоит попробовать:

как есть, операция |: бит 3 поднялся, остальные семь разрядов не шелохнулись – сравните строку a и строку результата столбик за столбиком;
b = 2, операция &: результат нулевой – тёмная тема выключена;
b = 254, операция &: погас младший бит, уведомления выключены (254 – это и есть ~1 в пределах восьми битов);
b = 4, операция ^: автосохранение переключилось; нажмите мысленно ещё раз – вернётся обратно;
b = 5, операция &: маска сразу из двух битов, результат равен 5 – обе настройки включены. Этот случай разберём отдельно в следующем разделе.

Несколько битов одной операцией

Маска не обязана содержать одну единицу. Все три формулы работают с группой битов без единого изменения:

включить набор: x | (DARK | SOUND);
выключить набор: x & ~(DARK | SOUND);
переключить набор: x ^ (DARK | SOUND).

А вот проверка на группе распадается на два разных вопроса, и путать их дорого:

Вопрос	Формула	Пример при `x = 165`
Включён хотя бы один бит маски?	`x & M != 0`	`M = 9` (уведомления и звук): `165 & 9` = 1, не ноль → да
Включены все биты маски?	`x & M == M`	`M = 5` (уведомления и автосохранение): `165 & 5` = 5 → да. А для `M = 9` получится $1 \ne 9$ → нет
Выключены все биты маски?	`x & M == 0`	`M = 10` (тёмная тема и звук): `165 & 10` = 0 → да

Смысл проверки x & M == M стоит проговорить отдельно: & оставляет от маски только те биты, которые есть и в числе. Если после такой фильтрации маска уцелела целиком, значит все её биты в числе были подняты. Потерялся хоть один – результат окажется меньше маски.

Флаги настроек целиком

# Имена константам дают не для красоты: выражение settings & 4
# через месяц не расшифрует и автор.
NOTIFY   = 1 << 0    # 00000001
DARK     = 1 << 1    # 00000010
AUTOSAVE = 1 << 2    # 00000100
SOUND    = 1 << 3    # 00001000

settings = 165
print(f'{settings:08b}')                # 10100101

# Проверка – два способа
print(settings & DARK)                  # 0 – вес разряда, здесь ноль
print((settings >> 1) & 1)              # 0 – ровно 0 или 1
if settings & AUTOSAVE:
    print('автосохранение включено')    # напечатается

# Включить, выключить, переключить
print(f'{settings | SOUND:08b}')        # 10101101 – звук включён
print(f'{settings & ~NOTIFY:08b}')      # 10100100 – уведомления выключены
print(f'{settings ^ AUTOSAVE:08b}')     # 10100001 – автосохранение переключено
print(settings)                         # 165 – само число не изменилось

# Группа битов сразу
both = NOTIFY | AUTOSAVE
print(settings & both != 0)             # True  – включён хотя бы один
print(settings & both == both)          # True  – включены оба
print(settings & (NOTIFY | SOUND) == (NOTIFY | SOUND))   # False – звук выключен

# А так делать нельзя: на уже сброшенном бите вычитание уходит в заём
off = settings & ~NOTIFY                # 164 = 10100100
print(f'{off - NOTIFY:08b}')            # 10100011 – испорчены два чужих бита
print(f'{off & ~NOTIFY:08b}')           # 10100100 – а маска ничего не сломала

Достать поле из нескольких битов

Шаг за пределы «да/нет». В один int часто пакуют не флаги, а небольшие числа – тогда маска работает в паре со сдвигом:

(x >> k) & ((1 << n) - 1) – подвинуть поле в младшие разряды и отрезать ровно n битов.

Ровно это мы делали в уроке 6.2, распаковывая цвет: (color >> 16) & 0xFF. Просто там n было равно восьми, и маску мы записали шестнадцатеричной константой, не выводя формулу.

Другой пример – права доступа в Unix, о которых шла речь в 6.1. Число 0o755 – это девять битов, по три на владельца, группу и остальных:

владелец: (rights >> 6) & 0o7 = 7 – чтение, запись, выполнение;
группа: (rights >> 3) & 0o7 = 5 – чтение и выполнение;
остальные: rights & 0o7 = 5 – то же самое.

А проверить одно право внутри поля – снова маска: «может ли группа писать» – это бит записи (вес 2) внутри группы, то есть rights & (0o2 << 3). Для 0o755 получится 0 – не может.

Кстати, вот и причина, по которой права записывают именно восьмеричным числом (уроки 2.3 и 6.1): три бита ровно укладываются в одну восьмеричную цифру, поэтому в записи 755 границы полей видны глазами, без всякого перевода.

Все настройки за один проход

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

В виджете ниже программа перебирает биты от нулевого до третьего, на каждом шаге строит маску 1 << i и печатает название настройки, если бит поднят. Следите за строкой mask: она меняется на каждой итерации, а settings остаётся нетронутым – проверка ничего не портит.

Где маски встречаются на самом деле

Пять сюжетов, коротко.

Права доступа и системные вызовы. За командой chmod 755 стоят ровно те маски, которые мы только что разбирали. Флаги открытия файла собираются объединением: os.open(path, os.O_WRONLY | os.O_CREAT | os.O_APPEND).
Библиотеки Python. Далеко ходить не надо: re.search(pattern, text, re.IGNORECASE | re.MULTILINE) – это объединение флагов маской. Такую запись вы наверняка уже видели, не зная, что происходит внутри.
Форматы и протоколы. Поля в заголовке TCP-пакета, в PNG, во флагах IP не выровнены по байтам – их читают сдвигом и маской. Маска подсети из блока 14 – это буквально ip & mask.
Аппаратура. Регистр устройства: один бит включает питание, другой – прерывания. Записать туда число целиком нельзя, соседние биты нужно сохранить, поэтому | маска и & ~маска – единственный корректный способ.
Битовые множества. Множество чисел из небольшого диапазона хранят одним числом: элемент i принадлежит множеству, если поднят бит i. Тогда объединение множеств – это a | b, пересечение – a & b, разность – a & ~b, и каждая операция выполняется за одну инструкцию процессора вместо цикла по элементам.

И честная оговорка, в тон двум прошлым урокам. Если вы пишете обычную программу на Python, для настроек удобнее словарь, dataclass или enum.Flag из стандартной библиотеки – последний, кстати, устроен ровно на масках, просто прячет их за именами. Маски руками нужны там, где формат данных задан не вами – файлы, протоколы, железо, – либо где счёт идёт на биты и такты. Но читать их уметь надо в любом случае: иначе половина чужого кода останется набором загадочных символов.

Шпаргалка

Всё, что стоит держать перед глазами. Здесь M – маска, обычно 1 << k:

Задача	Формула	Почему работает
Маска бита k	`1 << k`	единица переезжает в разряд k
Маска младших n битов	`(1 << n) - 1`	заём превращает нули в единицы
Проверить бит	`x & M`, или `(x >> k) & 1`	`&` гасит всё, кроме разрядов маски
Включить бит	`x \| M`	`бит \| 1 = 1`, остальные не тронуты
Выключить бит	`x & ~M`	`~M` – все единицы, кроме разряда k
Переключить бит	`x ^ M`	`бит ^ 1` – инверсия, `бит ^ 0` – без изменений
Все биты маски подняты?	`x & M == M`	маска пережила фильтрацию целиком
Хотя бы один поднят?	`x & M != 0`	что-то уцелело
Достать поле из n битов	`(x >> k) & ((1 << n) - 1)`	подвинуть и отрезать

Ответы к задаче из начала урока

Все четыре вопроса решаются одной строкой каждый. При settings = 165:

тёмная тема: settings & (1 << 1) = 0 → выключена;
включить звук: settings | (1 << 3) → 173;
выключить уведомления: settings & ~(1 << 0) → 164;
переключить автосохранение: settings ^ (1 << 2) → 161.

Коротко

Битовая маска – число, где единицами отмечены интересующие нас разряды. Маска отвечает на вопрос «какие биты трогаем», операция рядом с ней – на вопрос «что мы с ними делаем».
Строится маска из идиом сдвига: 1 << k – один бит, (1 << n) - 1 – младшие n битов, объединяются маски по |. Знакомое 0xFF – это (1 << 8) - 1.
Четыре формулы: проверить – x & M или (x >> k) & 1, включить – x | M, выключить – x & ~M, переключить – x ^ M. Все они не трогают соседние разряды и безопасны при любом исходном состоянии бита.
Флаги нельзя складывать и вычитать: + даёт перенос, − – заём, и оба портят чужие разряды. 164 - 1 включает сразу две настройки, которых никто не просил.
x & M возвращает вес разряда, а не единицу: 165 & (1 << 2) = 4. Для if этого достаточно, а сравнивать с единицей нельзя – условие x & 4 == 1 ложно при любом x.
Для группы битов «включён хотя бы один» – это x & M != 0, «включены все» – x & M == M, «выключены все» – x & M == 0.
Поле из нескольких битов достают сдвигом вместе с маской: (x >> k) & ((1 << n) - 1). Так распаковывают цвет и права доступа 755.
Маска – обычное выражение, её можно вычислять: 1 << i внутри цикла превращает четыре отдельные проверки в один проход.