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

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

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

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

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 обозначается ^ .

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

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

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

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(); }

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

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

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

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

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

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

Операнды в данном случае подаются - на вход логического элемента поступают сигналы в форме напряжения высокого или низкого уровня, которые и служат по сути входными данными. Так, напряжение высокого уровня - это логическая единица 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».

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

Рис. 4.1.

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

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

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

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

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

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

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

Простейшие логические операции относятся к двузначной логике. Их 4 штуки: “НЕ”, “И”, “ИЛИ”, “XOR”. Также для обозначения этих операций используют разные значки (“~”, “&” и т.п.).

При записи логических формул вместо слов “истина” и “ложь” обычно используют стандартные международные обозначения:
Вместо “истина” пишут: true, T, t, 1.
Вместо “ложь” пишут: false, F, f, 0.

“НЕ”

Операция “НЕ” преобразует истину в ложь, а ложь в истину:

НЕ true = false
НЕ false = true

У этой операции бывают разные другие названия: “логическое НЕ”, “отрицание”, “логическое отрицание”, “инверсия”, “логическая инверсия”. Для международных обозначений вместо “НЕ” пишут “NOT”.

В естественном языке этой операции соответствует добавление слов “неправда, что...” в начале высказывания. Например:

Применение операции “НЕ” к высказыванию (1):

“Неправда, что Сурков должен мне денег”. (2)

Если высказывание (1) ложно, то высказывание (2) истинно. Если высказывание (2) ложно, то высказывание (1) истинно.

Нетрудно понять, что двойное применение “НЕ” возвращает нас к прежней истинности.

“Неправда, что неправда, что Сурков должен мне денег”. (3)

Истинность высказывания (3) всегда совпадает с истинностью высказывания (1).

“И”

Операция “И” применяется к двум высказываниям. Ее результат “истина”, только если оба высказывания истинны (а иначе “ложь”):

false И false = false
false И true = false
true И false = false
true И true = true

У этой операции бывают разные другие названия: “логическое И”, “конъюнкция”, “логическое умножение”. Для международных обозначений вместо “И” пишут “AND”.

В естественном языке этой операции соответствует вставка союза “и” между высказываниями. Например:

“Сурков должен мне денег”. (1)
“Петров должен мне денег”. (2)

Применение операции “И” к высказываниям (1) и (2):

“Сурков должен мне денег, и Петров должен мне денег”. (3)

Эту фразу можно сократить, сохранив прежний смысл:

“Сурков и Петров должны мне денег”. (3)

Высказывание (3) истинно только тогда, когда истинны оба высказывания: (1) и (2). Если хотя бы одно из них ложно, то результат тоже ложен. Если оба ложны – тоже.

То есть, если Петров мне денег не задолжал, а задолжал только Сурков, тогда высказывание (3) не будет “полуправдой” или “полуложью”, а будет просто ложью.

“ИЛИ”

Операция “ИЛИ” применяется к двум высказываниям. Ее результат “истина”, если хотя бы одно высказывание истинно (а иначе “ложь”):

false ИЛИ false = false
false ИЛИ true = true
true ИЛИ false = true
true ИЛИ true = true

У этой операции бывают разные другие названия: “логическое ИЛИ”, “включающее ИЛИ”, “дизъюнкция”, “логическое сложение”. Для международных обозначений вместо “ИЛИ” пишут “OR”.
В естественном языке этой операции соответствует вставка союза “или” между высказываниями, но... не всегда (см. ниже об операции “XOR”). Например:

“Я хочу попить”. (1)
“Я хочу поесть”. (2)

Применение операции “ИЛИ” к высказываниям (1) и (2):

“Я хочу попить, или я хочу поесть”. (3)

По-русски звучит правильно, но коряво, и эту фразу можно сократить, сохранив прежний смысл:

“Я хочу попить или поесть ”. (3)

Высказывание (3) истинно тогда, когда истинно хотя бы одно из высказываний (1) и (2), а можно оба. Если оба высказывания ложны, то результат тоже ложен.

То есть, если я хочу есть, но не пить, тогда высказывание (3) истинно. Если я не прочь и поесть, и попить, выказывание (3) тоже истинно. Ложно оно тогда, когдя я не хочу ни того, ни другого.

“XOR”

Операция “XOR” применяется к двум высказываниям. Ее результат “истина”, если ровно одно из высказываний истинно (а иначе “ложь”):

false XOR false = false
false XOR true = true
true XOR false = true
true XOR true = false

У этой операции бывают разные другие названия: “исключающее ИЛИ”, “сложение по модулю 2”, “логическое сложение по модулю 2”. “XOR” – это международное обозначение, общепринятого “русского” аналога нет.

В естественном языке этой операции соответствует вставка союза “или” между высказываниями – так же, как в случае с операцией “ИЛИ”. Например:

“Я собираюсь просить прибавки к зарплате”. (1)
“Я попытаюсь сэкономить ”. (2)

Применение операции “XOR” к высказываниям (1) и (2):

“Я собираюсь просить прибавки к зарплате или я попытаюсь сэкономить”. (3)

Сокращенно:

“Я собираюсь просить прибавки к зарплате или попытаюсь сэкономить”. (3)

Высказывание (3) истинно тогда, когда истинно ровно одно из высказываний (1) и (2). Если я не собираюсь ни просить прибавки, ни экономить, тогда фраза ложна. Также, я имел в виду, что не собираюсь делать и то, и другое одновременно.

Обратите внимание на разницу между операциями “ИЛИ” и “XOR”. Она заключается только в последнем правиле:

true ИЛИ true = true
true XOR true = false

В естественном языке обе операции изображаются одним и тем же союзом “или”. Это – пример неоднозначности естественного языка. Если помните, омонимы и многозначные слова могут иметь больше одного значения. Союз “или” именно такой: он имеет два возможных значения. Первое выражается логической операцией “ИЛИ”, второе – логической операцией “XOR”.

В английском языке существуют те же проблемы: союз “or” имеет те же два значения. А вот древним римлянам было проще, так как в латыни есть два разных слова: “vel” (операция “ИЛИ”) и “aut” (операция “XOR”).

Поскольку разница между операциями “ИЛИ” и “XOR” невелика (всего одно последнее правило), то иногда эта разница не имеет значения. Иногда о том, что имеется в виду, можно догадаться по интонации, или по контексту. Иногда определить точный смысл так и не удается.

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

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

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

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

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

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

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

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

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

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

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

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