Битовые операции

Как уже говорилось ранее, минимальная адресуемая ячейка памяти - 1 байт, то есть можно записать и прочитать из памяти данные размером как минимум 1 байт, переменную тоже можно сделать минимум 1 байт размером (исключение - битовые поля в структурах). Байт состоит из 8 бит, есть ли у нас возможность работать с ними напрямую? Есть - в C/C++ есть поддержка битовых операций.

Битовые операции позволяют взаимодействовать непосредственно с битами значения, этот процесс также называется битовой математикой (bit math). С их помощью можно не только получить доступ к конкретному биту, но и выполнять более сложные операции очень быстро - процессор обычно имеет набор аппаратных инструкций с битовыми операциями и они выполняются за один такт.

При помощи битовых операций можно:

• "Собирать" значения с любым нужным набором битов
• Паковать и распаковывать данные
• Настраивать биты в регистрах МК и цифровых микросхем
• Писать очень хитрые и эффективные алгоритмы для вычислений и обработки данных
• Понимать чужой код, который использует битовые операции 🙂

Битовые операторы #

И (AND) #

Битовое И (битовое умножение) выполняется между двумя значениями при помощи оператора & и похоже на логическое И, имеет такую же таблицу истинности:

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

// 0b11010110 & 0b01101101

0b11010110
// &
0b01101101
// =
0b01000100

Получается результат, у которого единицы есть только там, где были единицы у обоих чисел. Битовое И обычно используется там, где нужно взять конкретные биты из числа - битовая маска (bit mask). В этом случае одно число это просто число, а другое - маска. После операции И мы получим результат, у которого единицы есть только в тех местах, где они есть и в маске. Можно делать это хоть по одному биту, например для того, чтобы вручную прочитать каждый бит из числа:

0b11010110
0b10000000  // маска
// &
0b10000000

0b11010110
0b01000000  // маска
// &
0b01000000

0b11010110
0b00100000  // маска
// &
0b00000000

Можно использовать и составной оператор &=:

uint8_t val = 0b11010110;
val &= 0b00010000;
// val == 0b00010000

Остаток от деления #

При помощи битовой маски можно очень эффективно получать остаток от деления на число, которое является 2^n (2, 4, 8, 16, 32...). Для этого мы по сути делаем маску, которая выберет нужные биты - это будут все младшие биты справа от единицы.

Чтобы получить остаток от деления на 8 (0b1000), достаточно взять маской три младших бита, то есть маска получится 0b111:

// 73 % 8
73 & 0b111; // == 1001001 & 0b111 == 1

Маску младших битов можно получить, если отнять от делителя единицу - 0b1000 - 1 == 0b0111. Таким образом получается формула быстрого остатка от деления: val % (2^n) можно вычислить как val & (2^n - 1), то есть 73 % 8 == 73 & 7.

ИЛИ (OR) #

Битовое ИЛИ (битовое сложение) выполняется между двумя значениями при помощи оператора | и похоже на логическое ИЛИ, имеет такую же таблицу истинности:

Логика такая же - два числа побитно "складываются": у результата будут единицы в тех местах, где у чисел есть хотя бы одна единица:

// 0b11010110 | 0b01101101

0b11010110
// |
0b01101101
// =
0b11111111

Используется там, где нужно "сложить" биты. Также имеется составной оператор |=:

uint8_t val = 0b11110000;
val |= 0b00001111;
// val == 0b11111111

Исключающее ИЛИ (XOR) #

Битовое исключающее ИЛИ, или "сложение по модулю", выполняется между двумя значениями при помощи оператора ^ или xor:

Может использоваться для инвертирования конкретных битов - они должны быть единицами в "маске":

// 0b11110000 ^ 0b10000001

0b11110000
// ^
0b10000001
// =
0b01110001

Можно использовать и составной оператор ^=:

uint8_t val = 0b11110000;
val ^= 0b11110001;
// val == 0b00000001

НЕ (NOT) #

Битовая операция НЕ выполняется с одним значением при помощи оператора ~ и просто инвертирует все биты:

// ~0b11110000

0b11110000
// ~
0b00001111

Сдвиг #

Операция битовый сдвиг (bit shift) выполняется с двумя значениями при помощи операторов >> и << и буквально сдвигает биты первого значения в указанном направлении на расстояние в битах, равное второму значению.

0b00111100 << 2;    // == 0b11110000
0b11110000 >> 4;    // == 0b00001111
0b00001111 >> 2;    // == 0b00000011

Можно использовать и составные операторы >>= и <<=:

uint8_t val = 0b00011000;
val >>= 3;
// val == 0b00000011;

Умножение и деление #

Если вспомнить двоичную систему счисления, то можно догадаться, что сдвиг влево - это умножение на 2^n, а сдвиг вправо - деление на 2^n, где n - величина сдвига:

0b00000001 << 3;    // == 0b00001000 == 1 * 2^3 == 1 * 8 == 8
1 << 3;             // == 8

0b00100101 >> 2;    // == 0b00001001 == 37 / 2^2 == 37 / 4 == 9
37 >> 2;            // == 9

Выбор бита #

Сдвиг влево позволяет "создать" значение, в котором установлен один конкретный бит под номером n - 1 << n, счёт начинается с нуля справа налево:

1 << 0;     // == 0b00000001
1 << 5;     // == 0b00100000
1 << 7;     // == 0b10000000

Применение #

Включить бит #

На практике очень часто бывает нужно установить (set) конкретный бит в числе - сделать его единицей. Для этого используется типовая конструкция val |= (1 << n), где n - номер бита.

Как это работает - при помощи (1 << n) получаем значение с одиноким битом под указанным номером, а затем просто "прибавляем" его при помощи битового ИЛИ:

0b00000000 | (1 << 3) == 0b00000000 | (0b1000) == 0b00001000

Можно установить несколько бит сразу, сложив одинокие биты при помощи |:

val |= (1 << 3) | (1 << 7);     // установить 3 и 7 биты

Выключить бит #

Не менее часто бывает нужно сбросить (clear) нужный бит в числе - сделать его нулём. Для этого используется типовая конструкция val &= ~(1 << n), где n - номер бита.

Как это работает - при помощи (1 << n) получаем значение с одиноким битом под указанным номером, затем инвертируем его, чтобы получить маску. И эту маску применяем к числу - маска возьмёт все биты кроме указанного!

0b11111111 & ~(1 << 3) == 0b11111111 & ~(0b00001000) == 0b11111111 & (0b11110111) == 0b11110111

Можно сбросить несколько бит сразу, сложив одинокие биты при помощи |, а затем инвертировав их:

val &= ~( (1 << 3) | (1 << 7) );    // сбросить 3 и 7 биты

Склеить байты #

Ещё одна типовая задача - склеить число из старшего и младшего байтов. Для этого к младшему (low) байту через ИЛИ прибавляется старший (high), сдвинутый на 8 влево:

val = (byteHigh << 8) | byteLow;

Точно так же можно склеить и больше байтов:

val = (byte3 << 16) | (byte2 << 8) | byte0;

Разделить на байты #

Не менее типовая обратная задача - разделить на байты. Всё то же самое в обратном порядке:

byteLow = val & 0xff;       // берём маской младший байт, 0xff == 0b11111111
byteHigh = (val >> 8);      // младшие байты отсекутся при сдвиге

Экономия памяти #

В программировании часто используются "флаги" - логические значения. Тип bool у нас занимает 1 байт, то есть 8 бит. Расточительно! Можно "запаковать" 8 флагов в один байт - читать и писать их как биты, как было показано выше. Это довольно громоздкая запись, в отдельном уроке разберём более красивые реализации.

uint8_t flags = 0;
flags |= (1 << 3);      // установить флаг #3
flags &= ~(1 << 3);     // сбросить флаг #3
flags & (1 << 3);       // прочитать флаг #3

Проверка на -1 #

В программировании очень часто встречаются инструменты, которые возвращают -1 в случае ошибки или "не найдено", т.е. валидным значением считается 0 и положительные числа. Чтобы не сравнивать значение с нулём, например if (res < 0), можно использовать инверсию: в любом типе данных -1 это все биты - единички. Если инвертировать - получится ноль: if (~res) - проверка на -1.