---
title: "Битовые манипуляции"
url: https://algopath.pro/ru/patterns/bit-manipulation
language: ru
summary: "Считайте целое число длинным рядом переключателей. Маски, сдвиги и XOR читают или переключают каждый из них прямо на месте."
updated: 2026-08-24
---

# Битовые манипуляции

Считайте целое число длинным рядом переключателей. Маски, сдвиги и XOR читают или переключают каждый из них прямо на месте.

## Битовые манипуляции: как это работает?

Число это ряд битов, каждый вдвое дороже соседа справа. Бит i стоит 2 в степени i.

Сдвиг влево на один удваивает число. Сдвиг вправо делит пополам и теряет последний бит.

AND с маской оставляет только те биты, что есть в маске. Так читают один бит.

OR ставит бит, а XOR его переключает. Бит, сложенный по XOR сам с собой, даёт ноль.

Этот факт и есть весь приём поиска одинокого значения. Каждая пара взаимно уничтожается.

n AND n минус один снимает младший установленный бит. Повторение этого считает установленные биты.

- `n = 1100` Двенадцать в двоичной записи. У него два установленных бита.
- `n & 1 = 0` Последний бит нулевой, значит число чётное.
- `n >> 2 = 11` Два сдвига вправо оставляют тройку.
- `n & (n - 1) = 1000` Вычитание единицы даёт 1011, и AND снимает младший установленный бит.
- `два круга дают ноль` Значит у двенадцати ровно два установленных бита.

## Битовые манипуляции: когда применять?

- найти единственное или уникальное число через XOR
- установить, снять, переключить или проверить бит
- упаковать много флагов да/нет в одно целое число
- подсчёт установленных битов или проверка степени двойки

## Битовые манипуляции: с чем путают?

- **Хеш-множество / словарь** - Множество отвечает про принадлежность для любого ключа. Битовая маска умеет это для 32 известных элементов без памяти.
- **Математика и теория чисел (НОД, решето, модульная арифметика)** - Оба работают с самим числом. Та страница про делители и простые, эта про биты.
- **Бэктрекинг** - Подмножества можно перечислить простым счётом от нуля. Бэктрекинг строит тот же список рекурсией.
- **Сортировка без сравнений (подсчётом / поразрядная)** - Поразрядная сортировка читает разряды, иногда как биты. Её цель группировка, а не переключение.

## Битовые манипуляции: сложность по времени и памяти

Одна операция стоит O(1) на 32-битном значении. Проход по битам это O(32), то есть константа.

## Битовые манипуляции: разбор примера

### Посчитать биты у всех чисел подряд

Для каждого числа от 0 до n посчитайте, сколько у него установленных битов.

Считать каждое отдельно можно, но это повторяет кучу работы.

Снятие младшего установленного бита даёт меньшее число, уже посчитанное.

Значит ответ для i это ответ для i AND i минус один плюс единица.

```javascript
function countBits(n) {
    const bits = new Array(n + 1).fill(0);

    for (let i = 1; i <= n; i++) {
        // i & (i - 1) clears the lowest set bit, so it is always smaller
        bits[i] = bits[i & (i - 1)] + 1;
    }

    return bits;
}
```

## Битовые манипуляции: частые ошибки

- **Сдвигают дальше 31 бита** Битовые операции JavaScript работают на 32 битах и заворачиваются. Дальше нужен BigInt.
- **Забывают про знаковый бит** Результат сдвига может вернуться отрицательным. Для простого подсчёта берите беззнаковый сдвиг.
- **Путают AND и OR** AND читает или снимает, а OR ставит. Их перестановка даёт молча неверную маску.
- **Берут биты там, где важна ясность** Массив булевых значений читается лучше и работает так же быстро. Маска нужна, когда ограничение это память.

## Битовые манипуляции: задачи с собеседований

- **Одинокое число** Каждая пара сама себя уничтожает под XOR.
- **Число единичных битов** Снимайте младший установленный бит, пока не станет ноль.
- **Подсчёт битов** Каждый ответ переиспользует уже посчитанный меньший.
- **Пропущенное число** Сложите по XOR индексы со значениями.
- **Подмножества** Считайте от нуля до двойки в степени n.
- **Степень двойки** Верно ровно тогда, когда n AND n минус один равно нулю.
- **Сумма двух целых** XOR даёт сумму, а сдвинутый AND даёт перенос.

## JavaScript

```javascript
function findUnique(nums) {
    return nums.reduce((acc, n) => acc ^ n, 0);
}
function setBit(mask, i) { return mask | (1 << i); }
function clearBit(mask, i) { return mask & ~(1 << i); }
function hasBit(mask, i) { return (mask & (1 << i)) !== 0; }
```

## Python

```python
def find_unique(nums):
    acc = 0
    for n in nums:
        acc ^= n
    return acc

def set_bit(mask, i): return mask | (1 << i)
def clear_bit(mask, i): return mask & ~(1 << i)
def has_bit(mask, i): return (mask & (1 << i)) != 0
```

## PHP

```php
function findUnique(array $nums): int {
    $acc = 0;
    foreach ($nums as $n) $acc ^= $n;
    return $acc;
}
function setBit(int $mask, int $i): int { return $mask | (1 << $i); }
function clearBit(int $mask, int $i): int { return $mask & ~(1 << $i); }
function hasBit(int $mask, int $i): bool { return ($mask & (1 << $i)) !== 0; }
```