Как работает xor

Команда XOR

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

B0 XOR B1 XOR B2 XOR B3

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

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

Оператор Xor (Visual Basic)

Выполняет логическое исключение для двух Boolean выражений или побитовое исключение для двух числовых выражений.

Синтаксис

Компоненты

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

expression1
Обязательный. Произвольное выражение типа Boolean или числового типа.

expression2
Обязательный. Произвольное выражение типа Boolean или числового типа.

Комментарии

Для логического сравнения result параметр имеет True значение, только если в True точности один из значений expression1 expression2 равен. То есть, если и только если expression1 и expression2 имеют противоположные Boolean значения. В следующей таблице показано, как result определяется.

Если expression1 имеет значение	И expression2 является	Значение result равно
True	True	False
True	False	True
False	True	True
False	False	False

При логическом сравнении Xor оператор всегда вычисляет оба выражения, которые могут включать вызовы процедур. Не существует аналога Xor сокращенного выражения, поскольку результат всегда зависит от обоих операндов. Дополнительные операторы для сокращенного вычисления логических операторов см. в разделе оператор AndAlso и оператор OrElse.

Для побитовых операций Xor оператор выполняет побитовое сравнение одинаково позиционированных битов в двух числовых выражениях и устанавливает соответствующий бит в result соответствии со следующей таблицей.

Если бит в expression1 имеет значение	И bit в expression2 имеет	Бит в result имеет значение
1	1	0
1	0	1
0	1	1
0	0	0

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

Например, 5 Xor 3 — 6. Чтобы узнать, почему это так, преобразуйте значения 5 и 3 в двоичные представления, 101 и 011. Затем используйте предыдущую таблицу, чтобы определить, что 101 Xor 011 имеет значение 110, которое является двоичным представлением десятичного числа 6.

Типы данных

если операнды состоят из одного Boolean выражения и одного числового выражения, Visual Basic преобразует Boolean выражение в числовое значение (– 1 для True и 0 для False ) и выполняет побитовую операцию.

Boolean Для сравнения тип данных результата — Boolean . Для побитового сравнения тип данных результата является числовым типом, подходящим для типов expression1 данных и expression2 . См. таблицу «реляционные и побитовые сравнения» в разделе типы данных результатов операторов.

Перегрузка

Xor Оператор можно Xor , что означает, что класс или структура может переопределить свое поведение, когда операнд имеет тип этого класса или структуры. Если код использует этот оператор для такого класса или структуры, убедитесь, что вы понимаете его переопределенное поведение. Для получения дополнительной информации см. Operator Procedures.

Пример 1

В следующем примере оператор используется Xor для выполнения логического исключения (исключающее логическое сложение) в двух выражениях. Результатом является Boolean значение, указывающее, имеет True ли только одно из выражений.

В предыдущем примере создаются результаты False , True и False соответственно.

Пример 2

В следующем примере оператор используется Xor для выполнения логического исключения (исключающее логическое сложение) для отдельных битов двух числовых выражений. Бит в результирующем шаблоне устанавливается, если только один из соответствующих битов операндов имеет значение 1.

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

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

Введение

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

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

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

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

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

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₂ , или 55₁₀ .

Побитовое И (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₂ , или 36₁₀ .

С помощью побитового оператора И можно проверить, является ли число четным или нечетным. Для целых чисел, если младший бит равен 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

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

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

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

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

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

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

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

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

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

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

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

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

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

Представленным выше методом мы получаем -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. Тем не менее, битовые операции неплохо иметь в своем арсенале, и теперь вы сможете воспользоваться ими в случае надобности или же ответить на каверзный вопрос на собеседовании.