Сначала разберём запись числа
13 в двоичной системе записывается как 1101: единицы стоят на местах с весом 8, 4 и 1. Позиции нумеруются справа налево, начиная с нуля.
| Позиция |
3 |
2 |
1 |
0 |
| Вес |
8 |
4 |
2 |
1 |
| Бит числа 13 |
1 |
1 |
0 |
1 |
1101₂ = 8 + 4 + 0 + 1 = 13₁₀. Маска 1 << k оставляет единицу только в позиции k.
Что делают операторы
Возьмём четырёхбитные записи A = 1010₂ (10) и B = 1100₂ (12). Операция выполняется над каждой парой битов на одной позиции.
| Операция |
Запись |
Правило для каждого бита |
Результат |
| И |
A & B |
1, если обе цифры равны 1 |
1000₂ = 8 |
| ИЛИ |
A | B |
1, если хотя бы одна цифра равна 1 |
1110₂ = 14 |
| XOR |
A ^ B |
1, если цифры различаются |
0110₂ = 6 |
~ меняет нули и единицы местами. Если рассматривать только четыре младших бита, то ~1010₂ → 0101₂. Для такого результата в обоих языках запишем (~A) & 15: число 15 = 1111₂ ограничивает результат четырьмя битами.
A << 1 сдвигает биты влево и даёт 10100₂ = 20. A >> 1 сдвигает их вправо и даёт 0101₂ = 5. Для неотрицательных чисел это соответствует умножению или целочисленному делению на два, если результат помещается в выбранный тип.
C++
#include <iostream>
using namespace std;
int main() {
unsigned int a = 10, b = 12;
cout << (a & b) << ' ' << (a | b)
<< ' ' << (a ^ b) << '\n';
cout << (a << 1) << ' '
<< (a >> 1) << '\n';
cout << ((~a) & 15u) << '\n';
}
Python
a, b = 10, 12
print(a & b, a | b, a ^ b)
print(a << 1, a >> 1)
print((~a) & 15)
Вывод обеих программ: 8 14 6, затем 20 5, затем 5. У Python целые числа не ограничены четырьмя битами, а C++ использует фиксированную ширину типа. Поэтому при демонстрации ~ мы явно ограничиваем результат маской.
Маска: проверяем и меняем один бит
Пусть x = 1010₂ (10). Хотим работать с битом позиции 2 — это третий бит справа. Его маска равна 1 << 2 = 0100₂.
| Что сделать |
Выражение |
Результат |
| Проверить |
x & mask |
0: бит сейчас выключен |
| Установить в 1 |
x | mask |
1110₂ = 14 |
| Сбросить в 0 |
x & ~mask |
1010₂ = 10 |
| Поменять на противоположный |
x ^ mask |
1110₂ = 14 |
C++
#include <iostream>
using namespace std;
int main() {
unsigned int x = 10;
unsigned int mask = 1u << 2;
cout << ((x & mask) != 0u) << '\n';
cout << (x | mask) << '\n';
cout << (x & ~mask) << '\n';
cout << (x ^ mask) << '\n';
}
Python
x = 10
mask = 1 << 2
print(int((x & mask) != 0))
print(x | mask)
print(x & ~mask)
print(x ^ mask)
Оба примера выводят 0, 14, 10 и 14. В каждом выражении используется исходное значение x; результаты операций не записываются обратно в x.
Проверь себя: какой маской проверить самый правый бит?
1 << 0, то есть 0001₂. Выражение x & 1 равно 1 для нечётного x и 0 для чётного.
Тренажёр: собери два числа из битов
Нажимай на биты чисел A и B, выбери операцию и сначала запиши четыре бита ответа. Затем проверь себя. Биты расположены от позиции 3 слева до позиции 0 справа.
Результат: ????
Если тренажёр не запустился: ответ для начальных чисел
Для A = 0101₂ и B = 0011₂: И → 0001₂, ИЛИ → 0111₂, XOR → 0110₂.
Число как небольшое множество
Договоримся: единица в позиции k означает, что элемент k входит в множество. Тогда 0101₂ описывает множество {0, 2}, а 0110₂ — {1, 2}.
0101₂∪0110₂=0111₂
Объединение получают операцией ИЛИ: 0101 | 0110 = 0111, то есть {0, 1, 2}. Пересечение получают операцией И: 0101 & 0110 = 0100, то есть {2}.
Мини-задание: какой битовой маской записать множество {1, 3}?
1010₂: единицы стоят в позициях 3 и 1.
Код Грея (Gray Code)
Условие по-русски. По данному числу n составь последовательность из 2ⁿ различных двоичных строк длины n. Любые две соседние строки должны отличаться ровно в одной позиции. Можно вывести любую последовательность, которая выполняет эти условия.
Ввод: одно число n, где 1 ≤ n ≤ 16. Вывод: 2ⁿ строк, каждая на отдельной строке. Лимиты: 1 с, 512 МБ.
Один допустимый вывод
00
01
11
10
Подсказка для проверки: если выполнить XOR двух соседних строк, в результате должна остаться ровно одна единица.
Открыть Gray Code и отправить решение ↗
Проверь свою последовательность
Составь собственный код Грея для n = 2 или n = 3. Запиши каждую строку с новой строки; проверка покажет, выполнены ли все правила задачи.
Пример последовательности для n = 2
00 → 01 → 11 → 10. Каждая из четырёх строк встречается один раз; между соседними строками меняется один бит.
Где применяются биты: задачи Codeforces
В одних задачах поразрядная операция даёт ключевую идею, в других маска помогает удобно записать очередной вариант перебора. Таблица идёт от простых примеров к задачам, требующим дополнительных алгоритмов.
| Задача |
Что требуется |
Где работают биты |
| 579A — Raising Bacteria ↗Разведение бактерий
1000
Разбор задачи
|
Получить ровно x бактерий, добавив за всё время как можно меньше новых. |
Минимальное число добавлений равно количеству единиц в двоичной записи x. Например, у 5 = 101₂ две единицы. |
| 467B — Fedor and New Game ↗Фёдор и новая игра1100 |
Посчитать игроков, чьи армии отличаются от армии Фёдора не более чем по k видам солдат. |
Операция x ^ f отмечает единицами различающиеся биты армий. Нужно сосчитать их и сравнить результат с k. |
| 1097B — Petr and a Combination Lock ↗Пётр и кодовый замок1200 |
Для каждого поворота выбрать направление и проверить, можно ли вернуться к нулю на шкале в 360°. |
Бит i маски может означать направление i-го поворота. При n ≤ 15 перебирают все 2ⁿ вариантов. |
| 550B — Preparing Olympiad ↗Подготовка олимпиады1400 |
Посчитать наборы минимум из двух задач, подходящие по суммарной сложности и разнице между самой лёгкой и самой трудной. |
Единица в позиции i означает, что задача i выбрана. Маска задаёт один набор; при n ≤ 15 можно проверить все наборы. |
| 276D — Little Girl and Maximum XOR ↗Девочка и максимальный XOR1700 |
Найти наибольшее a ^ b для двух чисел из отрезка [l, r]. |
Нужно рассмотреть старший разряд, в котором числа могут различаться. Перебор всех пар не подходит: r достигает 10¹⁸. |
| 339D — Xenia and Bit Operations ↗Ксения и битовые операции1700 |
После изменений элементов массива заново находить результат последовательных операций ИЛИ и XOR. |
Операции чередуются на уровнях дерева отрезков. Эту задачу лучше решать после знакомства с деревом отрезков. |
Начни с первых четырёх задач. В 1097B и 550B варианты можно перебирать и рекурсией: битовая маска здесь удобна для записи выбора. Числа в зелёных метках — рейтинг сложности Codeforces.
|