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

Введение

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

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

• | (Побитовое ИЛИ (OR)),
• & (Побитовое И (AND)),
• ^ (Исключающее ИЛИ (XOR)),
• ~ (Побитовое отрицание (NOT)),
• << (Побитовый сдвиг влево),
• >> (Побитовый сдвиг вправо).

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

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

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

Побитовое ИЛИ (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

В итоге мы получаем 110111 2 , или 55 10 .

Побитовое И (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

Как результат, получаем 100100 2 , или 36 10 .

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

Исключающее ИЛИ (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

… 10100001 2 , или 160 10

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

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

String msg = "This is a message"; char message = msg.toCharArray(); String key = ".*)"; String encryptedString = new String(); for(int i = 0; i< message.length; i++){ encryptedString += message[i]^key.toCharArray(); }

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

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

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

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

A	0	0	1	1	0	1	0	0
~A	1	1	0	0	1	0	1	1

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

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

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

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

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

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

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

A	0	1	1	0	1	1	0	1
~A	1	0	0	1	0	0	1	0
~A+1	1	0	0	1	0	0	1	1

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

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

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

A	1	0	1	1	0	1	0	0
A<<2	1	1	0	1	0	0	0	0

Интересной особенностью сдвига влево на N позиций является то, что это эквивалентно умножению числа на 2 N . Таким образом, 43<<4 == 43*Math.pow(2,4) . Использование сдвига влево вместо Math.pow обеспечит неплохой прирост производительности.

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

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

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

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

Вывод

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

Команда XOR в Ассемблере выполняет операцию исключающего ИЛИ между всеми битами двух операндов. Результат операции XOR записывается в первый операнд. Синтаксис:

XOR ПРИЁМНИК, ИСТОЧНИК

Инструкция XOR всегда сбрасывает CF и OF, а также (в зависимости от результата) изменяет флаги SF, ZF и PF. Значение флага AF может быть любым - оно не зависит от результата операции.

ПРИЁМНИК может быть одним из следующих:

• Область памяти (MEM)

ИСТОЧНИК может быть одним из следующих:

• Область памяти (MEM)
• Регистр общего назначения (REG)
• Непосредственное значение - константа (IMM)

С учётом ограничений, которые были описаны выше, комбинации ПРИЁМНИК-ИСТОЧНИК могут быть следующими:

REG, MEM MEM, REG REG, REG MEM, IMM REG, IMM

Операция исключающего ИЛИ

При выполнении операции исключающего ИЛИ значение результата будет равно 1, если сравниваемые биты отличаются (не равны). Если же сравниваемые биты имеют одинаковое значение, то результат будет равен 0.

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

Но, так как любая пара неодинаковых битов это 0 и 1, то операция логического ИЛИ в результате даст 1.

Таблица истинности исключающего ИЛИ

Таблица истинности XOR приведена ниже:

0 XOR 0 = 0 0 XOR 1 = 1 1 XOR 0 = 1 1 XOR 1 = 0

Особенности операции XOR

Операция XOR обладает свойством реверсивности. Если её выполнить дважды с одним и тем же операндом, то значение результата инвертируется. То есть если два раза выполнить эту операцию между битами X и Y , то в конечном результате мы получим исходное значение бита Х .

0 XOR 0 = 0 XOR 0 = 0 0 XOR 1 = 1 XOR 1 = 0 1 XOR 0 = 1 XOR 0 = 1 1 XOR 1 = 0 XOR 1 = 1

Это свойство можно использовать, например, для простейшего шифрования данных (об этом как-нибудь в другой раз).

Проверка флага чётности после операции XOR

Команда XOR работает с 8-, 16- и 32-разрядными операциями.

Иногда есть необходимость после выполнения операции проверить флаг чётности PF, для того, чтобы узнать, какое количество единичных битов (чётное или нечётное) содержится в младшем байте результата (это бывает необходимо не только в случае выполнения операции XOR, но и при выполнении других арифметических и логических операций).

Если флаг чётности установлен, то в результате получилось чётное количество единичных битов. Иначе флаг будет сброшен.

Можно также просто проверить на чётность любое число, не меняя значения результата. Для этого надо выполнить команду XOR с нулевым значением. То есть в ПРИЁМНИКЕ должно быть проверяемое число, а в ИСТОЧНИКЕ должен быть ноль. А затем надо проверить флаг чётности. Пример:

AL, 10110101b ;Поместить в AL число с нечётным;количеством единичных битов (5) XOR AL, 0 ;При этом флаг чётности PF не;устанавливается (PO) MOV AL, 10110111b ;Поместить в AL число с чётным;количеством единичных битов (6) XOR AL, 0 ;При этом флаг чётности PF ;будет установлен (PE)

В отладчиках обычно для обозначения чётного количества единиц в полученном результате используется сокращение PE (Parity Even), а для нечётного - PO (Parity Odd).

Чётность в 16-разрядных словах

Как уже было сказано, флаг чётности устанавливается в зависимости от количества единиц, содержащихся в младшем байте результата. Чтобы проверить чётность 16-разрядного операнда, надо выполнить команду XOR между старшим и младшим байтом этого числа:

MOV AX, 64C1h ;0110 0100 1100 0001 - 6 единичных битов XOR AH, AL ;Флаг чётности будет установлен

Таким нехитрым способом 16-разрядный операнд разбивается на два байта (2 группы по 8 битов), и при выполнении команды XOR единичные биты, находящиеся в соответствующих разрядах двух 8-разрядных операндов, не будут учитываться. Потому что соответствующий бит результата равен нулю.

Команда XOR удаляет из результата любые пересекающиеся единичные биты двух 8-разрядных операндов и добавляет в результат непересекающиеся единичные биты. То есть чётность полученного нами 8-разрядного числа будет такой же, как и чётность исходного 16-разрядного числа.

0110 0100 1100 0001 - исходное 16-разрядное число 0 XOR 1 = 1 1 XOR 1 = 0 1 XOR 0 = 1 0 XOR 0 = 0 0 XOR 0 = 0 1 XOR 0 = 1 0 XOR 0 = 0 0 XOR 1 = 1

В результате 4 единицы, то есть флаг PF будет установлен

Чётность в 32-разрядных двойных словах

Ну а если надо определить чётность в 32-разрядном числе?

Тогда число разбивается на четыре байта, и поочерёдно с этими байтами выполняется операция исключающего ИЛИ.

Например, мы разбили 32-разрядное число B на четыре байта B0 , B1 , B2 , B3 , где В0 - это младший байт.

Тогда для определения чётности числа В нам надо будет использовать следующую формулу:

B0 XOR B1 XOR B2 XOR B3

Но в ассемблере такая запись недопустима. Поэтому придётся немного подумать.

Ну и напоследок о происхождении мнемоники XOR . В английском языке есть слово eX ception - исключение. Сокращением от этого слова является буква Х (так повелось). Вы наверняка встречали такое в рекламе или в названии продуктов, производители которых претендуют (ну или думают, что претендуют) на исключительность. Например, Лада XRAY, Sony XPeria и т.п. Так что XOR - это аббревиатура, собранная из двух слов - eX ception OR - исключающее ИЛИ.

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

Вход 1	Вход 2	Выход
0	0	0
0	1	1
1	0	1
1	1	0

Рис. 4.1.

Под функцией Исключающее ИЛИ понимается следующее: единица на выходе появляется тогда, когда только на одном входе присутствует единица . Если единиц на входах две или больше, или если на всех входах нули, то на выходе будет нуль. Таблица истинности двухвходового элемента Исключающее ИЛИ приведена в табл. 4.1. Обозначения, принятые в отечественных и зарубежных схемах, показаны на рис. 4.1. Надпись на отечественном обозначении элемента Исключающее ИЛИ "=1" как раз и обозначает, что выделяется ситуация, когда на входах одна и только одна единица .

Элементов Исключающее ИЛИ в стандартных сериях немного. Отечественные серии предлагают микросхемы ЛП5 (четыре двухвходовых элемента с выходом 2С), ЛЛ3 и ЛП12, отличающиеся от ЛП5 выходом ОК. Слишком уж специфическая функция реализуется этими элементами.

С точки зрения математики, элемент Исключающее ИЛИ выполняет операцию так называемого суммирования по модулю 2. Поэтому эти элементы также называются сумматорами по модулю два. Как уже отмечалось в предыдущей лекции, обозначается суммирование по модулю 2 знаком плюса, заключенного в кружок.

Основное применение элементов Исключающее ИЛИ, прямо следующее из таблицы истинности , состоит в сравнении двух входных сигналов. В случае, когда на входы приходят две единицы или два нуля (сигналы совпадают), на выходе формируется нуль (см. табл. 4.1) . Обычно при таком применении на один вход элемента подается постоянный уровень, с которым сравнивается изменяющийся во времени сигнал, приходящий на другой вход. Но значительно чаще для сравнения сигналов и кодов применяются специальные микросхемы компараторов кодов , которые будут рассмотрены в следующей лекции.

В качестве сумматора по модулю 2 элемент Исключающее ИЛИ используется также в параллельных и последовательных делителях по модулю 2, служащих для вычисления циклических контрольных сумм. Но подробно эти схемы будут рассмотрены в лекциях 14,15.

Важное применение элементов Исключающее ИЛИ - это управляемый инвертор (рис. 4.2) . В этом случае один из входов элемента используется в качестве управляющего, а на другой вход элемента поступает информационный сигнал. Если на управляющем входе единица , то входной сигнал инвертируется, если же нуль - не инвертируется. Чаще всего управляющий сигнал задается постоянным уровнем, определяя режим работы элемента, а информационный сигнал является импульсным. То есть элемент Исключающее ИЛИ может изменять полярность входного сигнала или фронта, а может и не изменять в зависимости от управляющего сигнала .

Рис. 4.2.

В случае, когда имеется два сигнала одинаковой полярности (положительные или отрицательные), и при этом их одновременный приход исключается, элемент Исключающее ИЛИ может быть использован для смешивания этих сигналов (рис. 4.3) . При любой полярности входных сигналов выходные сигналы элемента будут положительными. При положительных входных сигналах элемент Исключающее ИЛИ будет работать как элемент 2ИЛИ, а при отрицательных он будет заменять элемент 2И-НЕ. Такие замены могут быть полезны в тех случаях, когда в схеме остаются неиспользованными некоторые элементы Исключающее ИЛИ. Правда, при этом надо учитывать, что задержка распространения сигнала в элементе Исключающее ИЛИ обычно несколько больше (примерно в 1,5 раза), чем задержка в простейших элементах И, И-НЕ, ИЛИ, ИЛИ-НЕ.

Бит — это минимальная единица измерения объёма информации, так как она хранит одно из двух значений — 0 (False) или 1 (True). False и True в переводе на русский ложь и истина соответственно. То есть одна битовая ячейка может находиться одновременно лишь в одном состоянии из возможных двух. Напомню, два возможных состояния битовой ячейки равны — 1 и 0.
Есть определённые операции, для манипуляций с битами. Эти операции называются логическими или булевыми операциями, названные в честь одного из математиков — Джорджа Буля (1815-1864), который способствовал развитию этой области науки.
Все эти операции могут быть применены к любому биту, независимо от того, какое он имеет значение — 0(нуль) или 1(единицу). Ниже приведены основные логические операции и примеры их использования.

Логическая операция И (AND)

Обозначение AND: &

Логическая операция И выполняется с двумя битами, назовем их a и b. Результат выполнения логической операции И будет равен 1, если a и b равны 1, а во всех остальных (других) случаях, результат будет равен 0. Смотрим таблицу истинности логической операции and.

a(бит 1)	b(бит 2)	a(бит 1) & b(бит 2)
0	0	0
0	1	0
1	0	0
1	1	1

Логическая операция ИЛИ (OR)

Обозначение OR: |

Логическая операция ИЛИ выполняется с двумя битами (a и b). Результат выполнения логической операции ИЛИ будет равен 0, если a и b равны 0 (нулю), а во всех остальных (других) случаях, результат равен 1 (единице). Смотрим таблицу истинности логической операции OR.

a(бит 1)	b(бит 2)	a(бит 1) | b(бит 2)
0	0	0
0	1	1
1	0	1
1	1	1

Логическая операция исключающее ИЛИ (XOR).

Обозначение XOR: ^
Логическая операция исключающее ИЛИ выполняется с двумя битами (a и b). Результат выполнения логической операции XOR будет равен 1 (единице), если один из битов a или b равен 1 (единице), во всех остальных случаях, результат равен 0 (нулю). Смотрим таблицу истинности логической операции исключающее ИЛИ.

a(бит 1)	b(бит 2)	a(бит 1) ^ b(бит 2)
0	0	0
0	1	1
1	0	1
1	1	0

Логическая операция НЕ (not)

Обозначение NOT: ~
Логическая операция НЕ выполняется с одним битом. Результат выполнения этой логической операции напрямую зависит от состояния бита. Если бит находился в нулевом состоянии, то результат выполнения NOT будет равен единице и наоборот. Смотрим таблицу истинности логической операции НЕ.

a(бит 1)	~a(отрицание бита)
0	1
1	0

Запомните эти 4 логические операции. Используя эти логические операции, мы можем получить любой возможный результат. Подробно об использовании логических операций в С++ читаем .

C++. Логические операции. Поразрядные логические операции. Операции сдвига. Операция XOR

1. Для каких типов можно применять логические операции, поразрядные логические операции и операции сдвига?

Логические операции, поразрядные логические операции и операции сдвига можно использовать только для операндов целых типов.

2. Какие логические операции используются в C/C++?

В языке программирования C/C++ используются следующие логические операции:

• && – логическое «И»;
• || – логическое «ИЛИ»;
• ! – логическое «НЕТ».

Результатом логических операций есть значение false или true . В языке C++ принято, что значение false считается равным 0, а значение true считается равным 1.

Отсюда можно сделать вывод, что false < true . Например:

// логические операции bool res; res = false < true ; // res = true

3. Таблица истинности логических операций

Таблица истинности логических операций && (логическое «И»), || (логическое «ИЛИ»), ! (логическое «НЕТ») имеет следующий вид:

В языке C/C++ принимается, что значение false равно 0, а значение true не равно 0 (любое ненулевое целочисленное значение).

4. Примеры использования логических операций в C++

Пример 1. Логическая операция в сочетании с логическим выражением

// логические операции bool res; int a, b; // операция && (AND) a = 8; b = 5; res = a && b; // res = True a = 0; res = a && b; // res = False // операция || (OR) a = 0; b = 0; res = a || b; // res = False b = 7; res = a || b; // res = True // операция! (логическое "НЕТ") a = 0; res = !a; // res = True a = 15; res = !a; // res = False

Пример 2. Логическая операция в условных выражениях. Приведен фрагмент кода, в котором логическая операция используется в операторе условного перехода if .

// логические операции в условных выражениях int a, b; bool res; a = 0; b = 3; res = false ; if (a && b) res = true ; // res = false a = 0; b = 7; if (a || b) res = true ; // res = true

5. Какие поразрядные логические операции используются в C/C++?

Язык С/С++ поддерживает следующие поразрядные логические операции :

• & – поразрядное логическое И (AND );
• ^ – поразрядное сложение по модулю 2 (XOR — исключающее ИЛИ);
• | – поразрядное логическое ИЛИ (OR );
• ~ – поразрядная инверсия (NOT ).

Операции & , ^ , | есть бинарными. Это означает, что они требуют двух операндов. Биты любого операнда сравниваются между собой по следующему правилу : бит в позиции 0 первого операнда сравнивается с битом в позиции 0 второго операнда. Затем бит в позиции 1 первого операнда сравнивается с битом в позиции 1 второго операнда. Так сравниваются все биты целочисленных операндов.

6. Таблица истинности поразрядных логических операций

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

Инверсия требует единого операнда справа от знака ~ . Результат получается поразрядной инверсией всех битов операнда.

7. Пример работы с логическими побитовыми операциями

Пусть даны два числа 17 и 45 типа unsigned short int . Каждое из чисел занимает в памяти 1 байт или 8 бит. Ниже приведен пример того, как происходит вычисление для каждой побитовой операции

Как видно из примера, происходит выполнение заданной операции над каждым битом.

8. Какие операции сдвига используются в C/C++?

Язык С/С++ включают две операции поразрядного сдвига :

• << – сдвиг влево значения операнда на заданное количество бит. Операнд размещается слева от знака операции. Число сдвигаемых бит указывается справа от знака операции;
• >> – сдвиг вправо значения операнда на заданное количество бит. Операнд размещается слева от знака операции (<<). Количество сдвигаемых бит размещается справа от знака операции.

Выдвижные биты теряются, а «входят» нулевые биты. Сдвиг операндов влево на 1, 2, 3 и более разрядов – наиболее быстрый способ умножения на 2, 4, 8, … Сдвиг операндов вправо на 1, 2, 3 и более разрядов – наиболее быстрый способ деления на 2, 4, 8, …

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

Это касается и случаев, когда нужно максимально быстро поделить целочисленный операнд на 2, 4, 8 и т.д. В этих случаях рекомендуется использовать сдвиг вправо.

9. Примеры использования операций сдвига в программе

// Операции сдвига int a; int b; int c; a = 15; b = -5; // сдвиг влево - умножение c = a << 1; // c = a * 2^1 = 30 c = b << 2; // c = b * 2^2 = -20 // сдвиг вправо - деление c = a >> 3; // c = a / 2^3 = 1 c = b >> 1; // c = b / 2^1 = -3

10. Какое отличие между логическими операциями и поразрядными логическими операциями?

В логических операциях сравнивается значение двух операндов целиком. Каждый из операндов может иметь значение true или false . Язык C/C++ допускает сравнение операндов, которые являются целыми числами. В этом случае целочисленное значение 0 соответствует значению false , а ненулевое (любое другое) значение соответствует значению true .