10.4 Побитовые оптимизации¶

Во многих алгоритмах побитовые операции позволяют заметно ускорить программу. Обычно такие улучшения не меняют асимптотическую сложность, но на практике могут сократить время работы в несколько раз. Ниже разберём два характерных примера.

Расстояния Хэмминга¶

Расстояние Хэмминга между двумя строками одинаковой длины — это количество позиций, в которых символы различаются.

Например:

• hamming(01011, 11001) = 2

Рассмотрим задачу: дан список из n двоичных строк длины k. Нужно найти минимальное расстояние Хэмминга между двумя строками списка.

Для примера возьмём строки:

• 00011
• 01010
• 11011

Тогда:

• hamming(00011, 01010) = 2
• hamming(00011, 11011) = 1
• hamming(01010, 11011) = 3

Значит, ответ равен 1.

Прямой подход¶

Можно перебрать все пары строк и для каждой посчитать число отличающихся позиций. Тогда получаем алгоритм со сложностью O(n^2 k).

int hamming(string a, string b) {
    int d = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        if (a[i] != b[i]) d++;
    }
    return d;
}

Ускорение через биты¶

Если длина строки невелика, её можно хранить не как string, а как целое число.

Например, строку 101101 можно интерпретировать как число в двоичной записи. Тогда различия между двумя строками удобно находить через операцию xor:

• в результате a ^ b единицы стоят ровно в тех позициях, где строки различаются;
• остаётся только посчитать число единичных битов.

int hamming(int a, int b) {
    return __builtin_popcount(a ^ b);
}

Почему это работает¶

Пусть:

• a = 101011
• b = 111001

Тогда:

a ^ b = 010010

В результате две единицы, значит расстояние Хэмминга равно 2.

Практический смысл¶

Наивный способ тратит время на посимвольное сравнение. Побитовый вариант обрабатывает сразу весь блок битов одной операцией процессора. Поэтому при небольшом k ускорение может быть очень заметным.

Особенно полезен этот приём, когда:

• строки действительно бинарные;
• длина ограничена, например k <= 32 или k <= 64;
• нужно сравнить очень много пар.

Подсчёт подрешёток¶

Рассмотрим другую задачу.

Дана квадратная таблица n × n, в каждой клетке которой стоит либо 1 (чёрная клетка), либо 0 (белая клетка). Нужно посчитать число подпрямоугольников, у которых все четыре угла чёрные.

Например, для такой таблицы:

1 0 1 1
1 1 0 1
0 1 1 0
1 1 1 1

мы ищем все прямоугольники, у которых четыре угловые клетки равны 1.

Идея обычного решения¶

Переберём все пары строк (a, b). Для каждой пары посмотрим, в каких столбцах в обеих строках стоит 1.

Если таких столбцов cnt, то из них можно выбрать любые два — они образуют левую и правую границу прямоугольника. Поэтому число подходящих прямоугольников для пары строк равно:

Подсчёт cnt для одной пары строк занимает O(n), а пар строк всего O(n^2). Итого получаем алгоритм O(n^3).

int cnt = 0;
for (int i = 0; i < n; i++) {
    if (color[a][i] == 1 && color[b][i] == 1) cnt++;
}

Побитовое ускорение¶

Разобьём каждую строку на блоки по N столбцов и будем хранить каждый блок как одно целое число.

Тогда вместо проверки столбцов по одному мы можем за один раз обработать целый блок:

• color[a][i] & color[b][i] оставит единицы только там, где в обеих строках стоят 1;
• __builtin_popcount(...) посчитает, сколько таких совпадений в блоке.

int cnt = 0;
for (int i = 0; i <= n / N; i++) {
    cnt += __builtin_popcount(color[a][i] & color[b][i]);
}

Что изменилось¶

Раньше мы обрабатывали столбцы по одному. Теперь — сразу по N штук.

Если:

• N = 32, используем int;
• N = 64, используем long long или uint64_t.

Тогда сложность становится:

То есть асимптотика формально улучшается за счёт пакетной обработки столбцов.

Наглядная схема¶

flowchart TD
    A["Выбрали пару строк a и b"] --> B["Разбили строки на битовые блоки"]
    B --> C["Для каждого блока вычислили AND"]
    C --> D["Посчитали число единиц через popcount"]
    D --> E["Получили cnt общих чёрных столбцов"]
    E --> F["Добавили cnt * (cnt - 1) / 2 к ответу"]

Когда это особенно полезно¶

Такой подход эффективен, если:

• таблица большая;
• значения бинарные (0/1);
• нужно много раз искать пересечения между строками.

На практике побитовая версия часто оказывается в разы быстрее обычной.

Что важно запомнить¶

Побитовые оптимизации особенно полезны в задачах, где данные естественно кодируются нулями и единицами.

Частые идеи:

• заменить массив булевых значений на битовую маску;
• сравнивать сразу целые блоки битов, а не элементы по одному;
• использовать xor, and, or, popcount для ускорения вычислений.

Такие приёмы не всегда меняют общую теоретическую оценку, но очень часто дают решающий выигрыш по времени в реальных задачах.

Небольшой итог¶

Раздел показывает две типичные ситуации:

1. Сравнение бинарных объектов удобно ускорять через xor и подсчёт единичных битов.
2. Обработку бинарных таблиц удобно ускорять, если хранить строки блоками и работать с ними как с битовыми масками.

Это один из самых практичных способов «выжать» из алгоритма больше скорости без изменения основной идеи.