О битовых операциях

Процессоры

О битовых операциях

Обложка: О битовых операциях

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

Введение

Побитовые операторы проводят операции непосредственно на битах числа, поэтому числа в примерах будут в двоичной системе счисления.

Я расскажу о следующих побитовых операторах:

  • | (Побитовое ИЛИ (OR)),
  • & (Побитовое И (AND)),
  • ^ (Исключающее ИЛИ (XOR)),

(Побитовое отрицание (NOT)),

  • > (Побитовый сдвиг вправо).
  • Битовые операции изучаются в дискретной математике, а также лежат в основе цифровой техники, так как на них основана логика работы логических вентилей — базовых элементов цифровых схем. В дискретной математике, как и в цифровой технике, для описания их работы используются таблицы истинности. Таблицы истинности, как мне кажется, значительно облегчают понимание битовых операций, поэтому я приведу их в этой статье. Их, тем не менее, почти не используют в объяснениях побитовых операторов высокоуровневых языков программирования.

    О битовых операторах вам также необходимо знать:

    1. Некоторые побитовые операторы похожи на операторы, с которыми вы наверняка знакомы (&&, ||). Это потому, что они на самом деле в чем-то похожи. Тем не менее, путать их ни в коем случае нельзя.
    2. Большинство битовых операций являются операциями составного присваивания.

    Побитовое ИЛИ (OR)

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

    38 | 53 будет таким:

    A00100110
    B00110101
    A | B00110111

    В итоге мы получаем 1101112 , или 5510 .

    Побитовое И (AND)

    Побитовое И — это что-то вроде операции, противоположной побитовому ИЛИ. Двоичный разряд результата равен 1 только тогда, когда оба соответствующих бита операндов равны 1. Другими словами, можно сказать, двоичные разряды получившегося числа — это результат умножения соответствующих битов операнда: 1х1 = 1, 1х0 = 0. Побитовому И соответствует следующая таблица истинности:

    Пример работы побитового И на выражении 38 & 53:

    A00100110
    B00110101
    A & B00100100

    Как результат, получаем 1001002 , или 3610 .

    Старт 10 февраля, 3 месяца, Онлайн, Беcплатно

    С помощью побитового оператора И можно проверить, является ли число четным или нечетным. Для целых чисел, если младший бит равен 1, то число нечетное (основываясь на преобразовании двоичных чисел в десятичные). Зачем это нужно, если можно просто использовать %2 ? На моем компьютере, например, &1 выполняется на 66% быстрее. Довольно неплохое повышение производительности, скажу я вам.

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

    Разница между исключающим ИЛИ и побитовым ИЛИ в том, что для получения 1 только один бит в паре может быть 1:

    Например, выражение 138^43 будет равно…

    A10001010
    B00101011
    A ^ B10100001

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

    Также с помощью исключающего ИЛИ можно зашифровать текст. Для этого нужно лишь итерировать через все символы, и ^ их с символом-ключом. Для более сложного шифра можно использовать строку символов:

    Исключающее ИЛИ не самый надежный способ шифровки, но его можно сделать частью шифровального алгоритма.

    Побитовое отрицание (NOT)

    Побитовое отрицание инвертирует все биты операнда. То есть, то что было 1 станет 0, и наоборот.

    Вот, например, операция

    Результатом будет 20310

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

    Дополнительный код

    Здесь мне стоит рассказать вам немного о способе представления отрицательных целых чисел в ЭВМ, а именно о дополнительном коде (two’s complement). Не вдаваясь в подробности, он нужен для облегчения арифметики двоичных чисел.

    Главное, что вам нужно знать о числах, записанных в дополнительном коде — это то, что старший разряд является знаковым. Если он равен 0, то число положительное и совпадает с представлением этого числа в прямом коде, а если 1 — то оно отрицательное. То есть, 10111101 — отрицательное число, а 01000011 — положительное.

    Чтобы преобразовать отрицательное число в дополнительный код, нужно инвертировать все биты числа (то есть, по сути, использовать побитовое отрицание) и добавить к результату 1.

    Например, если мы имеем 109:

    Представленным выше методом мы получаем -109 в дополнительном коде.
    Только что было представлено очень упрощенное объяснение дополнительного кода, и я настоятельно советую вам детальнее изучить эту тему.

    Побитовый сдвиг влево

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

    Побитовый сдвиг вправо

    Как вы могли догадаться, >> сдвигает биты операнда на обозначенное количество битов вправо.

    Если операнд положительный, то пустые места заполняются нулями. Если же изначально мы работаем с отрицательным числом, то все пустые места слева заполняются единицами. Это делается для сохранения знака в соответствии с дополнительным кодом, объясненным ранее.

    Так как побитовый сдвиг вправо — это операция, противоположная побитовому сдвигу влево, несложно догадаться, что сдвиг числа вправо на N количество позиций также делит это число на 2 N . Опять же, это выполняется намного быстрее обычного деления.

    Вывод

    Итак, теперь вы знаете больше о битовых операциях и не боитесь их. Могу предположить, что вы не будете использовать >>1 при каждом делении на 2. Тем не менее, битовые операции неплохо иметь в своем арсенале, и теперь вы сможете воспользоваться ими в случае надобности или же ответить на каверзный вопрос на собеседовании.

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

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

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

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

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

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

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

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

    2 в степениDECBIN
    010b00000001
    120b00000010
    240b00000100
    380b00001000
    4160b00010000
    5320b00100000
    6640b01000000
    71280b10000000

    Таким образом, степень двойки явно “указывает” на номер бита в байте, считая справа налево (примечание: в других архитектурах может быть иначе). Напомню, что абсолютно неважно, в какой системе исчисления вы работаете – микроконтроллеру всё равно и он во всём видит единицы и нули. Если “сложить” полный байт в десятичном представлении битов, то мы получим как раз 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

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

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

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

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

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

    Битовое И

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

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

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

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

    Битовое ИЛИ

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

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

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

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

    Битовое НЕ

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

    и просто инвертирует бит:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Как я уже говорил, битовые операции – самые быстрые. Если требуется максимальная скорость вычислений – их можно оптимизировать и подогнать под “степени двойки”, но иногда компилятор делает это сам, подробнее смотри в уроке про оптимизацию кода. Рассмотрим базовые операции:

    • Деление на 2^n – сдвиг вправо на n . Например, val / 8 можно записать как val >> 3 . Компилятор не оптимизирует деление самостоятельно, что позволяет ускорить данную операцию приблизительно в 15 раз при ручной оптимизации.
    • Умножение на 2^n – сдвиг влево на n . Например, val * 8 можно записать как val . Компилятор оптимизирует умножение самостоятельно, поэтому в ручной оптимизации нет смысла. Но можно встретить в чужих исходниках.
    • Остаток от деления на 2^n – битовая маска на n младших битов. Например, val % 8 можно записать как val & 0b111 . Компилятор оптимизирует такие операции самостоятельно, поэтому в ручной оптимизации нет смысла. Но можно встретить в чужих исходниках.

    Примечание: рассмотренные выше операции работают только с целочисленными типами данных!

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

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

    https://tproger.ru/translations/bitwise-operations/

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

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *

    Related Posts