Битовые операции: сдвиги, маски, поразрядные трюки

Сигнализацию на сто зон я начинал честно: bool zona[100] — по переменной на датчик, сто байт из двух килобайт, живём. Убило не место, а EEPROM: захотел хранить карту зон между включениями — и получил сто ячеек по три миллисекунды записи, треть секунды на каждое сохранение. Радио-пакет со статусом разросся до ста байт, где половину съедали нули. Всё состояние при этом честно укладывалось в тринадцать байт — по одному биту на зону, — но переписывать проект побитово было страшно: казалось, что это уровень регистров и ассемблера.

Оказалось — уровень обычного C: битовые операции уже были в арсенале, не хватало только привычки думать «флаг = бит». Один байт держит восемь флагов, int — шестнадцать, сто датчиков — тринадцать байт, тринадцать ячеек EEPROM, тринадцать байт пакета. И побочные подарки: количество сработавших зон считается циклом по тринадцати байтам, а не по ста bool, карта печатается в Serial одним числом, EEPROM пишется одним прогоном.

Здесь собираем битовую карту массива флагов: индексация через сдвиги, подсчёт единиц, поиск границ — и честно разберём, где трюки со сдвигами кусаются: на знаковом int единица в шестнадцатом разряде уезжает в минус. Четыре приёма установки, сброса, проверки и переключения бита — таблица умножения, которую я уже раскладывал в уроке про побитовые операции на байте флагов — там они на устройстве с шестью переключателями; здесь масштаб больше: карта на сотню датчиков.

Тип byte — восемь бит, int на Uno — шестнадцать. Массив из шестнадцати bool съедает шестнадцать байт: на AVR bool занимает целый байт, промежуточных значений между 0 и 1 нет. Один int с флагами — два байта, экономия в восемь раз на любом объёме. Для шестнадцати флагов это смешные четырнадцать байт, для ста зон — уже восемьдесят семь, а для карты занятости из пятисот ячеек склада — пятьсот байт против шестидесяти трёх. Память — не главный приз, но главный аргумент, когда проект начинает дышать на свободные килобайты.

Механика доступа: флаг номер n живёт в байте с номером n >> 3 и бите n & 7. Сдвиг вправо на три — деление на восемь, остаток от деления достаётся маской на младшие три бита. Установить: karta[n >> 3] |= (1 << (n & 7)); снять: &= ~(1 << (n & 7)); проверить: if (karta[n >> 3] & (1 << (n & 7))). Скобки обязательны в каждой операции: у сдвига и масок приоритеты устроены коварно, и if (karta[i] & 1 << n == 0) проверяет не то, что написано словами.

Теперь то, ради чего карта делается вовсе: состояние целиком — одно число. Печать в Serial — одна строка, EEPROM — тринадцать ячеек по три миллисекунды вместо ста, радио-пакет — тринадцать байт. Количество единиц считается не просмотром ста bool, а циклом по тринадцати байтам с трюком, который снимает по единице за шаг.

Разбор. karta[n >> 3] выбирает нужный байт: флаг 99 живёт в байте 12 (99 >> 3 = 12), в бите 3 (99 & 7 = 3). Цикл подсчёта — трюк Кернигана: b &= b - 1 сбрасывает самый младший единичный бит, и число итераций равно числу единиц, а не разрядности. Три сработавшие зоны из ста — три шага на весь массив. Альтернатива — восемь проверок на байт через сдвиги — тоже честна, но вдвое-втрое длиннее; на карте из тринадцати байт разница микроскопична, на больших картах уже заметна.

Печать я выбрал HEX-ом по байтам: Serial.print(b, BIN) для байта 0b00000001 напечатает 1 без ведущих нулей, и карта собьётся в нечитаемую кашу — ведущие нули и механика второго аргумента разобраны в уроке про BIN, HEX и DEC. Двоичная система, на которой вся эта кухня стоит, — тема отдельного урока: если веса разрядов до сих пор в голове с оговорками, начните оттуда.

И главное — одно число вместо ста переменных. Карта складывается в EEPROM тринадцатью вызовами EEPROM.update — сорок миллисекунд против трети секунды; уезжает в радио-пакет тринадцатью байтами вместо ста; хранится в RAM там, где раньше лежали сто bool. Приз не в байтах, а в том, что операции над состоянием перестали быть операциями над массивом: одна строка вместо цикла.

int на Uno — шестнадцать бит со знаком, и карта на шестнадцать флагов встаёт на минное поле: 1 << 15 уводит единицу в старший, знаковый разряд. Значение получается -32768, Serial печатает минус, и сравнение вида flags > 100 ложно для половины карт: любое число со стоящим старшим битом отрицательно, и пороги, написанные в расчёте на положительные величины, молчат. Сама карта в BIN при этом правильная — бит на месте, — ломается арифметика вокруг. Лечение: для карт на шестнадцать флагов берите unsigned int, а маски собирайте как ((unsigned int)1 << n); на byte-картах проблемы нет — знакового разряда там не существует.

Второй подвох — сдвиг вправо отрицательных чисел: >> для знаковых типов копирует знаковый бит, и -7 >> 1 даёт -4, а деление -7 / 2 — минус три: сдвиг тянет вниз, деление округляет к нулю. Для карт это ещё один аргумент за unsigned: у беззнаковых типов сдвиг вправо честно подставляет нули. Третья ловушка — проверка «число — степень двойки» через (v & (v - 1)) == 0: на нуле она отвечает истина, потому что 0 & 255 обнуляется; правильная форма — v != 0 && (v & (v - 1)) == 0. Ловушка мелкая, но именно такие места потом ищутся вечерами.

Отдельное мнение, чтобы не плодить культ: трюки ради тактов — самообман. Деление на степень двойки компилятор заменяет сдвигом сам, обмен значений через тройной XOR он делает лучше и без нулевых времён — я перестал писать такое руками ещё на первом листинге, где компилятор выдал тот же машинный код для обоих вариантов. Оправданы трюки ради памяти и ради «одно число — одна операция»: карта в EEPROM, пакет в радио, байт статуса в Serial. Это то, что не заменит никакой оптимизатор.

Граница применимости — сверху, а не снизу. До пяти-шести флагов карта — комбинаторика ради комбинаторики: пять именованных переменных с говорящими именами читаются лучше, чем биты под номерами, и я так и оставляю мелочь на bool. Карта оправдывает себя с момента, когда флаги становятся массивом: зоны охраны, занятость ячеек, неделя архива состояний, карта ошибок по датчикам. Второй сигнал — когда состояние должно покидать скетч: EEPROM, Serial, радио. Массив bool туда едет циклом, карта — одной строкой.

Если захочется уплотнить и дальше — есть PROGMEM для больших таблиц констант и структуры с битовыми полями, где компилятор сам раскладывает поля по битам. Домашнее: добавьте к карте поиск номера самой старшей сработавшей зоны — цикл от байта 12 вниз с проверкой старшего бита; и сохраните карту в EEPROM в момент, когда сработавших зон становится больше пяти, восстановив её в setup() после ребута.