---
title: "Битовые операции: таблица, восемь приёмов наизусть и код на Python"
url: https://algopath.pro/ru/blog/bitovye-operatsii
language: ru
summary: "И, или, исключающее или, сдвиги и что с ними делать в задачах. Таблица операций, приёмы вроде x & (x - 1), Single Number, подсчёт единиц, подмножества через маску, ошибки."
updated: 2026-11-17
---

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

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

 

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

 

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

 

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

 

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

 

## Какие битовые операции есть в 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.
- Считают единицы через строку внутри цикла на миллион чисел.

 

## Как объяснить приём на собеседовании?

 

Назовите операцию и её свойство одной фразой. «Исключающее или гасит пары, поэтому остаётся одиночка». Этого хватает.

 

Потом покажите двоичную запись на маленьком числе. Собеседующий видит, что вы не просто помните трюк.

 

Отработать узнавание приёма можно на странице [битовые манипуляции](/ru/patterns/bit-manipulation). Общая карта приёмов лежит в статье [паттерны алгоритмов](/ru/blog/patterny-algoritmov).

 

## Вопросы и ответы

 

### Как обменять две переменные без третьей?

 

a ^= b, b ^= a, a ^= b. Работает, но в Python проще a, b = b, a. На собеседовании это спрашивают ради понимания исключающего или.

 

### Что такое код Грея?

 

Последовательность, где соседние числа отличаются одним битом. Формула: i ^ (i >> 1). Встречается в задаче Gray Code.

 

### Как найти два одиночных числа среди пар?

 

Исключающее или всех даёт a ^ b. Выделите любой выставленный бит через x & -x. Разделите числа по этому биту на две группы и сверните каждую.

 

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

 

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