Начнем с простого с побитовых операций чему равно 0011 or 0101
Урок №45. Побитовые операторы
Обновл. 11 Сен 2021 |
Побитовые операторы манипулируют отдельными битами в пределах переменной.
Примечание: Для некоторых этот материал может показаться сложным. Если вы застряли или что-то не понятно — пропустите этот урок (и следующий), в будущем сможете вернуться и разобраться детально. Он не столь важен для прогресса в изучении языка C++, как другие уроки, и изложен здесь в большей мере для общего развития.
Зачем нужны побитовые операторы?
В далеком прошлом компьютерной памяти было очень мало и ею сильно дорожили. Это было стимулом максимально разумно использовать каждый доступный бит. Например, в логическом типе данных bool есть всего лишь два возможных значения (true и false), которые могут быть представлены одним битом, но по факту занимают целый байт памяти! А это, в свою очередь, из-за того, что переменные используют уникальные адреса памяти, а они выделяются только в байтах. Переменная bool занимает 1 бит, а другие 7 бит — тратятся впустую.
Используя побитовые операторы, можно создавать функции, которые позволят уместить 8 значений типа bool в переменную размером 1 байт, что значительно сэкономит потребление памяти. В прошлом такой трюк был очень популярен. Но сегодня, по крайней мере, в прикладном программировании, это не так.
Теперь памяти стало существенно больше и программисты обнаружили, что лучше писать код так, чтобы было проще и понятнее его поддерживать, нежели усложнять его ради незначительной экономии памяти. Поэтому спрос на использование побитовых операторов несколько уменьшился, за исключением случаев, когда необходима уж максимальная оптимизация (например, научные программы, которые используют огромное количество данных; игры, где манипуляции с битами могут быть использованы для дополнительной скорости; встроенные программы, где память по-прежнему ограничена).
В языке С++ есть 6 побитовых операторов:
| Оператор | Символ | Пример | Операция |
| Побитовый сдвиг влево | > | x >> y | Все биты в x смещаются вправо на y бит |
| Побитовое НЕ | Все биты в x меняются на противоположные | ||
| Побитовое И | & | x & y | Каждый бит в x И каждый соответствующий ему бит в y |
| Побитовое ИЛИ | | | x | y | Каждый бит в x ИЛИ каждый соответствующий ему бит в y |
| Побитовое исключающее ИЛИ (XOR) | ^ | x ^ y | Каждый бит в x XOR с каждым соответствующим ему битом в y |
В побитовых операциях следует использовать только целочисленные типы данных 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
В третьем случае мы снова переместили бит за пределы литерала. Он также потерялся навсегда.
Хотя в примерах, приведенных выше, мы смещаем биты только в литералах, мы также можем смещать биты и в переменных:
O.2 – Побитовые операторы
Побитовые операторы
Для битовых манипуляций C++ предоставляет 6 операторов, часто называемых побитовыми операторами:
| Оператор | Обозначение | Пример использования | Операция |
|---|---|---|---|
| Сдвиг влево | x | Все биты в x сдвигаются влево на количество бит, представленное значением y | |
| Сдвиг вправо | >> | x >> y | Все биты в x сдвигаются вправо на количество бит, представленное значением y |
| Побитовое НЕ (NOT) | Все биты в x инвертируются | ||
| Побитовое И (AND) | & | x & y | Выполняется операция И каждого бита в x с каждым соответствующим битом в y |
| Побитовое ИЛИ (OR) | | | x | y | Выполняется операция ИЛИ каждого бита в x с каждым соответствующим битом в y |
| Побитовое исключающее ИЛИ (XOR) | ^ | x ^ y | Выполняется операция исключающее ИЛИ каждого бита в x с каждым соответствующим битом в y |
Примечание автора
В следующих примерах мы в основном будем работать с 4-битными двоичными значениями. Это сделано для удобства и простоты примеров. В реальных программах количество используемых битов зависит от размера объекта (например, 2-байтовый объект будет хранить 16 бит).
Для удобства чтения мы также опустим префикс 0b вне примеров кода (например, вместо 0b0101 мы будем писать просто 0101 ).
Операторы побитового сдвига влево ( ) и побитового сдвига вправо ( >> )
Оператор побитового сдвига влево ( ) сдвигает биты влево. Левый операнд – это выражение для сдвига битов, а правый операнд – это целое число, представляющее количество бит, на которое нужно выполнить сдвиг.
Обратите внимание, что в третьем случае мы вытеснили бит с левого конца числа! Биты, сдвинутые с конца двоичного числа, теряются навсегда.
Оператор побитового сдвига вправо ( >> ) сдвигает биты вправо.
Обратите внимание, что в третьем случае мы вытеснили бит с правого конца числа, поэтому он потерялся.
Вот пример выполнения побитового сдвига:
Эта программа напечатает:
Обратите внимание, что результаты применения операторов побитового сдвига к целому числу со знаком до C++20 зависели от компилятора.
Предупреждение
При использовании стандарта до C++20 не выполняйте сдвиг для значений целочисленных типов со знаком (и даже при новом стандарте, вероятно, всё же лучше использовать беззнаковые типы).
Что?! Разве operator и operator>> не используются для ввода и вывода?
Сегодняшние программы обычно не очень часто используют операторы побитового сдвига влево и вправо для сдвига битов. Скорее, у вас больше шансов увидеть оператор побитового сдвига влево, используемый с std::cout для вывода текста. Рассмотрим следующую программу:
Эта программа напечатает:
Обратите внимание, что если вы используете operator как для вывода, так и для сдвига влево, необходимо использовать скобки:
Эта программа печатает:
Мы поговорим больше о перегрузке операторов в следующем разделе, включая обсуждение того, как перегружать операторы для ваших собственных целей.
Побитовое НЕ (NOT)
Оператор побитовое НЕ (
), пожалуй, самый простой для понимания из всех побитовых операторов. Он просто инвертирует каждый бит с 0 на 1, или наоборот. Обратите внимание, что результат побитового НЕ зависит от размера вашего типа данных.
Инвертирование 4-битного значения:
Инвертирование 8-битного значения:
И в 4-битном, и в 8-битном случаях мы начинаем с одного и того же числа (двоичное 0100 соответствует 0000 0100 точно так же, как десятичное 7 соответствует 07), но в конечном итоге мы получаем другой результат.
Мы можем увидеть это в действии в следующей программе:
Эта программа напечатает:
Побитовое ИЛИ (OR)
Для выполнения (любых) побитовых операций проще всего выровнять два операнда следующим образом:
а затем применить операцию к каждому столбцу битов.
Если вы помните, логическое ИЛИ вычисляется как true (1), если левый, правый или оба операнда равны true (1), и 0 в противном случае. Побитовое ИЛИ вычисляется как 1, если левый, правый или оба бита равны 1, и 0 в противном случае. Следовательно, выражение вычисляется так:
Наш результат – 0111 в двоичном формате.
Эта программа напечатает:
А вот код для этого примера:
Эта программа напечатает:
Побитовое И (AND)
Эта программа напечатает:
Эта программа напечатает:
Побитовое исключающее ИЛИ (XOR)
Последний оператор – это побитовое исключающее ИЛИ ( ^ ), также известное как XOR.
Побитовые операторы присваивания
Подобно арифметическим операторам присваивания, C++, чтобы упростить изменение переменных, предоставляет побитовые операторы присваивания.
| Оператор | Обозначение | Пример использования | Операция |
|---|---|---|---|
| Присваивание со сдвигом влево | x | Сдвигает x влево на количество бит, представленное значением y | |
| Присваивание со сдвигом вправо | >>= | x >>= y | Сдвигает x вправо на количество бит, представленное значением y |
| Присваивание с побитовым И (AND) | &= | x &= y | Присваивает результат выполнения x & y переменной x |
| Присваивание с побитовым ИЛИ (OR) | |= | x |= y | Присваивает результат выполнения x | y переменной x |
| Присваивание с побитовым исключающее ИЛИ (XOR) | ^= | x ^= y | Присваивает результат выполнения x ^ y переменной x |
Эта программа напечатает:
Резюме
Обобщая, как вычислять побитовые операции с использованием метода «в столбик»:
В следующем уроке мы рассмотрим, как для облегчения битовых манипуляций эти операторы могут использоваться в сочетании с битовыми масками.
Небольшой тест
Вопрос 1
a) Что дает выражение 0110 >> 2 в двоичном формате?
0110 >> 2 вычисляется как 0001
Вопрос 2
Должен выполняться следующий код:
и печататься следующее:
Вопрос 3
Битовые операции
Логические битовые (побитовые) операции
Битовые операции сдвига
В распространённых языках программирования встроенными средствами реализуются только четыре побитовые (битовые) логические операции : И, ИЛИ, НЕ и исключающее ИЛИ. Для задания произвольной побитовой логической операции вполне достаточно перечисленных операций.
И еще, регистр общего назначения (R0. R31) я буду обозначать аббревиатурой РОН.
Битовые (побитовые) логические операции
Битовая операция НЕ:
Если бит равен «1», то после выполнения операции он будет равен «0». И наоборот, если бит равен «0», то после выполнения операции он будет равен «1». (операция выполняется одновременно над всеми битами РОН). В качестве операнда может использоваться только РОН
Обозначается знаком «
Дополнительный код, как и прямой и обратный коды — наиболее распространённые способы представления десятичных чисел в двоичном коде. Это вопрос будет рассмотрен в отдельной статье.
Битовая операция И:
Если оба соответствующих бита операндов равны 1, результирующий двоичный разряд равен 1; если же хотя бы один бит из пары равен 0, результирующий двоичный разряд равен 0. В качестве операндов могут использоваться два РОН или РОН и константа (число, записанное в памяти МК)
Обозначается знаком «&»
Практическое применение:
— для сброса конкретного бита (битов) в ноль:
— для проверки бита на 0 или 1, оно же чтение конкретного бита (если результат равен 0, значит бит равен 0, иначе бит равен 1):
Битовая операция ИЛИ
Если оба соответствующих бита операндов равны 0, двоичный разряд результата равен 0; если же хотя бы один бит из пары равен 1, двоичный разряд результата равен 1. В качестве операндов могут использоваться два РОН или РОН и константа
Обозначается знаком «|» (вертикальная палочка)
Битовая операция ИСКЛЮЧАЮЩЕЕ ИЛИ
Результат действия выполнения операции равен 1, если число складываемых единичных битов нечётно и равен 0, если чётно. В качестве операндов могут использоваться только РОН
Обозначается знаком «^»
Практическое применение:
— для инвертирования битов регистра по маске
Битовые операции сдвига
Логический сдвиг влево
При логическом сдвиге влево происходит сдвиг всех разрядов регистра влево на одну позицию, старший бит (самый левый) при этом теряется, а в младший (самый правый) записывается 0.
Обозначается знаком «
Логический сдвиг вправо
При логическом сдвиге вправо происходит сдвиг всех разрядов регистра вправо на одну позицию, младший бит (самый правый) при этом теряется, а в старший (самый левый) записывается 0
Обозначается знаком «>>»
Логический сдвиг вправо используется как арифметическая операция для целочисленного деления на 2.
(29 голосов, оценка: 4,97 из 5)
О битовых операциях
В этой статье я расскажу вам о том, как работают битовые операции. С первого взгляда они могут показаться вам чем-то сложным и бесполезным, но на самом деле это совсем не так. В этом я и попытаюсь вас убедить.
Введение
Побитовые операторы проводят операции непосредственно на битах числа, поэтому числа в примерах будут в двоичной системе счисления.
Я расскажу о следующих побитовых операторах:
Битовые операции изучаются в дискретной математике, а также лежат в основе цифровой техники, так как на них основана логика работы логических вентилей — базовых элементов цифровых схем. В дискретной математике, как и в цифровой технике, для описания их работы используются таблицы истинности. Таблицы истинности, как мне кажется, значительно облегчают понимание битовых операций, поэтому я приведу их в этой статье. Их, тем не менее, почти не используют в объяснениях побитовых операторов высокоуровневых языков программирования.
О битовых операторах вам также необходимо знать:
Побитовое ИЛИ (OR)
Побитовое ИЛИ действует эквивалентно логическому ИЛИ, но примененному к каждой паре битов двоичного числа. Двоичный разряд результата равен 0 только тогда, когда оба соответствующих бита в равны 0. Во всех других случаях двоичный результат равен 1. То есть, если у нас есть следующая таблица истинности:
38 | 53 будет таким:
| A | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| B | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| A | B | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
Побитовое И (AND)
Побитовое И — это что-то вроде операции, противоположной побитовому ИЛИ. Двоичный разряд результата равен 1 только тогда, когда оба соответствующих бита операндов равны 1. Другими словами, можно сказать, двоичные разряды получившегося числа — это результат умножения соответствующих битов операнда: 1х1 = 1, 1х0 = 0. Побитовому И соответствует следующая таблица истинности:
Пример работы побитового И на выражении 38 & 53:
| A | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| B | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| A & B | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
Исключающее ИЛИ (XOR)
Разница между исключающим ИЛИ и побитовым ИЛИ в том, что для получения 1 только один бит в паре может быть 1:
Например, выражение 138^43 будет равно…
| A | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| B | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| A ^ B | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
С помощью ^ можно поменять значения двух переменных (имеющих одинаковый тип данных) без использования временной переменной.
Также с помощью исключающего ИЛИ можно зашифровать текст. Для этого нужно лишь итерировать через все символы, и ^ их с символом-ключом. Для более сложного шифра можно использовать строку символов:
Исключающее ИЛИ не самый надежный способ шифровки, но его можно сделать частью шифровального алгоритма.
Побитовое отрицание (NOT)
Побитовое отрицание инвертирует все биты операнда. То есть, то что было 1 станет 0, и наоборот.
Вот, например, операция
Результатом будет 20310
При использовании побитового отрицания знак результата всегда будет противоположен знаку исходного числа (при работе со знаковыми числами). Почему так происходит, узнаете прямо сейчас.
Дополнительный код
Здесь мне стоит рассказать вам немного о способе представления отрицательных целых чисел в ЭВМ, а именно о дополнительном коде (two’s complement). Не вдаваясь в подробности, он нужен для облегчения арифметики двоичных чисел.
Главное, что вам нужно знать о числах, записанных в дополнительном коде — это то, что старший разряд является знаковым. Если он равен 0, то число положительное и совпадает с представлением этого числа в прямом коде, а если 1 — то оно отрицательное. То есть, 10111101 — отрицательное число, а 01000011 — положительное.
Чтобы преобразовать отрицательное число в дополнительный код, нужно инвертировать все биты числа (то есть, по сути, использовать побитовое отрицание) и добавить к результату 1.
Например, если мы имеем 109:
| A | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
A+1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
Побитовый сдвиг влево
Побитовые сдвиги немного отличаются от рассмотренных ранее битовых операций. Побитовый сдвиг влево сдвигает биты своего операнда на N количество битов влево, начиная с младшего бита. Пустые места после сдвига заполняются нулями. Происходит это так:
Побитовый сдвиг вправо
Как вы могли догадаться, >> сдвигает биты операнда на обозначенное количество битов вправо.
Если операнд положительный, то пустые места заполняются нулями. Если же изначально мы работаем с отрицательным числом, то все пустые места слева заполняются единицами. Это делается для сохранения знака в соответствии с дополнительным кодом, объясненным ранее.
Вывод
Итак, теперь вы знаете больше о битовых операциях и не боитесь их. Могу предположить, что вы не будете использовать >>1 при каждом делении на 2. Тем не менее, битовые операции неплохо иметь в своем арсенале, и теперь вы сможете воспользоваться ими в случае надобности или же ответить на каверзный вопрос на собеседовании.