Битовые флаги в программировании

Битовые флаги – компактное представление множества булевых признаков внутри целого числа, где каждый бит кодирует состояние одного признака: 1 – установлен (истина), 0 – снят (ложь). Такой способ используется в системном программировании, сетевых протоколах, графике, доступах/правами, кешировании состояний и в олимпиадно-экзаменационных задачах.
Для ЕГЭ по информатике тема объединяет разделы булевой алгебры, представления чисел в двоичном виде, побитовых операций и логики предикатов. В этой статье последовательно изложены: строгая математическая модель, стандарты кодирования (степени двойки, маски), операционная семантика AND/OR/XOR/NOT и сдвигов, правила корректности, инженерные соглашения, мини-шпаргалка, типичные ошибки и 5 упражнений формата ЕГЭ с подробными решениями.

Формальная модель

1. Множества признаков и битовые представления
   

   Пусть задан конечный набор признаков

   U = {p₀, p₁, …, p_{k−1}}.

   Любое подмножество S ⊆ U кодируем целым числом F ∈ [0, 2^k − 1] через характеристический вектор:

   бит i в F равен 1  ⇔  p_i ∈ S.

   Битовое смещение i соответствует весу 2^i. Тогда:

   F = ∑_{i=0}^{k−1} b_i · 2^i,   где b_i ∈ {0,1}.

2. Битовая маска
   

   Маска M – число, у которого интересующие биты выставлены в 1, прочие в 0. Маска выбирает, изменяет или проверяет поднабор признаков.

3. Операционная семантика
   

   На уровне битов для целых неотрицательных чисел определены операции:

   • Побитовое И: F AND M – очищает все биты, не входящие в маску (прозрачность по 0).

   • Побитовое ИЛИ: F OR M – устанавливает биты, включённые в маску (прозрачность по 1).

   • Побитовое XOR: F XOR M – инвертирует биты маски, остальные сохраняет.

   • Побитовое НЕ: NOT F – инвертирует все биты слова (в практике используют с маской).

   • Сдвиги: F << s (влево), F >> s (вправо) – умножение/деление на 2^s для беззнаковых при отсутствии потерь.

Кодирование флагов и соглашения

1. Стандарт кодирования (степени двойки)
   

   Назначим каждому признаку уникальную степень двойки:

   FLAG_A = 1         = 1 << 0

   FLAG_B = 2         = 1 << 1

   FLAG_C = 4         = 1 << 2

   FLAG_D = 8         = 1 << 3

   ...

   Тогда набор флагов задаётся суммой (эквивалентно OR):

   F = FLAG_A OR FLAG_C OR FLAG_D   // F = 1 + 4 + 8 = 13.

2. Не пересекать биты
   

   Каждый флаг имеет свой непересекающийся бит (никаких «1» в одинаковых позициях у разных флагов), иначе теряется однозначность.

3. Размер слова
   

   Выбирайте ширину: 8/16/32/64 бита. Для масок, выходящих за диапазон, фиксируйте тип «беззнаковый» и проверяйте переполнение.

Алгебра масок: базовые операции и корректность

Пусть F – текущее множество флагов, MASK – маска (один или несколько флагов).

1. Установка флага(ов)
   

   F ← F OR MASK

   Корректность: после операции каждый бит i из MASK становится 1, остальные не меняются.

2. Снятие (сброс) флага(ов)
   

   F ← F AND (NOT MASK)

   Корректность: биты из MASK обнуляются, остальные сохраняются.

3. Инверсия (переключение) флага(ов)
   

   F ← F XOR MASK

   Корректность: биты из MASK меняют состояние на противоположное, прочие неизменны.

4. Проверка установленности флага(ов)
   

   установлен ли один флаг p_i?      (F AND FLAG_i) ≠ 0

   установлен ли ровно набор M?      (F AND M) = M

   установлен ли хотя бы один из M?  (F AND M) ≠ 0

5. Выделение подмаски
   

   Чтобы оставить только интересующие биты:

   F_sub = F AND M

   Это «проекция» состояния на подмножество признаков.

Сдвиги и позиционные поля

1. Позиционные флаги
   

   Флаг сдвигается в нужную позицию:

   FLAG(i) = 1 << i

   Проверка:

   (F >> i) AND 1   // бит i

2. Битовые поля (несколько бит под значение)
   

   Если атрибут хранит значение v в w битах, начинается с позиции s:

   MASK_field = ((1 << w) − 1) << s

   запись:   F ← (F AND (NOT MASK_field)) OR ((v << s) AND MASK_field)

   чтение:   v = (F AND MASK_field) >> s

   Ограничение: 0 ≤ v < 2^w.

Инженерные правила и безопасность

1. Типобезопасность. Предпочитайте беззнаковые целые для побитовых операций, чтобы исключить неопределённости с арифметическим сдвигом вправо.
2. Константные определения. Все FLAG_* и MASK_* оформляйте как константы одной ширины.
3. Скобки и приоритеты. Явно расставляйте скобки: F AND (NOT MASK).
4. Нулевые и пересекающиеся маски. Проверяйте, что MASK ≠ 0 и не пересекает чужие флаги при определениях.
5. Композиция. Не смешивайте логические (&&, ||) и побитовые (&, |) операторы – у них разная семантика.
6. Документация масок. Таблица флагов с описанием назначения битов – обязательна для совместной разработки и проверок.

Мини-шпаргалка 

Задать флаг i: 
F ← F OR (1 << i)

Снять флаг i:
F ← F AND (NOT (1 << i))

Инвертировать флаг i:
F ← F XOR (1 << i)

Проверить флаг i:
((F AND (1 << i)) ≠ 0)

Проверить «все флаги из M установлены»:
(F AND M) = M

Проверить «хотя бы один из M установлен»:
(F AND M) ≠ 0

Сбросить всё, кроме M:
F ← F AND M

Битовое поле ширины w на позиции s:
MASK = ((1 << w) − 1) << s
запись: F ← (F AND (NOT MASK)) OR ((v << s) AND MASK)
чтение: v = (F AND MASK) >> s

Типичные ошибки и профилактика

• Смешение логических и побитовых операторов. Ошибка: if (F && MASK) вместо if (F & MASK). → Всегда использовать побитовые для масок.
• Знаковые типы и сдвиг вправо. На некоторых языках >> для знаковых – арифметический сдвиг (копирует знак). → Использовать беззнаковые типы/операторы.
• Неправильная проверка «все биты установлены». Ошибка: (F OR M) = F. → Верное: (F AND M) = M.
• Пересекающиеся константы флагов. Два флага делят один и тот же бит. → Назначать строго 1 << i с уникальным i.
• Слишком широкая маска при очистке. Ошибка: F AND NOT 0xFF при 8-битном поле в слове иной ширины. → Строго вычисляйте MASK_field.
• Выход значений за ширину поля. Нет проверки v < 2^w. → Вводить утверждение/маску v = v AND ((1 << w) − 1) перед записью.

Связь с подготовкой к ЕГЭ по информатике

• Булева алгебра: практическая работа с И/ИЛИ/НЕ/XOR и таблицами истинности.
• Двоичное представление: перевод чисел из десятичной системы, работа с «степенями двойки».
• Логика предикатов: формулировки проверок «все/ни одного/хотя бы один».
• Алгоритмизация: компактное хранение состояний в задачах на перебор, графы (посещённость), динамику по подмножествам.
• Оценка сложности: экономия памяти и времени на проверках/изменениях множеств. 

Пять упражнений – с подробными решениями

Упражнение 1. «Конструирование маски и проверка»
Условие. Даны флаги P0=1<<0, P1=1<<1, P2=1<<2, P3=1<<3. В числе F должны быть одновременно установлены P1 и P3. Запишите логическое выражение проверки и сформируйте маску M.
Решение.

Маска:

M = P1 OR P3 = (1<<1) OR (1<<3) = 2 + 8 = 10.

Проверка «все биты из M установлены»:

(F AND M) = M.

Если истинно – оба флага стоят. 

Упражнение 2. «Сброс подмаски и установка новой»
Условие. В 8-битном слове F низкие три бита – режим mode (значение 0..7). Требуется заменить mode на v и сбросить все остальные биты.
Решение.

Маска поля:

MASK = (1<<3) − 1 = 0b00000111 = 7.

Операция:

F ← ((v AND MASK))        // обнуляем всё и записываем поле

Если важно сохранить старшие биты → используем запись в поле без обнуления:

F ← (F AND (NOT MASK)) OR (v AND MASK)

Условие допустимости: 0 ≤ v < 8. 

Упражнение 3. «Ровно один флаг из набора»
Условие. Требуется проверить: из маски M в F установлен ровно один флаг.
Решение. Пусть X = F AND M. Свойство «ровно один бит» эквивалентно проверке «X – степень двойки и X ≠ 0». Формула:

(X ≠ 0) AND ((X AND (X − 1)) = 0).

Доказательство: у степеней двойки единственный установленный бит; у любого такого X выполняется X AND (X − 1) = 0. 

Упражнение 4. «Битовое поле: чтение и запись»
Условие. В 32-битном беззнаковом F хранится поле len шириной w=5 бит, начиная с позиции s=8.

1. Запишите len = v (0..31) в F.
2. Прочитайте len из F.

Решение.
Маска:

MASK = ((1<<5) − 1) << 8 = (31) << 8 = 0x1F00.

Запись:

F ← (F AND (NOT MASK)) OR ((v << 8) AND MASK)

Чтение:

len = (F AND MASK) >> 8

Проверка: 0 ≤ v < 32. 

Упражнение 5. «Инвертировать подмножество и проверить состав»
Условие. Пусть F кодирует набор прав доступа. Требуется: (i) инвертировать флаги из M, (ii) убедиться, что после инверсии ни один из флагов B не установлен.
Решение.

(i) Инверсия:

F ← F XOR M

(ii) Проверка отсутствия битов из B:

(F AND B) = 0

Если равно нулю – ни один флаг из B не включён. 

Практические шаблоны (псевдокод в «экзаменационном» стиле)

Определения констант:

CONST READ   = 1 << 0

CONST WRITE  = 1 << 1

CONST EXEC   = 1 << 2

CONST ADMIN  = 1 << 3

Установить права READ и EXEC:

F ← F OR (READ OR EXEC)

Снять право WRITE:

F ← F AND (NOT WRITE)

Проверить: есть ли хотя бы одно из (WRITE, ADMIN)?

((F AND (WRITE OR ADMIN)) ≠ 0)

Проверить: установлены ровно READ или EXEC (но не оба)?

X ← F AND (READ OR EXEC)

(X = READ) XOR (X = EXEC)     // либо через «степень двойки» 

Чек-лист самопроверки

• Каждому флагу назначена уникальная степень двойки: FLAG_i = 1 << i.
• Все константы одной ширины, используются беззнаковые типы.
• Для очистки применяю F AND (NOT MASK), для установки – F OR MASK, для инверсии – F XOR MASK.
• Проверки корректны: «все биты из M» → (F AND M) = M; «хотя бы один» → (F AND M) ≠ 0.
• Для битовых полей правильно вычислены MASK, s, w, контролируется диапазон v.
• Не смешиваю &&/|| и &/|.
• Учтены граничные случаи (нули, широкие маски, знаковость, сдвиги). 

Контрольные вопросы

1. Как формально описать соответствие между подмножеством признаков и целым числом?
2. Почему проверка «все биты из M установлены» записывается как (F AND M) = M?
3. Приведите доказательство критерия «число – степень двойки» через X AND (X−1).
4. Чем логические операторы отличаются от побитовых при работе с масками?
5. Как корректно задать и прочитать битовое поле шириной w на позиции s? 

Заключение

Битовые флаги – минималистичный и мощный инструмент представления множества булевых свойств. Его сила – в однозначной алгебре масок, постоянной асимптотике операций, экономии памяти и выразительности проверок. Строго следуя формальной модели (степени двойки, маски, корректные проверки), вы получаете надёжные и переносимые решения – от системных задач до экзаменационных. Для ЕГЭ навыки работы с флагами укрепляют понимание двоичного представления, булевой алгебры и формальной логики.