Xor логическая операция c. Более сложные логические элементы. Примеры использования операций сдвига в программе

функция , выполняемая ими, несколько сложнее, чем в случае элемента И или элемента ИЛИ. Все входы элементов Исключающее ИЛИ равноправны, однако ни один из входов не может заблокировать другие входы, установив выходной сигнал в уровень единицы или нуля. Таблица 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 раза), чем задержка в простейших элементах И, И-НЕ, ИЛИ, ИЛИ-НЕ.

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

Введение

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

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

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

Обозначается оборотом речи «либо…, либо…» Составное утверждение «либо A, либо B» считается истинным, когда истинно либо A, либо B, но не оба сразу; в противном случае составное утверждение ложно.

Т.е. результат истинен (равен 1), если A не равно B (A≠B).

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

1. истинно, если истинно или , или оба сразу.

2. истинно, если истинно или , но не оба сразу.

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

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

Запись: А®В

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

Т.е. если из 1 следует 0, то результат – 0, в остальных случаях – 1.

Например, высказывание «Если число делится на 10, то оно делится на 5» истинно, т.к. истинны и первое и второе высказывание.

Высказывание «Если число делится на 10, то оно делится на 3» ложно, т.к. из истинной предпосылки делается ложный вывод.

"Данный четырёхугольник - квадрат" (А ) и "Около данного четырёхугольника можно описать окружность" (В ). Тогда составное высказывание , читается как "Если данный четырёхугольник квадрат, то около него можно описать окружность".

В обычной речи связка "если..., то" описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться "бессмысленностью" импликаций, образованных высказываниями, совершенно не связанными по содержанию. Например, такими: "если президент США - демократ, то в Африке водятся жирафы", "если арбуз - ягода, то в бензоколонке есть бензин".

6. Эквивалентность (логическое равенство, ~ º Û) образуется соединением двух высказываний в одно с помощью оборота речи « …тогда и только тогда, когда...»

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

Например, высказывание «Компьютер может производить вычисления тогда и только тогда, когда он включен» и «Компьютер не может производить вычисления тогда и только тогда, когда он не включен» - истинны, поскольку оба простых высказывания одновременно истинны.

Таблицы истинности

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

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

Отразим выше рассмотренные логические операции в таблице истинности:

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

Докажем, что операция импликация А®В равносильна логическому выражению:

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

Операнды в данном случае подаются - на вход логического элемента поступают сигналы в форме напряжения высокого или низкого уровня, которые и служат по сути входными данными. Так, напряжение высокого уровня - это логическая единица 1 - обозначает истинное значение операнда, а напряжение низкого уровня 0 - значение ложное. 1 - ИСТИНА, 0 - ЛОЖЬ.

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

Логические элементы имеют один или несколько входов и один или два (обычно инверсных друг другу) выхода. Значения «нулей» и «единиц» выходных сигналов логических элементов определяются логической функцией, которую выполняет элемент, и значениями «нулей» и «единиц» входных сигналов, играющих роль независимых переменных. Существуют элементарные логические функции, из которых можно составить любую сложную логическую функцию.

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

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

Логический элемент «И» - конъюнкция, логическое умножение, AND

«И» - логический элемент, выполняющий над входными данными операцию конъюнкции или логического умножения. Данный элемент может иметь от 2 до 8 (наиболее распространены в производстве элементы «И» с 2, 3, 4 и 8 входами) входов и один выход.

Условные обозначения логических элементов «И» с разным количеством входов приведены на рисунке. В тексте логический элемент «И» с тем или иным числом входов обозначается как «2И», «4И» и т. д. - элемент «И» с двумя входами, с четырьмя входами и т. д.

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

На западных схемах значок элемента «И» имеет прямую черту на входе и закругление на выходе. На отечественных схемах - прямоугольник с символом «&».

Логический элемент «ИЛИ» - дизъюнкция, логическое сложение, OR

«ИЛИ» - логический элемент, выполняющий над входными данными операцию дизъюнкции или логического сложения. Он так же как и элемент «И» выпускается с двумя, тремя, четырьмя и т. д. входами и с одним выходом. Условные обозначения логических элементов «ИЛИ» с различным количеством входов показаны на рисунке. Обозначаются данные элементы так: 2ИЛИ, 3ИЛИ, 4ИЛИ и т. д.

Таблица истинности для элемента «2ИЛИ» показывает, что для появления на выходе логической единицы, достаточно чтобы логическая единица была на первом входе ИЛИ на втором входе. Если логические единицы будут сразу на двух входах, на выходе также будет единица.

На западных схемах значок элемента «ИЛИ» имеет закругление на входе и закругление с заострением на выходе. На отечественных схемах - прямоугольник с символом «1».

Логический элемент «НЕ» - отрицание, инвертор, NOT

«НЕ» - логический элемент, выполняющий над входными данными операцию логического отрицания. Данный элемент, имеющий один выход и только один вход, называют еще инвертором, поскольку он на самом деле инвертирует (обращает) входной сигнал. На рисунке приведено условное обозначение логического элемента «НЕ».

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

На западных схемах значок элемента «НЕ» имеет форму треугольника с кружочком на выходе. На отечественных схемах - прямоугольник с символом «1», с кружком на выходе.

Логический элемент «И-НЕ» - конъюнкция (логическое умножение) с отрицанием, NAND

«И-НЕ» - логический элемент, выполняющий над входными данными операцию логического сложения, и затем операцию логического отрицания, результат подается на выход. Другими словами, это в принципе элемент «И», дополненный элементом «НЕ». На рисунке приведено условное обозначение логического элемента «2И-НЕ».

Таблица истинности для элемента «И-НЕ» противоположна таблице для элемента «И». Вместо трех нулей и единицы - три единицы и ноль. Элемент «И-НЕ» называют еще «элемент Шеффера» в честь математика Генри Мориса Шеффера, впервые отметившего значимость этой в 1913 году. Обозначается как «И», только с кружочком на выходе.

Логический элемент «ИЛИ-НЕ» - дизъюнкция (логическое сложение) с отрицанием, NOR

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

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

Логический элемент «исключающее ИЛИ» - сложение по модулю 2, XOR

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

Изображение в западных схемах - как у «ИЛИ» с дополнительной изогнутой полоской на стороне входа, в отечественной - как «ИЛИ», только вместо «1» будет написано «=1».

Этот логический элемент еще называют «неравнозначность». Высокий уровень напряжения будет на выходе лишь тогда, когда сигналы на входе не равны (на одном единица, на другом ноль или на одном ноль, а на другом единица) если даже на входе будут одновременно две единицы, на выходе будет ноль - в этом отличие от «ИЛИ». Данные элементы логики широко применяются в сумматорах.

Абсолютно все цифровые микросхемы состоят из одних и тех же логических элементов – «кирпичиков» любого цифрового узла. Вот о них мы и поговорим сейчас.

Логический элемент – это такая схемка, у которой несколько входов и один выход. Каждому состоянию сигналов на входах, соответствует определенный сигнал на выходе.

Итак, какие бывают элементы?

Элемент «И» (AND)

Иначе его называют «конъюнктор».

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

Вот так выглядит элемент «И» и его таблица истинности:

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

Смотрим таблицу истинности, и проясняем в мозгу принцип. Понять его не сложно: единица на выходе элемента «И» возникает только тогда, когда на оба входа поданы единицы. Это объясняет название элемента: единицы должны быть И на одном, И на другом входе.

Если посмотреть чуток иначе, то можно сказать так: на выходе элемента «И» будет ноль в том случае, если хотя бы на один из его входов подан ноль. Запоминаем. Идем дальше.

Элемент «ИЛИ» (OR)

По другому, его зовут «дизъюнктор».

Любуемся:

Опять же, название говорит само за себя.

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

Элемент «НЕ» (NOT)

Чаще, его называют «инвертор».

Надо чего-нибудь говорить по поводу его работы?

Элемент «И-НЕ» (NAND)

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

Элемент «ИЛИ-НЕ» (NOR)

Та же история – элемент «ИЛИ» с инвертором на выходе.

Следующий товарищ устроен несколько хитрее:
Элемент «Исключающее ИЛИ» (XOR)

Он вот такой:

Операция, которую он выполняет, часто называют «сложение по модулю 2». На самом деле, на этих элементах строятся цифровые сумматоры.

Смотрим таблицу истинности. Когда на выходе единицы? Правильно: когда на входах разные сигналы. На одном – 1, на другом – 0. Вот такой он хитрый.

Эквивалентная схема примерно такая:

Ее запоминать не обязательно.

Собственно, это и есть основные логические элементы. На их основе строятся абсолютно любые цифровые микросхемы. Даже ваш любимый Пентиум 4.

Ну и напоследок – несколько микросхем, внутри которых содержатся цифровые элементы. Около выводов элементов обозначены номера соответствующих ног микросхемы. Все микросхемы, перечисленные здесь, имеют 14 ног. Питание подается на ножки 7 (-) и 14 (+). Напряжение питания – смотри в таблице в предыдущем параграфе.