AND, OR, XOR и сдвиги
Уверенно читайте и комбинируйте биты
«AND, OR, XOR и сдвиги» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Биты — Ваш рабочий инструмент
На самом деле каждое целое число представляет собой последовательность битов, состоящую только из нулей и единиц. Умение читать и комбинировать их даёт быстрые и изящные приёмы для соревнований. 🔧
Посмотрите двоичное представление
Используйте bin() в Python, чтобы посмотреть на биты любого числа. Префикс 0b просто обозначает двоичную запись, а остальная часть представляет собой последовательность битов.
print(bin(13)) # 0b1101AND сохраняет общие биты
Оператор AND (&) даёт 1 только в тех позициях, где у обоих чисел стоит 1. Он отлично подходит для проверки или маскирования общих битов.
print(6 & 3) # 0b110 & 0b011 = 0b010 = 2OR объединяет биты
Оператор OR (|) даёт 1 в каждой позиции, где хотя бы у одного числа стоит 1. Используйте его, чтобы включить флаги, не изменив остальные биты.
print(6 | 1) # 0b110 | 0b001 = 0b111 = 7XOR находит различия
Оператор XOR (^) даёт 1 там, где два бита различаются. В задачах на соревнованиях его часто используют для переключения битов и поиска единственного отличающегося элемента.
print(6 ^ 3) # 0b110 ^ 0b011 = 0b101 = 5XOR сокращает сам себя
Число, подвергнутое операции XOR с самим собой, всегда даёт 0, а XOR с 0 оставляет число без изменений. Это свойство самосокращения лежит в основе многих задач на XOR.
print(7 ^ 7) # 0
print(7 ^ 0) # 7Найдите уникальное число
Если каждое значение встречается дважды, кроме одного, примените XOR ко всем значениям, и пары сократятся. Оставшееся значение будет уникальным.
ans = 0
for x in [4, 1, 2, 1, 2]:
ans ^= x
print(ans) # 4Сдвиг влево умножает
Сдвиг влево перемещает биты вверх, добавляя справа нули. Каждый сдвиг на один разряд удваивает значение, как умножение на степень двойки.
print(3 << 2) # 3 * 4 = 12Сдвиг вправо делит
Сдвиг вправо удаляет биты с правого края. Каждый сдвиг на один разряд делит значение пополам, выполняя целочисленное деление на степень двойки.
print(20 >> 2) # 20 // 4 = 5Создайте степень двойки
Сдвиг 1 влево на k позиций мгновенно создаёт значение 2 в степени k. Это самый простой способ создать маску с одним установленным битом.
print(1 << 5) # 32Скорость важна на соревнованиях
Побитовые операторы выполняются за один быстрый шаг, поэтому замена арифметики на сдвиги может помочь уложиться в жёсткое ограничение по времени. Выучите их назубок. ⚡
Быстрая проверка
Пора проверить Ваши побитовые операторы.
Итоги: побитовые операторы
Вы познакомились с AND, OR, XOR и сдвигами: объединяйте, переключайте и масштабируйте биты за один быстрый шаг. Это строительные блоки всех последующих побитовых приёмов. 🎉
Часто задаваемые вопросы
Урок «AND, OR, XOR и сдвиги» бесплатный?
Да — полный текст урока «AND, OR, XOR и сдвиги» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «AND, OR, XOR и сдвиги»?
Уверенно читайте и комбинируйте биты Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «AND, OR, XOR и сдвиги»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- AND, OR, XOR и сдвиги
- Установить, сбросить и переключить бит
- Подсчёт битов и младший установленный бит
- Битовые маски как маленькие множества