Конспект: маски, сдвиги и множество на битах

Понятия

Бит - один двоичный разряд. Бит номер k весит 2ᵏ, счёт справа с нуля.

Маска - число-трафарет: единицы в нём отмечают, какие разряды другого числа нужны.

Слово - n битов фиксированной ширины; всё, что не поместилось, отбрасывается. Арифметика в слове идёт по модулю 2ⁿ.

Дополнительный код - чтение слова со знаком: старший бит единица → значение u − 2ⁿ. Запись -x - это 2ⁿ − x, она же ~x + 1.

Подмаска маски m - число s с s & m == s: запись подмножества.

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

Что унести

ШЕСТЬ ОПЕРАЦИЙ                 12 = 1100, 10 = 1010
a & b    единица у обоих       1000 = 8
a | b    хотя бы у одного      1110 = 14
a ^ b    биты разные           0110 = 6
~a       переворот             −13          ~x = −x − 1
a << k   умножить на 2ᵏ        12 << 2 = 48
a >> k   разделить на 2ᵏ вниз  12 >> 2 = 3,  −7 >> 1 = −4

ПОРЯДОК ДЕЙСТВИЙ, от слабого к сильному
сравнения < | < ^ < & < сдвиги < + − < * / // % < ~ и унарный минус < **
1 << n + 1  это  1 << (n + 1)          x & 1 == 0  в Python это  (x & 1) == 0,  в C -  x & (1 == 0)

ТРИ ДВИЖЕНИЯ
достать бит k           x >> k & 1
вырезать поле           x >> сдвиг & маска           0x2E8B57 >> 8 & 0xFF = 0x8B
склеить из полей        a << 16 | b << 8 | c
маска из k единиц       (1 << k) - 1
сеть и узел             адрес & маска,  адрес & ~маска & 0xFFFFFFFF

СЛОВО ИЗ 8 БИТОВ          без знака     со знаком
0111 1111                    127           127
1000 0000                    128          −128
1111 1011                    251            −5
1111 1111                    255            −1

в Python:  слово = x & 0xFF         со знаком = (u ^ 0x80) - 0x80
100 + 100 → −56      127 + 1 → −128      −(−128) → −128
расширение знака: слева копии старшего бита
сдвиг вправо: арифметический копирует знак (−8 → −4), логический вдвигает ноль (248 → 124)

МНОЖЕСТВО НОМЕРОВ 0 … n−1 КАК ЧИСЛО
пересечение  a & b        объединение  a | b       разность  a & ~b       ровно в одном  a ^ b
входит ли k  a >> k & 1   добавить  a | 1 << k     убрать  a & ~(1 << k)  переключить  a ^ 1 << k
a внутри b   a & b == a   размер  a.bit_count()    всё множество  (1 << n) - 1
дополнение   ~a & vse

два набора по 25 чисел: поиск по спискам 591 шаг, готовые маски - 1 шаг

ПОДМАСКИ                                 m = 1101:  1101 1100 1001 1000 0101 0100 0001 0000
s = m
пока s > 0:                              s − 1: младшая единица гаснет, нули под ней зажигаются
    ...                                  & m: стирает то, что зажглось не на своём месте
    s = (s − 1) & m                      s & (s − 1): s без младшей единицы
отдельно: s = 0

подмасок у m: 2 в степени «число единиц»       пар (m, s) на n битах: 3ⁿ, не 4ⁿ
n = 8: 6561 пара, 19 941 шаг против 137 891       потолок: 15-18 элементов

Выигрыш - ширина слова, 64 раза. Порядок роста тот же: строка длиннее слова - массив слов.

Зета и Мёбиус: суммы по подмаскам и их обращение - O(n·2ⁿ). Свёртка по непересекающимся частям через слои мощности - O(n²·2ⁿ) действий и O(n·2ⁿ) памяти.

Ловушки джокера

Скобки. Сдвиг слабее сложения: 1 << k - 1 - это 1 << (k − 1).

^ как степень. 2 ^ 10 равно 8. Степень - 2 ** 10 или 1 << 10.

+ вместо |. Работает, пока биты не пересеклись; потом перенос портит соседний разряд: {1, 3} плюс элемент 1 даёт {2, 3}.

~ без рамки. ~0x0F в Python равно −16. Нужно ~0x0F & 0xFF.

Переполнение молчит. Сумма двух положительных стала отрицательной. В C для знаковых это ещё и неопределённое поведение.

Знаковое с беззнаковым. В C -1 < 1u ложно, а for (unsigned i = n - 1; i >= 0; i--) бесконечен.

Модуль наименьшего числа. −(−128) в восьми битах равно −128.

Сдвиг вместо деления отрицательного. -7 >> 1 равно −4, деление в C даёт −3.

Номера с единицы. Цифре d отводят бит d − 1 и забывают сдвиг при записи или при чтении.

Проверка бита через == 1. a & m равно не единице, а m. Сравнивать с нулём.

s >= 0 в цикле подмасок. (0 − 1) & m возвращает m, цикл бесконечен.

Одно разбиение много раз. Три группы цикл находит шестью способами; лечится правилом «старший элемент обязан входить в s».

Число со сдвигом растёт. mozhno << w без маски удлиняется в Python и теряет биты в C.

Первый символ строки - старший бит. После int(s, 2) символ номер k слева - бит длина − 1 − k.

Куда это ведёт

В цикле подмасок спрятаны два наблюдения про вычитание единицы: s − 1 переворачивает младшую единицу и всё под ней, а s & (s − 1) эту единицу убирает. Следующая глава строит на них целое семейство приёмов: проверка степени двойки одной строкой, счёт единиц за число единиц, а не за число битов, и логарифм числа без цикла.