Мы используем необходимые куки для работы сайта (вход и язык). Если ты согласишься, мы также загрузим Google Analytics, чтобы видеть, какие страницы читают, и Google reCAPTCHA для защиты форм обратной связи и сообщений об ошибке от спама. Политика конфиденциальности

← Блог
Как готовиться

Битовые операции: таблица, восемь приёмов наизусть и код на Python

· 2026-11-17

Короткий ответ. Битовые операции работают с числом как с набором нулей и единиц. Шесть операций: и, или, исключающее или, не, сдвиг влево, сдвиг вправо. С ними задачи «найти единственное число», «посчитать единицы», «степень ли двойки» решаются за O(1) или O(log n) без лишней памяти. Ниже таблица, восемь приёмов, код на Python и типичные ошибки.

Что такое битовые операции?

Число 13 в двоичной записи это 1101. Каждая позиция это бит, ноль или единица. Битовые операции меняют или проверяют эти позиции напрямую.

Операция «и» оставляет единицу там, где единицы у обоих. «Или» ставит единицу, если она есть хоть у одного. «Исключающее или» ставит единицу, если биты разные.

Сдвиг влево на k это умножение на 2 в степени k. Сдвиг вправо это деление с округлением вниз.

Поиск числа без пары через XOR
findUnique([5, 3, 5, 6, 3])
nums
5
3
5
6
3
биты (столбец = сколько стоит бит)
8421
acc0000
acc = 0

Каждое число встречается дважды, кроме одного. acc начинается с 0, а a XOR b переключает биты a там, где у b стоит 1.

Гонка скорости
Подсчёт единичных битов одного и того же 32-битного числа: проверка всех 32 или сброс одной единицы за шаг

Столбики: 32 бита числа, старший слева, высокий столбик означает 1. Проверка каждого бита их только читает; приём Кернигана сбрасывает каждую посчитанную единицу, поэтому его столбики в конце обнулены.

Одна операция: один шаг цикла: проверка одного бита или сброс одного бита. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.

Проверка каждого бита O(n)
операций: 0
Приём Кернигана O(k)
операций: 0

 

А если чисел больше

Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.

n = 1 000
Проверка каждого бита1 тыс. · меньше 1 мс
Приём Кернигана250 · меньше 1 мс
n = 100 000
Проверка каждого бита100 тыс. · 1 мс
Приём Кернигана25 тыс. · меньше 1 мс
n = 10 000 000
Проверка каждого бита10 млн · 100 мс
Приём Кернигана2,5 млн · 25 мс

Страница паттерна: когда его применять и шаблон на шести языках

Какие битовые операции есть в Python?

ОперацияЗаписьПримерСмысл
Иa & b12 & 10 = 81100 & 1010 = 1000
Илиa | b12 | 10 = 141100 | 1010 = 1110
Исключающее илиa ^ b12 ^ 10 = 61100 ^ 1010 = 0110
Не~a~12 = -13В Python это -a - 1
Сдвиг влевоa << k3 << 2 = 12Умножить на 4
Сдвиг вправоa >> k12 >> 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. Разделите числа по этому биту на две группы и сверните каждую.

Где битовые операции встречаются в реальных системах?

В правах доступа файлов, где каждый бит это разрешение. В сетевых масках. В флагах компиляторов и в графике, где цвет упакован в одно число.