Что такое исключающее или

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

Авторизуйтесь

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

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

Введение

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

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

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

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

Побитовое ИЛИ (OR)

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

38 | 53 будет таким:

Побитовое И (AND)

Побитовое И — это что-то вроде операции, противоположной побитовому ИЛИ. Двоичный разряд результата равен 1 только тогда, когда оба соответствующих бита операндов равны 1. Другими словами, можно сказать, двоичные разряды получившегося числа — это результат умножения соответствующих битов операнда: 1х1 = 1, 1х0 = 0. Побитовому И соответствует следующая таблица истинности:

Пример работы побитового И на выражении 38 & 53:

Исключающее ИЛИ (XOR)

Разница между исключающим ИЛИ и побитовым ИЛИ в том, что для получения 1 только один бит в паре может быть 1:

Например, выражение 138^43 будет равно…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вывод

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

Источник

Практика применения 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, не вошедшие в статью, рассказать о них.

Источник

Основные логические операции. AND, NOT, OR и XOR (исключающее или)

В этой статье мы поговорим о некоторых битовых операциях. Рассмотрим основные из них: XOR (исключающее ИЛИ), AND (И), NOT (НЕ) а также OR (ИЛИ).

Как известно, минимальной единицей измерения информации является бит, который хранит одно из 2-х значений: 0 (False, ложь) либо 1 (True, истина). Таким образом, битовая ячейка может одновременно находиться лишь в одном из двух возможных состояний.

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

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

Оператор AND выполняется с 2-мя битами, возьмём, к примеру, a и b. Результат выполнения операции AND равен 1, если a и b равняются 1. В остальных случаях результат равен 0. Например, с помощью AND вы можете узнать, чётное число или нет.

Посмотрите на таблицу истинности операции AND:

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

Оператор OR также выполняется с 2-мя битами (a и b). Результат равен 0, если a и b равны 0, иначе он равен 1. Смотрим таблицу истинности.

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

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

Таблица истинности логической операции для XOR (исключающее ИЛИ) выглядит так:

Используя XOR (исключающее ИЛИ), вы можете поменять значения 2-х переменных одинакового типа данных, не используя временную переменную. А ещё, посредством XOR можно зашифровать текст, например:

Согласен, XOR — далеко не самый надёжный метод шифрования, но это не значит, что его нельзя сделать частью какого-либо шифровального алгоритма.

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

Это побитовое отрицание, поэтому выполняется с одним битом и обозначается

Результат зависит от состояния бита. Если он в нулевом состоянии, то итог операции — единица и наоборот. Всё предельно просто.

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

Источник

ElectronicsBlog

Обучающие статьи по электронике

Логический элемент Исключающее ИЛИ

Всем доброго времени суток! Сегодня мы рассмотрим последние два элемента, которые выполняют простейшие логические функции. Такими элементами являются Исключающее ИЛИ (Exclusive-OR, XOR) и Исключающее ИЛИ-НЕ (None Exclusive-OR, NXOR). Предыдущие статьи смотрите здесь, здесь, здесь и здесь.

Для сборки радиоэлектронного устройства можно преобрески DIY KIT набор по ссылке.

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

Элементы Исключающее ИЛИ из-за своего специфического функционала не имеют широкого применения, поэтому отдельных суффиксов в их обозначении не присутствует, они в основном входят в серию ЛП (например, К555ЛП5, КР1533ЛП12, К561ЛП2), в составе которой микросхемы с различным функционалом. Логические элементы Исключающее ИЛИ имеют своё графическое обозначение, которое приведено ниже.

Условное графическое обозначение элементов Исключающее ИЛИ: DIN (слева) и ANSI (справа).

Применение элемента Исключающее ИЛИ

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

Управляемый инвертор

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

Элемент Исключающее ИЛИ в качестве управляемого инвертора.

Смешивание сигналов

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

Применение элемента Исключающее ИЛИ для смешивания двух неодновременных сигналов.

Формирование коротких импульсов

Второе важное применение данного элемента – выделение фронта и среза входного импульса, которое традиционно делали с помощью дифференцирующего RC-звена, с последующим усилением и формированием сигнала. Микросхема с элементами Исключающее ИЛИ упрощает данную задачу.

Выделения фронта и среза импульса.

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

Схема реализующая выделение фронта и среза импульса.

Теория это хорошо, но без практического применения это просто слова.Здесь можно всё сделать своими руками.

Источник

Трюк с 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 — выбирайте одну из предустановленных ОС, либо устанавливайте из своего образа.

Источник