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

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

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

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

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

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

И (AND) #

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

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

// 0b11010110 & 0b01101101

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

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

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

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

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

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

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

ИЛИ (OR) #

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

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

// 0b11010110 | 0b01101101

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

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

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

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

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

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

// 0b11110000 ^ 0b10000001

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

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

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

НЕ (NOT) #

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

// ~0b11110000

0b11110000
// ~
0b00001111

Сдвиг #

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

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

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

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

Арифметический сдвиг #

При сдвиге влево << справа будут "выдвинуты" нули, т.е. 0b11 << 2 == 0b1100. При сдвиге вправо >> слева будут выдвинуты нули, если это unsigned число, и единицы, если это signed число. Другими словами, при сдвиге вправо сохраняется знак - так называемый арифметический сдвиг.

short val = -123;
val >>= 4;      // val == -8
// 0b1111111110000101 >> 4 == 0b1111111111111000

unsigned short val = 54321;
val >>= 4;      // val == 3395
// 0b1101010000110001 >> 4 == 0b0000110101000011

Применение #

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

Если вспомнить двоичную систему счисления, то можно догадаться, что сдвиг влево - это умножение на 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

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

При помощи битовой маски можно очень эффективно получать остаток от деления на число, которое является 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.

Получить маску #

Очень легко получить маску на n младших бит следующим образом: (1 << n) - 1. Например маска на 3 младших бита равна (1 << 3) - 1 == 0b111.

Выбор бита #

Сдвиг влево позволяет "создать" значение, в котором установлен один конкретный бит под номером 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 биты
//val |= _BV(3) | _BV(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 биты

Arduino #

В фреймворке Arduino есть несколько удобных макросов (см. справочник) для манипуляций с битами. Например bitSet(x, 3) установит третий бит в переменной x, bitClear(x, 6) - сбросит 6-ой бит, bitWrite(x, 4, 1) - установит 4-ый бит в 1.

Записать несколько бит #

При работе с регистрами часто бывает нужно записать несколько бит в байт, заменив старые значения новыми. Эта задача решается так: взять маской остальную часть байта (чтобы нужные биты обнулились) и прибавить к результату нужную комбинацию единиц через ИЛИ. Результат приравнять к исходному байту:

uint8_t reg = 0b11001100;
uint8_t val = 0b001;

// допустим, нужно записать в начало reg три бита val
reg = (reg & ~0b111) | val;
// reg == 0b11001001

// а теперь - в конец (8 - 3 = 5)
reg = (reg & ~(0b111 << 5)) | (val << 5);
// reg == 0b00101001

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

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

uint8_t byteHigh, byteLow;
// ...
uint16_t val = (byteHigh << 8) | byteLow;

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

uint8_t byte2, byte1, byte0;
// ...
uint32_t val = (byte2 << 16) | (byte1 << 8) | byte0;

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

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

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

Прочие трюки #

Остальные примеры с битовой математикой вынесены в сборники алгоритмов:

• Битовые флаги
• Битовые трюки

Дополнительно #

Полезные страницы #

• Набор GyverKIT – наш большой стартовый набор Arduino, продаётся в России
• Каталог ссылок на дешёвые Ардуины, датчики, модули и прочие железки с AliExpress
• Обратная связь – сообщить об ошибке в уроке или предложить дополнение по тексту ([email protected])
• Поддержать автора за работу над уроками