Для чего используется символ оператор xor исключающий или

Практика применения XOR в программировании

В данной статье я расскажу о битовой операции XOR (исключающее ИЛИ) и приведу наиболее интересные примеры ее применения на JAVA.

Итак, XOR – операция, которая принимает значение «истина» только если всего один из аргументов имеет значение «истина».

XOR обладает следующими свойствами:

a XOR 0 = a
a XOR a = 0
a XOR b = b XOR a
(a XOR b) XOR b = a

В языке JAVA (а также в С, С++, C#, Ruby, PHP, JavaScript) операция обозначается символом «^».

Обмен значений переменных без использования дополнительной переменной

С использованием операции XOR можно реализовать обмен значений однотипных пременных без использования дополнительной переменной:

или в более короткой записи:

Таким образом можно, например, реализовать реверс текстовой строки:

Следует, однако, заметить, что такой код не дает выигрыша в скорости по сравнению с кодом использующим временную переменную.

Шифрование

Шифрование на основе операций XOR использует свойство:
(a XOR k) XOR k = a
где k – выступает в роли ключа

Простая реализация шифрования строки:

Попробуем зашифровать строку “Съешь ещё этих мягких французских булок, да выпей чаю.” И в качестве ключа возьмем слово “хабра”:

Узким местом такого шифрования является то, что зная часть зашифрованного текста можно с легкостью восстановить ключ и, соответственно, расшифровать весь текст. Поэтому в чистом виде он редко используется на практике, хотя его применяют как часть более сложных алгоритмов шифрования.
Интересно, что в свое время данный алгоритм использовался Microsoft для шифрования содержимого документов в Office 95.

Генератор случайных чисел XORShift

В 2003 году Джордж Марсаглия представил миру быстрый алгоритм генерации случайных чисел с использованием XOR – XORShift.

Одна из возможных его рализаций:

39462749392662495
4596835458788324745
-7932128052244037525
-2502212788642280052
3288035714308340525
-8561046377475020727
-812160615072319265
-3869866974339671508
-7329504029400927428
3890915262874757420

В заключение просьба тем, у кого есть другие красивые примеры применения XOR, не вошедшие в статью, рассказать о них.

Источник

Трюк с XOR для собеседований и не только

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

Хоть и непривычно ожидать решения с XOR на собеседованиях, довольно забавно разбираться, как они работают. Оказывается, все они основаны на одном фундаментальном трюке, который я постепенно раскрою в этом посте. Далее мы рассмотрим множество способов применения этого трюка с XOR, например, при решении популярной задачи с собеседований:

Дан массив из n — 1 целых чисел, находящихся в интервале от 1 до n. Все числа встречаются только один раз, за исключением одного числа, которого нет. Найдите отсутствующее число.

В большинстве языков программирования ^ реализован как побитовый оператор, то есть XOR по отдельности применяется к каждому биту в строке битов (например, в байте).

Благодаря этому мы можем применять XOR к чему угодно, а не только к булевым значениям.

Выявляем полезные свойства

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

XOR и 0: x ^ 0 = x

XOR с одинаковыми аргументами: x ^ x = 0

Это означает, что применив XOR к одинаковым аргументам, мы их взаимно уничтожим.

Коммутативность: x ^ y = y ^ x

Операция XOR коммутативна, то есть мы можем менять порядок применения XOR. Чтобы доказать это, можно взглянуть на таблицу истинности x ^ y и y ^ x :

Как мы видим, x ^ y и y ^ x всегда дают одинаковые значения.

Последовательности операций XOR

Скомбинировав всё это, мы можем вывести главную мысль, стоящую в основе всего дальнейшего:

Давайте разберём пример:

Способ применения 1: перемена значений местами

Прежде чем приступать к задаче поиска отсутствующего числа, давайте начнём с более простой задачи:

Поменяйте местами два значения x и y без использования вспомогательных переменных.

Оказывается, эту задачу можно легко решить при помощи трёх команд XOR:

Это кажется довольно загадочным. Почему при этом x и y поменяются местами?

Чтобы понять, как это происходит, давайте разберёмся пошагово. В комментарии после каждой команды указаны текущие значения (x, y) :

Воспользовавшись выведенными ранее свойствами, мы видим, что это на самом деле так.

Способ применения 2: поиск отсутствующего числа

Давайте наконец решим задачу, представленную в начале поста:

Дан массив A из n — 1 целых чисел, находящихся в интервале от 1 до n. Все числа встречаются в нём ровно один раз, за исключением одного отсутствующего числа. Найти это отсутствующее число.

Разумеется, есть множество прямолинейных решений этой задачи, но мы решили использовать XOR.

Из трюка с XOR мы знаем, что имея последовательность операторов XOR, можно убрать из неё все повторяющиеся аргументы. Однако если мы просто применим XOR ко всем значениям массива, то не сможем воспользоваться этим трюком, потому что в нём нет одинаковых значений:

Так мы получим последовательность операторов XOR, в которой элементы встречаются следующим образом:

В коде это будет выглядеть примерно так:

С первого взгляда на код алгоритм понять сложно. Однако если знать, как работает трюк с XOR, то он становится довольно тривиальным. По-моему, именно поэтому не стоит ждать такого решения на собеседованиях: оно требует знания очень специфичного трюка, но почти никакого алгоритмического мышления.

Прежде чем мы перейдём к следующему способу применения, я сделаю пару замечаний.

Использование этого трюка не только для целых чисел

Хоть мы пока работали только с целыми числами от 1 до n, это необязательно. На самом деле, предыдущий алгоритм работает в любой ситуации, где есть (1) некоторое множество потенциальных элементов и (2) множество действительно встречающихся элементов. Эти множества могут отличаться только одним отсутствующим элементом. Это замечательно сработало для целых чисел, потому что множество потенциальных элементов соответствует элементам от 1 до n.

Можно придумать способы применения, где элементы не являются целыми числами от 1 до n:

Арифметические операции вместо XOR

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

Способ применения 3: поиск повторяющегося числа

И вот здесь всё становится интереснее: мы можем применить точно такое же решение к похожей задаче с собеседования:

Дан массив A из n + 1 целых чисел, находящихся в интервале от 1 до n. Все числа встречаются ровно один раз, за исключением одного числа, которое повторяется. Найти это повторяющееся число.

Давайте подумаем, что произойдёт, если мы просто применим алгоритм из предыдущего решения. Мы получим последовательность операторов XOR, в которой элементы встречаются следующим образом:

Все остальные элементы взаимно уничтожаются, потому что встречаются ровно два раза.

Способ применения 4: поиск двух отсутствующих/повторяющихся чисел

Оказывается, мы можем расширить возможности алгоритма. Рассмотрим чуть более сложную задачу:

Дан массив A из n — 2 целых чисел, находящихся в интервале от 1 до n. Все числа встречаются ровно один раз, за исключением двух отсутствующих чисел. Найти эти два отсутствующих числа.

Как и ранее, задача полностью эквивалентна поиску двух повторяющихся чисел.

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

Разделение при помощи изучения u ^ v

К счастью, мы можем понять, что делать, воспользовавшись изложенным выше. Давайте подумаем:

Упрощаем задачу

Далее мы можем использовать ещё одно сделанное ранее открытие:

Хоть пока мы работали только с целыми числами от 1 до n, это необязательно. На самом деле, предыдущий алгоритм работает в любой ситуации, где есть (1) некоторое множество потенциальных элементов и (2) множество действительно встречающихся элементов. Эти множества могут отличаться только одним отсутствующим (или повторяющимся) элементом.

На самом деле это очень удобный способ решения задачи: по сути, мы сводим данную новую задачу к более общей версии решённой ранее задачи.

Достигнуть предела

Следовательно, задача требует более сложных решений, больше не использующих XOR.

Заключительные мысли

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

Однако здорово было выяснить, как этот трюк работает. Похоже, XOR обладает идеально подходящими для этой задачи свойствами. Кроме того, есть некая красота в том, что нечто столь фундаментальное, как XOR, можно использовать для создания описанных в статье алгоритмов.

На правах рекламы

VDSina предлагает виртуальные серверы на Linux и Windows — выбирайте одну из предустановленных ОС, либо устанавливайте из своего образа.

Источник

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

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

Синтаксис

Компоненты

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

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

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

Комментарии

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

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

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

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

Типы данных

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

Перегрузка

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

Пример 1

Пример 2

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

В предыдущем примере выдается результат 2, 12 и 14 соответственно.

Источник

Побитовые операции в Java

1. Побитовый оператор AND

Когда-то мы говорили, что все данные хранятся в памяти в двоичной системе. Поэтому довольно давно программисты придумали много чего интересного для работы с двоичным представлением чисел. Например, в Java есть логические операторы, которые работают с битами чисел: AND (И), OR (ИЛИ), NOT (НЕ) и XOR (исключающее или).

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

Ну а оператор AND (И) означает, что «результирующий бит равен единице, только если бит числа a равен единице И бит числа b равен единице»:

2. Побитовый оператор OR

Данный оператор очень похож на логический оператор OR (ИЛИ), только обозначается уже не двумя вертикальными линиями, а одной:

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

Побитовый OR (ИЛИ) означает, что «результирующий бит равен единице если бит числа a равен единице ИЛИ бит числа b равен единице»:

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

Источник

Оператор Xor

Используется для выполнения логического исключения для двух выражений.

Синтаксис

[ результат = ] expression1 Xor expression2

Синтаксис оператора Xor содержит следующие элементы:

Примечания

Если только одно из выражений имеет значение True, результат имеет значение True. Однако, если любое из выражений имеет нулевое значение, результат также будет иметь нулевое значение.

Если ни одно из выражений не является Null, результат определяется в соответствии со следующей таблицей.

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

Пример

В этом примере оператор Xor используется для выполнения логического исключения для двух выражений.

См. также

Поддержка и обратная связь

Есть вопросы или отзывы, касающиеся Office VBA или этой статьи? Руководство по другим способам получения поддержки и отправки отзывов см. в статье Поддержка Office VBA и обратная связь.

Источник