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


Данный урок посвящён битовым операциям (операциям с битами, битовой математике, bitmath), из него вы узнаете, как оперировать с битами – элементарными ячейками памяти микроконтроллера. Мы уже сталкивались с битовыми операциями в уроке про регистры микроконтроллера, сейчас рассмотрим всё максимально подробно. Данная тема является одной из самых сложных для понимания в рамках данного курса уроков, так что давайте разберёмся, зачем вообще нужно уметь работать с битами:

  • Гибкая и быстрая работа напрямую с регистрами микроконтроллера (в том числе для написания библиотек)
  • Более эффективное хранение данных (упаковка нескольких значений в одну переменную и распаковка обратно)
  • Хранение символов и другой информации для матричных дисплеев (упаковка в один байт)
  • Максимально быстрые вычисления
  • Работа со сдвиговыми регистрами и другими подобными железками
  • Разбор чужого кода

Данный урок основан на оригинальном уроке по битовым операциям от Arduino, можете почитать его здесь – там всё описано чуть более подробно.

Двоичная система и хранение данных


В начале цикла уроков (в уроке о типах данных) мы уже разбирали тему систем исчисления и важность двоичной системы. Давайте коротко вспомним, как это всё работает.

Минимальная ячейка памяти, которую мы можем изменить – бит, он принимает всего два значения: 0 и 1. Минимальная ячейка памяти, к которой мы можем обратиться (которая имеет адрес в памяти) – байт, байт состоит из 8-ми бит, каждый занимает свою ячейку (примечание: в других архитектурах в байте может быть больше или меньше бит, в данном уроке речь идёт об AVR и 8-ми битном байте). Таким образом, байт – это элементарный блок памяти, к которому мы можем обратиться и читать/записывать данные, самый младший тип данных в Arduino так и называется – byte.

Обратившись к байту, мы можем манипулировать битами, из которых он состоит, именно для этого и используются операции с битами. Если мы “включим” все биты в байте, то получится число 0b11111111 в двоичной системе, или 255 в десятичной. Здесь нужно вспомнить важность степени двойки – на ней в битовых операциях завязано абсолютно всё. Давайте посмотрим на первые 8 степеней двойки (начиная с 0):

2 в степени DEC BIN
0 1 0b00000001
1 2 0b00000010
2 4 0b00000100
3 8 0b00001000
4 16 0b00010000
5 32 0b00100000
6 64 0b01000000
7 128 0b10000000

Таким образом, степень двойки явно “указывает” на номер бита в байте, считая справа налево (примечание: в других архитектурах может быть иначе). Напомню, что абсолютно неважно, в какой системе исчисления вы работаете – микроконтроллеру всё равно и он во всём видит единицы и нули. Если “сложить” полный байт в десятичном представлении битов, то мы получим как раз 255: 128+64+32+16+8+4+2+1 = 255. Нетрудно догадаться, что число 0b11000000 равно 128+64, то есть 192. Именно таким образом и получается весь диапазон от 0 до 255, который умещается в один байт. Если взять два байта – будет всё то же самое, просто ячеек будет 16, то же самое для 4 байт – 32 ячейки с единицами и нулями, каждая имеет свой номер согласно степени двойки.

Давайте начнём манипуляции с битами с самого простого – с макро-функций, которые идут “в комплекте” с ядром Arduino.

Макросы для манипуляций с битами


В “библиотеке” Arduino.h есть несколько удобных макросов, которые позволяют включать и выключать биты в байте:

Макросы Arduino.h Действие
bitRead(value, bit) Читает бит под номером bit в числе value
bitSet(value, bit) Включает (ставит 1) бит под номером bit в числе value
bitClear(value, bit) Выключает (ставит 0) бит под номером bit в числе value
bitWrite(value, bit, bitvalue) Ставит бит под номером bit в состояние bitvalue (0 или 1) в числе value
bit(bit) Возвращает 2 в степени bit
Другие встроенные макросы  
_BV(bit) Возвращает 2 в степени bit
bit_is_set(value, bit) Проверка на включенность (1) бита bit в числе value
bit_is_clear(value, bit) Проверка на выключенность (0) бита bit в числе value

Простой пример:

// тут myByte == 0
byte myByte = 0;

// тут myByte станет 128 или 0b10000000
bitSet(myByte, 7);

// тут myByte станет 192 или 0b11000000
bitWrite(myByte, 6, 1);

Есть ещё макрос _BV, который сидит в других файлах ядра и в целом является стандартным макросом для других платформ и компиляторов, он делает то же самое, что bit(b) – возвращает 2 в степени b

Также в ядре Arduino есть ещё два макроса для проверки состояния бита в байте, bit_is_set() и bit_is_clear(), их удобно использовать для условных конструкций с if.

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

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


Переходим к более сложным вещам. На самом деле они максимально просты для микроконтроллера, настолько просты, что выполняются за один такт. При частоте 16 МГц (большинство плат Arduino) одна операция занимает 0.0625 микросекунды.

Битовое И


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

0 & 0 == 0
0 & 1 == 0
1 & 0 == 0
1 & 1 == 1

Основное применение операции И – битовая маска. Позволяет “взять” из байта только указанные биты:

myByte = 0b11001100;
myBits = myByte & 0b10000111;
// myBits теперь равен 0b10000100

То есть при помощи & мы взяли из байта 0b11001100 только биты 10000111, а именно – 0b11001100, и получили 0b10000100

Также можно использовать составной оператор &=

myByte = 0b11001100;
myByte &= 0b10000000; // берём старший бит
// myByte теперь 10000000

Битовое ИЛИ


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

0 | 0 == 0
0 | 1 == 1
1 | 0 == 1
1 | 1 == 1

Основное применение операции ИЛИ – установка бита в байте:

myByte = 0b11001100;
myBits = myByte | 0b00000001; // ставим бит №0
// myBits теперь равен 0b11001101

myBits = myBits | bit(1); // ставим бит №1
// myBits теперь равен 0b11001111

Также можно использовать составной оператор |=

myByte = 0b11001100;
myByte |= 16; // 16 - 2 в 4, включаем бит №4
// myByte теперь 0b11011100

Вы уже поняли, что указывать на нужные биты можно любым удобным способом: в бинарном виде (0b00000001 – нулевой бит), в десятичном виде (16 – четвёртый бит) или при помощи макросов bit или _BV (bit(7) даёт 128 или 0b10000000, _BV(7) делает то же самое)

Битовое НЕ


Битовая операция НЕ (NOT) выполняется оператором и просто инвертирует бит:

~0 == 1
~1 == 0

Также она может инвертировать байт:

myByte = 0b11001100;
myByte = ~myByte; // инвертируем
// myByte теперь 00110011

Битовое исключающее ИЛИ


Битовая операция исключающее ИЛИ (XOR) выполняется оператором ^ и делает следующее:

0 ^ 0 == 0
0 ^ 1 == 1
1 ^ 0 == 1
1 ^ 1 == 0

Данная операция обычно используется для инвертирования состояния отдельного бита:

myByte = 0b11001100;
myByte ^= 0b10000000; // инвертируем 7-ой бит
// myByte теперь 01001100

То есть мы взяли бит №7 в байте 0b11001100 и перевернули его в 0, получилось 0b01001100, остальные биты не трогали.

Битовый сдвиг


Битовый сдвиг – очень мощный оператор, позволяет буквально “двигать” биты в байте вправо и влево при помощи операторов >> и <<, и соответственно составных >>= и <<= Если биты выходят за границы блока (8 бит, 16 бит или 32 бита) – они теряются.

myByte = 0b00011100;
myByte = myByte << 3; // двигаем на 3 влево
// myByte теперь 0b11100000

myByte >>= 5;
// myByte теперь 0b00000111

myByte >>= 2;
// myByte теперь 0b00000001
// остальные биты потеряны!

Битовый сдвиг делает не что иное, как умножает или делит байт на 2 в степени. Да, это операция деления, выполняющаяся за один такт процессора! К этому мы ещё вернёмся ниже. Посмотрите на работу оператора сдвига и сравните её с макросами bit и _BV:

1 <<  0  ==    1
1 <<  1  ==    2
1 <<  2  ==    4
1 <<  3  ==    8
...
1 <<  8  ==  256
1 <<  9  ==  512
1 << 10  == 1024

Да, это возведение двойки в степень!

Включаем-выключаем


Вспомним пример из пункта про битовое ИЛИ, про установку нужного бита. Вот эти варианты кода делают одно и то же:

myByte = 0b11000011;
// ставим бит №3 разными способами
// по сути - одно и то же

myByte |= (1 << 3);
myByte |= bit(3);
myByte |= _BV(3);
bitSet(myByte, 3);
// myByte равен 0b11001011

Как насчёт установки нескольких бит сразу?

myByte = 0b11000011;
// ставим бит №3 и 4 разными способами
// по сути - одно и то же

myByte |= (1 << 3) | (1 << 4);
myByte |= bit(3) | bit(4);
myByte |= _BV(3) | _BV(4);
// myByte равен 0b11011011

Или прицельного выключения бит? Тут чуть по-другому, используя &= и ~

myByte = 0b11000011;
// выключаем бит №1 разными способами
// по сути - одно и то же

myByte &= ~(1 << 1);
myByte &= ~_BV(1);
bitClear(myByte, 1);
// myByte равен 0b11000001

Выключить несколько бит сразу? Пожалуйста!

myByte = 0b11000011;
// выключаем биты №0 и 1 разными способами

myByte &= ~( (1 << 0) | (1 << 1) );
myByte &= ~( _BV(0) | _BV(1) );
// myByte равен 0b11000000

Именно такие конструкции встречаются в коде высокого уровня и библиотеках, именно так производится работа с регистрами микроконтроллера.

Вернёмся к устройству Ардуиновских макросов:

#define bitRead(value, bit) (((value) >> (bit)) & 0x01)
#define bitSet(value, bit) ((value) |= (1UL << (bit)))
#define bitClear(value, bit) ((value) &= ~(1UL << (bit)))
#define bitWrite(value, bit, bitvalue) (bitvalue ? bitSet(value, bit) : bitClear(value, bit))
#define bit(b) (1UL << (b))

Я думаю, комментарии излишни: макросы состоят из тех же элементарных битовых операций и сдвигов!

Быстрые вычисления


Как я уже говорил, битовые операции – самые быстрые операции, выполняются за один такт процессора. При помощи знания битовых операций можно делать некоторые вещи гораздо быстрее. Но так ли это? Можно разделить число на 2 в степени, например разделим число 3651 на 8:

int myVal = 3651;
myVal >>= 3;
// myVal равна 456

Операция деления – очень медленная, но на степень двойки она выполняется максимально быстро для МК – за один такт. Особо усердствовать с такой оптимизацией не стоит – компилятор сам оптимизирует вычисления перед загрузкой кода в МК: если мы напишем 3651 / 8, оно само превратится в 3651 >>= 3 на этапе компиляции. Деление на другие числа компилятор тоже может оптимизировать – вычесть до степени двойки, разделить “сдвигом” и прибавить остаток. Но деление именно на степень двойки будет быстрее, так как нет лишних действий.

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


При помощи битовых операций можно экономить немного памяти, пакуя данные в блоки. Например, переменная типа boolean занимает в памяти 8 бит, хотя принимает только 0 и 1. В один байт можно запаковать 8 логических переменных, например вот так:

// храним флаги как 1 бит

// макросы
#define B_TRUE(bp,bb)    (bp) |= (bb)
#define B_FALSE(bp,bb)   (bp) &= ~(bb)
#define B_READ(bp,bb)    bool((bp) & (bb))

// вот так храним наши флаги, значения обязательно как степени двойки!
#define B_FLAG_1        1
#define B_FLAG_2        2
#define B_LED_STATE     4
#define B_BUTTON_STATE  8
#define B_BUTTON_FLAG   16
#define B_SUCCESS       32
#define B_END_FLAG      64
#define B_START_FLAG    128

// этот байт будет хранить 8 бит
byte boolPack1 = 0;

void setup() {
  // суть такая: макрос функциями мы ставим/читаем бит в байте boolPack1

  // записать true во флаг B_BUTTON_STATE
  B_TRUE(boolPack1, B_BUTTON_STATE);

  // записать false во флаг B_FLAG_1
  B_FALSE(boolPack1, B_FLAG_1);

  // прочитать флаг B_SUCCESS (для примера читаем в булин переменную)
  boolean successFlag = B_READ(boolPack1, B_SUCCESS);

  // либо используем в условии
  if (B_READ(boolPack1, B_SUCCESS)) {
    // выполнить при выполнении условия
  }
}

void loop() { }

// пример упаковки битовых флагов в байт
// при помощи ардуино-функций

byte myFlags = 0; // все флаги в false

// можно задефайнить названия
// цифры по порядку 0-7
#define FLAG1 0
#define FLAG2 1
#define FLAG3 2
#define FLAG4 3
#define FLAG5 4
#define FLAG6 5
#define FLAG7 6
#define FLAG8 7

void setup() {
  // установить FLAG5 в true
  bitSet(myFlags, FLAG5);
  // установить FLAG1 в true
  bitSet(myFlags, FLAG1);

  // установить FLAG1 в false
  bitClear(myFlags, FLAG1);

  // считать FLAG5
  bitRead(myFlags, FLAG5);

  // условие с флагом 7
  if (bitRead(myFlags, FLAG7)) {
    // если FLAG7 == true
  }
}

void loop() {}

Хороший трюк, может пригодиться!

“Трюки” с битами


На битовых операциях можно сделать очень много всего интересного, и работать оно будет очень быстро и занимать мало места. Огромный список битовых трюков и хаков можно посмотреть в этой статье, их там очень много и все с примерами. Есть ещё один небольшой сборник самых простых и полезных хаков вот здесь (английский). Его я перевёл, смотрите ниже под спойлером. Другой вариант перевода (могут быть не все трюки) можно посмотреть здесь.

Целые


Установка nго бита

x | (1<<n)

Выключение nго бита

x & ~(1<<n)

Инверсия nго бита

x ^ (1<<n)

Округление до ближайшей степени двойки

unsigned int v; // работает только с 32 битными числами
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

Округление вниз

n >> 0

5.7812 >> 0 // вернёт 5

Получение максимального целого

int maxInt = ~(1 << 31);
int maxInt = (1 << 31) - 1;
int maxInt = (1 << -1) - 1;
int maxInt = -1u >> 1;

Получение минимального целого

int minInt = 1 << 31;
int minInt = 1 << -1;

Получение максимального long

long maxLong = ((long)1 << 127) - 1;

Умножение на 2

n << 1; // n*2

Деление на 2

n >> 1; // n/2

Умножение на mую степень двойки

n << m;

Деление на mую степень двойки

n >> m;

Проверка равенства

(a^b) == 0; // a == b
!(a^b) // использовать внутри if()

Проверка на чётность (кратность 2)

(n & 1) == 1;

Обмен значениями

//version 1
a ^= b;
b ^= a;
a ^= b;

//version 2
a = a ^ b ^ (b = a)

Получение абсолютного значения

//version 1
x < 0 ? -x : x;

//version 2
(x ^ (x >> 31)) - (x >> 31);

Максимум из двух

b & ((a-b) >> 31) | a & (~(a-b) >> 31);

Минимум из двух

a & ((a-b) >> 31) | b & (~(a-b) >> 31);

Проверка на одинаковый знак

(x ^ y) >= 0;

Смена знака

i = ~i + 1; // or
i = (i ^ -1) + 1; // i = -i

Вернёт 2n

1 << n;

Является ли число степенью 2

n > 0 && (n & (n - 1)) == 0;

Остаток от деления на 2n на m

m & ((1 << n) - 1);

Среднее арифметическое

(x + y) >> 1;
((x ^ y) >> 1) + (x & y);

Получить mый бит из n (от младшего к старшему)

(n >> (m-1)) & 1;

Получить mый бит из n (от старшего к младшему)

n & ~(1 << (m-1));

Проверить включен ли nый бит

if (x & (1<<n)) {
  n-th bit is set
} else {
  n-th bit is not set
}

Выделение самого правого включенного бита

x & (-x)

Выделение самого правого выключенного бита

~x & (x+1)

Выделение правого включенного бита

x | (x+1)

Выделение правого выключенного бита

x & (x-1)

n + 1

-~n

n – 1

~-n

Получение отрицательного значения

~n + 1;
(n ^ -1) + 1;

if (x == a) x = b; if (x == b) x = a;

x = a ^ b ^ x;

Поменять смежные биты

((n & 10101010) >> 1) | ((n & 01010101) << 1)

Different rightmost bit of numbers m & n

(n^m)&-(n^m) // returns 2^x where x is the position of the different bit (0 based)

Common rightmost bit of numbers m & n

~(n^m)&(n^m)+1 // returns 2^x where x is the position of the common bit (0 based)

Десятичные дроби


Примечание: хаки с float могут не работать на Ардуино!

Разбить float в массив бит (unsigned uint32_t)

#include <stdint.h>
typedef union {float flt; uint32_t bits} lens_t;
uint32_t f2i(float x) {
  return ((lens_t) {.flt = x}).bits;
}

Вернуть массив бит обратно в float

float i2f(uint32_t x) {
  return ((lens_t) {.bits = x}).flt;
}

Быстрый обратный квадратный корень

return i2f(0x5f3759df - f2i(x) / 2);

Быстрый nый корень из целого числа

float root(float x, int n) {
#DEFINE MAN_MASK 0x7fffff
#DEFINE EXP_MASK 0x7f800000
#DEFINE EXP_BIAS 0x3f800000
  uint32_t bits = f2i(x);
  uint32_t man = bits & MAN_MASK;
  uint32_t exp = (bits & EXP_MASK) - EXP_BIAS;
  return i2f((man + man / n) | ((EXP_BIAS + exp / n) & EXP_MASK));
}

Быстрая степень

return i2f((1 - exp) * (0x3f800000 - 0x5c416) + f2i(x) * exp)

Быстрый натуральный логарифм

#DEFINE EPSILON 1.1920928955078125e-07
#DEFINE LOG2 0.6931471805599453
return (f2i(x) - (0x3f800000 - 0x66774)) * EPSILON * LOG2

Быстрая экспонента

return i2f(0x3f800000 + (uint32_t)(x * (0x800000 + 0x38aa22)))

Строки


Конвертировать в нижний регистр

(x | ' ')
пример: ('a' | ' ') => 'a' ; ('A' | ' ') => 'a'

Конвертировать в верхний регистр

(x & '_')
пример: ('a' & '_') => 'A' ; ('A' & '_') => 'A'

Инвертировать регистр

(x ^ ' ')
пример: ('a' ^ ' ') => 'A' ; ('A' ^ ' ') => 'a'

Позиция буквы в алфавите (англ)

(x & "\x1F")
Пример: ('a' & "\x1F") => 1 ; ('B' & "\x1F") => 2

Позиция большой буквы в алфавите (англ)

(x & '?') или (x ^ '@')
Пример: ('C' & '?') => 3 ; ('Z' ^ '@') => 26

Позиция строчной буквы в алфавите (англ)

(x ^ '`')
Пример: ('d' ^ '`') => 4 ; ('x' ^ '`') => 24

Другое


Быстрая конвертация цвета R5G5B5 в R8G8B8

R8 = (R5 << 3) | (R5 >> 2)
G8 = (R5 << 3) | (R5 >> 2)
B8 = (R5 << 3) | (R5 >> 2)

Важные страницы


  • Каталог ссылок на дешёвые Ардуины, датчики, модули и прочие железки с AliExpress у проверенных продавцов
  • Подборка библиотек для Arduino, самых интересных и полезных, официальных и не очень
  • Полная документация по языку Ардуино, все встроенные функции и макро, все доступные типы данных
  • Сборник полезных алгоритмов для написания скетчей: структура кода, таймеры, фильтры, парсинг данных
  • Видео уроки по программированию Arduino с канала “Заметки Ардуинщика” – одни из самых подробных в рунете