Конспект раздела: битовые приёмы

Одна мысль на весь раздел

Число - это ещё и ряд битов, и у процессора есть действия, которые работают с рядом целиком за один шаг. Первые главы заменяют циклы по разрядам короткими последовательностями команд. В основе четыре семейства приёмов. Затем разбираем смысл весов разрядов и добавляем проверочные биты для обнаружения и исправления повреждений.

1. разряды независимы     &  |  ^  ~          множество в числе, 64 вопроса «да или нет» одной командой
2. перенос как указатель  x − 1, x + 1, −x    младшая единица, степень двойки, подмаски
3. слово как ряд полей    маски 0x55, 0x33…   счёт единиц, нулевой байт, разворот, раздвигание битов
4. знак как маска         x >> 31             модуль, минимум, выбор без ветвления

Как части связаны

шесть операций ──► маска и сдвиг ──► поля: цвет, адрес сети, дата, дробное число (знак, порядок, дробь)
      │
      ├──► дополнительный код: −x = ~x + 1 ──► x & −x ──► обход единиц, дерево Фенвика, трюк Госпера
      │                                   └──► x >> 31 как маска ──► без ветвлений
      │
      ├──► множество как число ──► подмаски (3ⁿ) ──► динамика по разбиениям
      │                       └──► битовый параллелизм ──► Хэмминг, суммы, достижимость
      │
      ├──► x & (x − 1) ──► степень двойки ──► остаток маской, выравнивание, хеш-таблицы
      │               └──► счёт единиц ──► длина числа ──► логарифм, корень, порядок дробного
      │
      └──► ^ без переноса ──► сложение = ^ + перенос ──► среднее без переполнения
                         ├──► код Грея: x ^ (x >> 1)
                         └──► CRC: деление, в котором вычитание - это ^

Что выбрать

Числа раздела, которые стоит помнить

3ⁿ против 4ⁿ:  n = 10 - 59 049 и 1 048 576            потолок подмасок: 15-18 элементов
ширина слова 64: постоянный множитель, порядок роста не меняется
2⁵³: предел точных целых в дробном числе; 53 значащих бита
ошибка предсказания перехода: 15-20 тактов;  случайные данные - ошибка в половине случаев
деление на 3: 0xAAAB и сдвиг 17 для 16 битов;  0xAAAAAAAB и 33 для 32 битов
CRC-32 от «123456789»: 0xCBF43926

Границы, общие для всех приёмов

Ширина. В C и в процессоре слово имеет ширину, и всё лишнее пропадает молча; в Python ширины нет, и рамку ставят маской. Приём, написанный для 32 битов, на 64-битном числе не падает, а врёт.

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

Порядок действий. Сдвиг слабее сложения, & слабее сдвига, сравнение в Python слабее всех побитовых, а в C сильнее &. Скобки в битовых выражениях ставят всегда.

Компилятор. Замену x * 2 на сдвиг, деления на константу на умножение, минимума на условную пересылку он делает сам. Руками приёмы нужны там, где он не может знать: множество в числе, битовый параллелизм, код без зависимости времени от секрета, разбор полей.

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

Приём без проверки на всех значениях. Формула, верная на трёх примерах, ломается на нуле, на наименьшем отрицательном или на верхней границе. Множитель для деления в разделе проверялся на всех 65 536 числах - и два похожих варианта не прошли.

Замер в тренажёре как замер времени. Тренажёр считает строки. Таблица у него дешевле арифметики, а ветвление дешевле маски; у настоящего процессора бывает наоборот - из-за кеша и предсказателя.

Хитрость ради хитрости. Обмен через ^, умножение сдвигами в исходном тексте, маска вместо понятного if на предсказуемом условии делают код хуже и не быстрее.

CRC как защита. Он против помех. Против человека - подпись.

Дробное число как точное. 53 бита, а не «достаточно много».

Границы слова и суммы по подмножествам

Представление и арифметика

В основании −2 веса равны 1,−2,4,−8,…, поэтому отдельный знак не нужен. Цифра r=n%2, следующее частное (n−r)//(-2). Перенос при сложении равен (s−digit)//(-2) и может быть отрицательным. Сдвиг влево умножает значение на −2. В основании −1+i цифры 0,1 кодируют пару целых координат, но арифметика получается сложнее хранения координат отдельно.

Цена основания зависит от модели. При цене разряда k·b и N состояниях стоимость равна k·b·ceil(log_b N). Непрерывный минимум при e объясняет сглаженную зависимость; для конкретного N нужны целые числа разрядов.

Обнаружение и исправление

Коды исправления добавляют проверочные разряды. При минимальном расстоянии d проверка принадлежности словарю замечает любые d−1 изменений, а исправление до ближайшего слова гарантировано лишь при 2t<d. Это разные обещания. У SEC-DED синдром по первой части и чётность всего слова дают четыре случая: принять, исправить один из первых битов, исправить общую чётность, отказаться от двойной ошибки. Для 32 данных нужно семь проверочных битов, всего 39. Для 64 данных - восемь проверочных, всего 72. Три ошибки могут выглядеть как одиночная ошибка другого сообщения.

Максимальный размер словаря A(n,d) ограничивается упаковкой шаров сверху и конструкциями снизу. Верхняя граница сама по себе не строит код: например, упаковка даёт A(4,3)≤3, а точный максимум равен 2.

Вопросы для повторения

1. Почему x & -x оставляет одну единицу - через ~x + 1.
2. Почему цикл s = (s - 1) & m не пропускает подмаски и откуда 3ⁿ.
3. Зачем в сложении половинками маска во второй строке стоит до сложения, а в третьей - после.
4. Почему множитель при делении на константу округляют вверх.
5. Почему (lo + hi) / 2 ошибочно, а (a & b) + ((a ^ b) >> 1) - нет.
6. Почему отсортированный массив обрабатывается быстрее случайного при том же числе сравнений.
7. Почему CRC замечает перестановку байтов, а сумма - нет, и почему он не защищает от подделки.
8. Почему после 2⁵³ дробные числа идут через одно целое.
9. Почему ни одна нумерация клеток не делает все соседние клетки соседними по номеру.
10. Почему обычный Хэмминг может ошибочно исправить две ошибки и как SEC-DED меняет решение.
11. Почему верхняя граница на размер кода не доказывает существование кода такого размера.
12. Почему при основании −2 две единицы складываются в 110 и как меняется перенос.
13. Почему непрерывный минимум цены при e не означает, что троичный регистр всегда дешевле двоичного.