Побитовые операторы манипулируют отдельными битами в пределах переменной.
Примечание: Для некоторых этот материал может показаться сложным. Если вы застряли или что-то не понятно — пропустите этот урок (и следующий), в будущем сможете вернуться и разобраться детально. Он не столь важен для прогресса в изучении языка C++, как другие уроки, и изложен здесь в большей мере для общего развития.
Зачем нужны побитовые операторы?
В далеком прошлом компьютерной памяти было очень мало и ею сильно дорожили. Это было стимулом максимально разумно использовать каждый доступный бит. Например, в логическом типе данных bool есть всего лишь два возможных значения (true и false), которые могут быть представлены одним битом, но по факту занимают целый байт памяти! А это, в свою очередь, из-за того, что переменные используют уникальные адреса памяти, а они выделяются только в байтах. Переменная bool занимает 1 бит, а другие 7 бит — тратятся впустую.
Используя побитовые операторы, можно создавать функции, которые позволят уместить 8 значений типа bool в переменную размером 1 байт, что значительно сэкономит потребление памяти. В прошлом такой трюк был очень популярен. Но сегодня, по крайней мере, в прикладном программировании, это не так.
Теперь памяти стало существенно больше и программисты обнаружили, что лучше писать код так, чтобы было проще и понятнее его поддерживать, нежели усложнять его ради незначительной экономии памяти. Поэтому спрос на использование побитовых операторов несколько уменьшился, за исключением случаев, когда необходима уж максимальная оптимизация (например, научные программы, которые используют огромное количество данных; игры, где манипуляции с битами могут быть использованы для дополнительной скорости; встроенные программы, где память по-прежнему ограничена).
В языке С++ есть 6 побитовых операторов:
Оператор
Символ
Пример
Операция
Побитовый сдвиг влево
>
x >> y
Все биты в x смещаются вправо на y бит
Побитовое НЕ
x
Все биты в 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:
В последнем третьем случае один бит перемещается за пределы самого литерала! Биты, сдвинутые за пределы двоичного числа, теряются навсегда.
Булевы операции очень близки (хотя и не тождественны) логическим связкам в классической логике. Бит можно рассматривать как логическое суждение — его значениями являются 1 «истина» и 0 «ложь». При такой интерпретации известные в логике связки конъюнкции, дизъюнкции, импликации, отрицания и другие имеют представление на языке битов. И наоборот, битовые операции легко описываются на языке исчисления высказываний.
Однако, связкам математической логики более соответствуют логические операции в т.ч. в программировании, нежели собственно битовые операции.
Булевы операции как основа цифровой техники
Перечисление битовых операций
«(Логическое) И» (and) — аналог конъюнкции в логике. Иногда называется логическим умножением.
В булевой логике:
В языке C: &
Выдаёт 1 если оба входа равны 1, в противном случае 0. Если один из аргументов равен 1, то результат «И» равен другому. Если один из аргументов равен 0, то результат «И» равен 0 независимо от значения другого аргумента.
«(Логическое) НЕ» (not), инвертирование — аналог отрицания в логике.
В булевой логике:
В языке C:
Данная унарная операция (с одним входом) заменяет 0 на 1 и наоборот. Реализующий её элемент называется инвертором.
«(Логическое) ИЛИ» (or) — аналог дизъюнкции в логике.
В булевой логике:
В языке C: |
Выдаёт 1 если и только если хотя бы один из входов равен 1. Операция, двойственная AND: при инвертировании выхода и всех входов (т.е. при замене 0 и 1 местами) «И» и «ИЛИ» взаимно превращается друг в друга.
Исключающее ИЛИ
«Исключающее ИЛИ» (xor), «сложение по модулю 2» — аналог исключающего ИЛИ в логике.
В булевой логике:
В языке C: ^
Если один из аргументов равен 0, то результат равен другому. Если один из аргументов равен 1, то результат равен отрицанию другого аргумента. Первое русское название операции обусловлено тем, что результат данной операции отличается от результата «ИЛИ» только в одном случае из 4 случаев входа — обоих 1 (случай одновременной истинности аргументов «исключается»). Ещё в русской грамматике значение данной логической связки передаётся союзом «либо».
Второе название — тем, что действительно является сложением в кольце вычетов по модулю 2, из чего следуют некоторые интересные свойства. Например, в отличие от вышеописанных «И» и «ИЛИ» данная операция является обратимой, или инволютивной: .
Операции от многих аргументов
Операции «И», «ИЛИ» и «исключающее ИЛИ» являются не только коммутативными, но и ассоциативными, и потому легко обобщаются на случай нескольких аргументов (входов).
Прочие бинарные операции
«ИЛИ-НЕ» (nor), она же «стрелка Пирса».
Стрелка Пирса является результатом инвертирования результата «ИЛИ» своих аргументов, выдаёт значение 1 только когда оба входа 0.
«И-НЕ» (nand), она же «штрих Шеффера».
В булевой логике:
Импликация («если-то») — аналог импликации в логике.
В булевой логике:
Совпадает с «ИЛИ» с инвертированным первым аргументом, выдаёт значение 0 только когда первый вход 1 а второй — 0. Данная операция не является коммутативной, в отличие от всех вышеописанных бинарных операций. Её можно понимать как арифметическое (меньше или равно).
Эквиваленция. Выдаёт 1 если и только если оба аргумента равны между собой. Является результатом инвертирования результата «исключающего ИЛИ» своих аргументов. Она же и двойственна исключающему «ИЛИ» в вышеописанном смысле.
Сводная таблица истинности булевых операций
Название
И/AND
НЕ/NOT
ИЛИ/OR
искл. ИЛИ/XOR
импл.
стрелка Пирса
штрих Шеффера
x
y
& ()
x ()
| ()
^ ()
()
0
0
0
1
0
0
1
1
1
0
1
0
1
1
1
1
0
1
1
0
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
0
Операции над битовыми векторами
Обобщение операций на булеву алгебру
Битовые сдвиги
К битовым операциям также относят битовые сдвиги. При сдвиге значения битов копируются в соседние по направлению сдвига. Различают несколько видов сдвигов — логический, арифметический и циклический, в зависимости от обработки крайних битов.
Также различают сдвиг влево (в направлении от младшего бита к старшему) и вправо (в направлении от старшего бита к младшему).
Арифметический сдвиг (правый)
Циклический сдвиг через перенос
Логический сдвиг
При логическом сдвиге значение последнего бита по направлению сдвига теряется (копируясь в бит переноса), а первый приобретает нулевое значение.
Логические сдвиги влево и вправо используются для быстрого умножения и деления на 2, соответственно.
Арифметический сдвиг
Арифметический сдвиг аналогичен логическому, но значение слова считается знаковым числом представленному дополнительным кодом. Так при правом сдвиге старший бит сохраняет свое значение. Левый арифметический сдвиг идентичен логическому.
Циклический сдвиг
При циклическом сдвиге, значение последнего бита по направлению сдвига копируется в первый бит (и копируется в бит переноса).
Также различают циклический сдвиг через бит переноса — при нем первый бит по направлению сдвига получает значение из бита переноса, а значение последнего бита сдвигается в бит переноса.
2-адическая интерпретация
Целое число, записанное (в дополнительном коде) в бесконечный (в сторону положительных степеней двойки) двоичный регистр является естественным объектом для теории p-адических чисел при . Множество целых 2-адических чисел (т.е. произвольных бесконечных битовых последовательностей) может быть рассмотрено как булева алгебра точно так же как и множество значений битового регистра конечной длины. Все вышеперечисленные битовые операции оказываются непрерывными отображениями. Хотя практическое программирование не располагает регистрами бесконечной длины, это не мешает использовать данный теоретический факт в криптографии для создания быстродействующих алгоритмов шифрования.
Практические применения
Физическая реализация битовых операций
В квантовых вычислениях из перечисленных булевых операций реализуются только НЕ и искл. ИЛИ (с некоторыми оговорками). Квантовых аналогов И, ИЛИ и т.д. не существует.
Схемы аппаратной логики
Результат операции ИЛИ-НЕ или ИЛИ ото всех битов двоичного регистра проверяет, равно ли значение регистра нулю; то же самое взятое от выхода искл. ИЛИ двух регистров проверяет равенство их значений между собой.
Использование в программировании
Регистровая операция И используется для сброса конкретного бита, ИЛИ — для установки, искл. ИЛИ — для инвертирования (т.е. для проведения операции НЕ над конкретным битом с сохранением остальных нетронутыми). Регистровый И с последующей проверкой равенства нулю используется для чтения значения конкретного бита.
Операция И также используется для наложения маски — например, в IP-адресации (хотя не только).
В этой статье я расскажу вам о том, как работают битовые операции. С первого взгляда они могут показаться вам чем-то сложным и бесполезным, но на самом деле это совсем не так. В этом я и попытаюсь вас убедить.
Введение
Побитовые операторы проводят операции непосредственно на битах числа, поэтому числа в примерах будут в двоичной системе счисления.
Я расскажу о следующих побитовых операторах:
Битовые операции изучаются в дискретной математике, а также лежат в основе цифровой техники, так как на них основана логика работы логических вентилей — базовых элементов цифровых схем. В дискретной математике, как и в цифровой технике, для описания их работы используются таблицы истинности. Таблицы истинности, как мне кажется, значительно облегчают понимание битовых операций, поэтому я приведу их в этой статье. Их, тем не менее, почти не используют в объяснениях побитовых операторов высокоуровневых языков программирования.
О битовых операторах вам также необходимо знать:
Побитовое ИЛИ (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. Тем не менее, битовые операции неплохо иметь в своем арсенале, и теперь вы сможете воспользоваться ими в случае надобности или же ответить на каверзный вопрос на собеседовании.
Логические битовые (побитовые) операции Битовые операции сдвига
В распространённых языках программирования встроенными средствами реализуются только четыре побитовые (битовые) логические операции : И, ИЛИ, НЕ и исключающее ИЛИ. Для задания произвольной побитовой логической операции вполне достаточно перечисленных операций.
И еще, регистр общего назначения (R0. R31) я буду обозначать аббревиатурой РОН.
Битовые (побитовые) логические операции
Битовая операция НЕ:
Если бит равен «1», то после выполнения операции он будет равен «0». И наоборот, если бит равен «0», то после выполнения операции он будет равен «1». (операция выполняется одновременно над всеми битами РОН). В качестве операнда может использоваться только РОН
Обозначается знаком «
Дополнительный код, как и прямой и обратный коды — наиболее распространённые способы представления десятичных чисел в двоичном коде. Это вопрос будет рассмотрен в отдельной статье.
Битовая операция И:
Если оба соответствующих бита операндов равны 1, результирующий двоичный разряд равен 1; если же хотя бы один бит из пары равен 0, результирующий двоичный разряд равен 0. В качестве операндов могут использоваться два РОН или РОН и константа (число, записанное в памяти МК)
Обозначается знаком «&»
Практическое применение: — для сброса конкретного бита (битов) в ноль:
— для проверки бита на 0 или 1, оно же чтение конкретного бита (если результат равен 0, значит бит равен 0, иначе бит равен 1):
Битовая операция ИЛИ
Если оба соответствующих бита операндов равны 0, двоичный разряд результата равен 0; если же хотя бы один бит из пары равен 1, двоичный разряд результата равен 1. В качестве операндов могут использоваться два РОН или РОН и константа
Обозначается знаком «|» (вертикальная палочка)
Битовая операция ИСКЛЮЧАЮЩЕЕ ИЛИ
Результат действия выполнения операции равен 1, если число складываемых единичных битов нечётно и равен 0, если чётно. В качестве операндов могут использоваться только РОН
Обозначается знаком «^»
Практическое применение: — для инвертирования битов регистра по маске
Битовые операции сдвига
Логический сдвиг влево
При логическом сдвиге влево происходит сдвиг всех разрядов регистра влево на одну позицию, старший бит (самый левый) при этом теряется, а в младший (самый правый) записывается 0.
Обозначается знаком «
Логический сдвиг вправо
При логическом сдвиге вправо происходит сдвиг всех разрядов регистра вправо на одну позицию, младший бит (самый правый) при этом теряется, а в старший (самый левый) записывается 0
Обозначается знаком «>>»
Логический сдвиг вправо используется как арифметическая операция для целочисленного деления на 2.
