Что такое побитовое или

Урок №45. Побитовые операторы

Обновл. 11 Сен 2021 |

Побитовые операторы манипулируют отдельными битами в пределах переменной.

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

Зачем нужны побитовые операторы?

В далеком прошлом компьютерной памяти было очень мало и ею сильно дорожили. Это было стимулом максимально разумно использовать каждый доступный бит. Например, в логическом типе данных bool есть всего лишь два возможных значения (true и false), которые могут быть представлены одним битом, но по факту занимают целый байт памяти! А это, в свою очередь, из-за того, что переменные используют уникальные адреса памяти, а они выделяются только в байтах. Переменная bool занимает 1 бит, а другие 7 бит — тратятся впустую.

Используя побитовые операторы, можно создавать функции, которые позволят уместить 8 значений типа bool в переменную размером 1 байт, что значительно сэкономит потребление памяти. В прошлом такой трюк был очень популярен. Но сегодня, по крайней мере, в прикладном программировании, это не так.

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

В языке С++ есть 6 побитовых операторов:

x

В побитовых операциях следует использовать только целочисленные типы данных unsigned, так как C++ не всегда гарантирует корректную работу побитовых операторов с целочисленными типами signed.

Правило: При работе с побитовыми операторами используйте целочисленные типы данных unsigned.

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

В языке C++ количество используемых бит основывается на размере типа данных (в 1 байте находятся 8 бит). Оператор побитового сдвига влево ( ) сдвигает биты влево. Левый операнд является выражением, в котором они сдвигаются, а правый — количество мест, на которые нужно сдвинуть. Поэтому в выражении 3 мы имеем в виду «сдвинуть биты влево в литерале 3 на одно место».

Примечание: В следующих примерах мы будем работать с 4-битными двоичными значениями.

Рассмотрим число 3, которое в двоичной системе равно 0011:

В последнем третьем случае один бит перемещается за пределы самого литерала! Биты, сдвинутые за пределы двоичного числа, теряются навсегда.

Оператор побитового сдвига вправо ( >> ) сдвигает биты вправо. Например:

12 = 1100
12 >> 1 = 0110 = 6
12 >> 2 = 0011 = 3
12 >> 3 = 0001 = 1

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

Хотя в примерах, приведенных выше, мы смещаем биты только в литералах, мы также можем смещать биты и в переменных:

Источник

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

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

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

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

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

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

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

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

Переходим к более сложным вещам. На самом деле они максимально просты для микроконтроллера, настолько просты, что выполняются за один такт. При частоте 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, остальные биты не трогали.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ещё интересный пример сжатия

Таким образом мы отбросили у красного и синего младшие (правые) биты, в этом и заключается сжатие. Чем больше битов отброшено – тем менее точно получится “разжать” число. Например сжимали число 0b10101010 (170 в десятичной) на три бита, при сжатии получили 0b10101000, т.е. потеряли три младших бита, и в десятичной уже получится 168. Для упаковки используется битовый сдвиг и маска, таким образом мы берём первые пять битов красного, шесть зелёного и пять синего, и задвигаем на нужные места в результирующей 16-битной переменной. Всё, цвет сжат и его можно хранить. Для распаковки используется обратная операция: выбираем при помощи маски нужные биты и сдвигаем их обратно в байт:

Как и в примере со светодиодами, мы просто брали нужные биты ( в этом случае младшие два, 0b11 ) и сдвигали их на нужное расстояние. Для распаковки делаем в обратном порядке:

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

Ну и теперь, проследив закономерность, можно сделать для себя функцию или макрос чтения пакета:

Где x это пакет, а y – порядковый номер запакованного значения. Выведем посмотрим:

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

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

Перемотка бита

Целые

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

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

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

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

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

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

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

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

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

Деление на 2

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

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

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

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

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

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

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

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

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

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

Смена знака

Вернёт 2 n

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

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

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

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

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

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

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

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

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

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

n + 1

n – 1

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

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

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

Different rightmost bit of numbers m & n

Common rightmost bit of numbers m & n

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

Примечание: хаки с float могут не работать на Ардуино! Разбить float в массив бит (unsigned uint32_t)

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

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

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

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

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

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

Строки

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

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

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

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

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

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

Другое

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

Приоритет операций

Чтобы не плодить скобки, нужно знать приоритет операций. В C++ он такой:

Источник

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

Авторизуйтесь

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результатом будет 203₁₀

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

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

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

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

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

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

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

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

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

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

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

Вывод

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

Источник