Раздел 12 — Битовые операции и множества

Целое число хранится в двоичной записи: биты нумеруются справа налево с нуля, бит k «весит» 2^k. 180 = 128 + 32 + 16 + 4 = 10110100. Длинные двоичные числа неудобно читать, поэтому пишут шестнадцатеричные: одна шестнадцатеричная цифра — ровно 4 бита.

  биты     1011 0100           двоичная
  hex        B    4            0xB4
  десятич.  180                11 · 16 + 4

В C: литерал 0xB4, вывод printf("%X", x) (или %x — строчными, %02X — две цифры с нулём). Двоичных литералов и формата в C11 нет — двоичную запись печатают своей функцией:

/* Вывести младшие bits битов x, старший первым */
void print_bits(unsigned x, int bits)
{
    for (int k = bits - 1; k >= 0; k--) {
        putchar((x >> k) & 1u ? '1' : '0');
    }
    putchar('\n');
}
                                          /* print_bits(180, 8)  ->  10110100 */

Цвет #FF8000 в CSS, MAC-адрес 00:1A:2B:…, коды символов в UTF-8 — всё это шестнадцатеричная запись байтов.

Битовые операции работают с каждым битом отдельно, в отличие от логических && || !, которые смотрят на число целиком (ноль / не ноль).

Маска — число, в котором единицы стоят в нужных битах. С маской 1u << k (единица в бите k) делают четыре действия:

Флаги — несколько да/нет-признаков в одном числе. Права файла в Linux — 9 флагов: чтение (r), запись (w), выполнение (x) для владельца, группы и остальных. Каждая тройка — восьмеричная цифра, отсюда chmod 755:

enum {
    READ  = 4,          /* 100 */
    WRITE = 2,          /* 010 */
    EXEC  = 1           /* 001 */
};

unsigned owner = READ | WRITE | EXEC;   /* 7 = rwx */
unsigned group = READ | EXEC;           /* 5 = r-x */
bool can_write = (group & WRITE) != 0;  /* false */
unsigned mode = owner << 6 | group << 3 | group;   /* 0755 = 493 */

Флаги — обычный способ передать несколько настроек в функцию одним параметром: open(path, O_WRONLY | O_CREAT | O_TRUNC) в Linux, стили окна в Windows API и Qt.

Множество чисел от 0 до 31 хранится в одном uint32_t: бит k равен 1, если k входит в множество. Операции над множествами становятся одной битовой операцией — O(1) вместо цикла по элементам:

Число элементов — число единичных битов. Приём: x &= x - 1 сбрасывает младшую единицу (вычитание единицы превращает младшую единицу в 0, а нули справа от неё — в единицы, и & их убирает). Цикл выполняется столько раз, сколько единиц:

int count_bits(uint32_t x)
{
    int count = 0;
    while (x != 0) {
        x &= x - 1;               /* 10110100 -> 10110000 -> 10100000 -> 10000000 -> 0 */
        count++;
    }
    return count;
}

Тот же приём: x != 0 && (x & (x - 1)) == 0 — «x — степень двойки» (ровно одна единица). Для множеств больше 32 или 64 элементов берут массив чисел: элемент k — бит k % 32 в слове k / 32. Буквы латинского алфавита — 26 бит: множество букв слова — одно число, общие буквы двух слов — одно &.

У множества из n элементов 2ⁿ подмножеств, и каждое — число от 0 до 2ⁿ − 1: бит i говорит, взят ли элемент i. Перебрать все подмножества — перебрать все числа:

/* Есть ли среди n чисел подмножество с суммой target? Перебор 2^n масок */
for (uint32_t mask = 1; mask < (1u << n); mask++) {
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        if ((mask >> i) & 1u) {
            sum += a[i];
        }
    }
    if (sum == target) {
        … подмножество найдено: элементы a[i] с единицей в бите i …
    }
}

Это полный перебор: O(2ⁿ · n). Для n = 20 — около 20 миллионов операций (доли секунды), для n = 40 — 4 · 10¹³ (дни). Полный перебор — честный способ решить задачу, у которой нет быстрого алгоритма, но только для небольших n; оценка 2ⁿ показывает, где его граница.

Найти все простые числа до n: выписать числа 2…n, взять первое невычеркнутое (оно простое) и вычеркнуть все его кратные; повторить. Вычёркивать кратные p можно начиная с p² — меньшие кратные уже вычеркнуты меньшими делителями; поэтому внешний цикл идёт до √n:

/* composite[k] == true — k составное; заполняется для 0..n */
void sieve(bool composite[], int n)
{
    for (int k = 0; k <= n; k++) {
        composite[k] = k < 2;
    }
    for (int p = 2; p <= n / p; p++) {
        if (!composite[p]) {
            for (int m = p * p; m <= n; m += p) {
                composite[m] = true;
            }
        }
    }
}

Решето делает около n · ln ln n вычёркиваний — почти O(n): для n = 10⁶ это несколько миллионов операций против ~10⁸ при проверке каждого числа делителями до √n (раздел 6). Простых до 100 — 25, до миллиона — 78 498. Массив bool на миллион — мегабайт; если хранить по биту на число, — 125 килобайт: это решето на битовой маске из практической работы.