Битовые операции: таблица, восемь приёмов наизусть и код на Python
Elman Huseynov · 2026-11-17
Короткий ответ. Битовые операции работают с числом как с набором нулей и единиц. Шесть операций: и, или, исключающее или, не, сдвиг влево, сдвиг вправо. С ними задачи «найти единственное число», «посчитать единицы», «степень ли двойки» решаются за O(1) или O(log n) без лишней памяти. Ниже таблица, восемь приёмов, код на Python и типичные ошибки.
Что такое битовые операции?
Число 13 в двоичной записи это 1101. Каждая позиция это бит, ноль или единица. Битовые операции меняют или проверяют эти позиции напрямую.
Операция «и» оставляет единицу там, где единицы у обоих. «Или» ставит единицу, если она есть хоть у одного. «Исключающее или» ставит единицу, если биты разные.
Сдвиг влево на k это умножение на 2 в степени k. Сдвиг вправо это деление с округлением вниз.
findUnique([5, 3, 5, 6, 3])| 8 | 4 | 2 | 1 | |
|---|---|---|---|---|
| acc | 0 | 0 | 0 | 0 |
Каждое число встречается дважды, кроме одного. acc начинается с 0, а a XOR b переключает биты a там, где у b стоит 1.
Столбики: 32 бита числа, старший слева, высокий столбик означает 1. Проверка каждого бита их только читает; приём Кернигана сбрасывает каждую посчитанную единицу, поэтому его столбики в конце обнулены.
Одна операция: один шаг цикла: проверка одного бита или сброс одного бита. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n)O(k)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Страница паттерна: когда его применять и шаблон на шести языках
Какие битовые операции есть в Python?
| Операция | Запись | Пример | Смысл |
|---|---|---|---|
| И | a & b | 12 & 10 = 8 | 1100 & 1010 = 1000 |
| Или | a | b | 12 | 10 = 14 | 1100 | 1010 = 1110 |
| Исключающее или | a ^ b | 12 ^ 10 = 6 | 1100 ^ 1010 = 0110 |
| Не | ~a | ~12 = -13 | В Python это -a - 1 |
| Сдвиг влево | a << k | 3 << 2 = 12 | Умножить на 4 |
| Сдвиг вправо | a >> k | 12 >> 2 = 3 | Разделить на 4 |
Какие битовые приёмы стоит знать наизусть?
- x & 1 даёт последний бит: чётность.
- x & (x - 1) гасит самую младшую единицу.
- x & (x - 1) == 0 при x больше 0 значит степень двойки.
- x & -x выделяет самую младшую единицу.
- x ^ x = 0 и x ^ 0 = x: пары гасят друг друга.
- 1 << i это маска для бита i. Проверка: x & (1 << i).
- x | (1 << i) ставит бит i. x & ~(1 << i) снимает.
- Подмножества множества из n элементов это числа от 0 до 2ⁿ - 1.
Последний приём называют битовой маской. Он заменяет список булевых флагов одним числом.
По каким словам в задаче узнать битовые операции?
- «Каждое число встречается дважды, кроме одного».
- «Посчитать единицы в двоичной записи», «вес Хэмминга».
- «Без использования знака плюс», «без лишней памяти».
- «Все подмножества» при n меньше 20, «состояние из флагов».
Как это выглядит на примере?
Массив [4, 1, 2, 1, 2]. Ищем число, которое встречается один раз. Исключающее или всех элементов: 4 ^ 1 ^ 2 ^ 1 ^ 2. Пары 1 ^ 1 и 2 ^ 2 дают 0. Остаётся 4.
Считаем единицы в 13 = 1101. Шаг 1: 13 & 12 = 12 = 1100. Шаг 2: 12 & 11 = 8 = 1000. Шаг 3: 8 & 7 = 0. Три шага, три единицы.
Как написать битовые приёмы на Python?
def single_number(nums):
result = 0
for x in nums:
result ^= x # пары гасят друг друга
return result
def count_ones(x):
count = 0
while x:
x &= x - 1 # гасим младшую единицу
count += 1
return count # или bin(x).count("1")
def is_power_of_two(x):
return x > 0 and x & (x - 1) == 0
def subsets(nums):
n = len(nums)
out = []
for mask in range(1 << n): # каждая маска это одно подмножество
out.append([nums[i] for i in range(n) if mask >> i & 1])
return out
def add(a, b): # сложение без плюса, 32 бита
mask = 0xFFFFFFFF
while b:
a, b = (a ^ b) & mask, ((a & b) << 1) & mask
return a if a < 0x80000000 else ~(a ^ mask)
Функция add показывает, зачем маска. У Python целые числа без ограничения длины. Отрицательные числа надо обрезать вручную.
Как решить Single Number II?
Каждое число встречается трижды, кроме одного. Исключающее или уже не помогает. Для каждого из 32 битов считаем, сколько чисел его содержат. Остаток от деления на 3 даёт бит ответа. Время O(32 · n), памяти O(1).
Как перебрать подмножества через битовую маску?
Множество из n элементов. Число от 0 до 2ⁿ - 1 кодирует подмножество. Бит i выставлен, элемент i взят. Цикл по всем числам перебирает все подмножества. Это короче бэктрекинга и удобно для динамического программирования по маскам.
На каких ошибках ломаются битовые операции?
- Путают приоритет: x & 1 == 0 читается как x & (1 == 0). Нужны скобки.
- Забывают, что ~x в Python это -x - 1. Инверсии 32 битов нет.
- Сдвигают отрицательное число вправо и ждут поведения C.
- Считают единицы через строку внутри цикла на миллион чисел.
Как объяснить приём на собеседовании?
Назовите операцию и её свойство одной фразой. «Исключающее или гасит пары, поэтому остаётся одиночка». Этого хватает.
Потом покажите двоичную запись на маленьком числе. Собеседующий видит, что вы не просто помните трюк.
Отработать узнавание приёма можно на странице битовые манипуляции. Общая карта приёмов лежит в статье паттерны алгоритмов.
Вопросы и ответы
Как обменять две переменные без третьей?
a ^= b, b ^= a, a ^= b. Работает, но в Python проще a, b = b, a. На собеседовании это спрашивают ради понимания исключающего или.
Что такое код Грея?
Последовательность, где соседние числа отличаются одним битом. Формула: i ^ (i >> 1). Встречается в задаче Gray Code.
Как найти два одиночных числа среди пар?
Исключающее или всех даёт a ^ b. Выделите любой выставленный бит через x & -x. Разделите числа по этому биту на две группы и сверните каждую.
Где битовые операции встречаются в реальных системах?
В правах доступа файлов, где каждый бит это разрешение. В сетевых масках. В флагах компиляторов и в графике, где цвет упакован в одно число.