В результате какой логической операции xor. Логический элемент исключающее или

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

Теги: Си битовые операции, побитовые операции, побитовое сложение, побитовое умножение, битовый сдвиг влево, битовый сдвиг вправо

Введение

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

Побитовые операции, как понятно из названия, позволяют оперировать непосредственно с битами. Большое количество примеров использования побитовых операций можно найти, например, в книге Генри Уоррена «Алгоритмические трюки для программистов». Здесь мы рассмотрим только сами операции и примитивные алгоритмы.

Побитовые И, ИЛИ, НЕ, исключающее ИЛИ

Н апомню для начала, что логические операции И, ИЛИ, исключающее ИЛИ и НЕ могут быть описаны с помощью таблиц истинности

В побитовых (bit-wise) операциях значение бита, равное 1, рассматривается как логическая истина, а 0 как ложь. Побитовое И (оператор &) берёт два числа и логически умножает соответствующие биты. Например, если логически умножить 3 на 8, то получим 0

Char a = 3; char b = 8; char c = a & b; printf("%d", c);

Так как в двоичном виде 3 в виде однобайтного целого представляет собой

Первый бит переменной c равен логическому произведению первого бита числа a и первого бита числа b. И так для каждого бита.

00000011
00001000
↓↓↓↓↓↓↓↓
00000000

Соответственно, побитовое произведение чисел 31 и 17 даст 17, так как 31 это 00011111 , а 17 это 00010001

00011111
00010001
↓↓↓↓↓↓↓↓
00010001

Побитовое произведение чисел 35 и 15 равно 3.

00100011
00001111
↓↓↓↓↓↓↓↓
00000011

Аналогично работает операция побитового ИЛИ (оператор |), за исключением того, что она логически суммирует соответствующие биты чисел без переноса.

Например,

Char a = 15; char b = 11; char c = a | b; printf("%d", c);

выведет 15, так как 15 это 00001111 , а 11 это 00001011

00001111
00001011
↓↓↓↓↓↓↓↓
00001111

Побитовое ИЛИ для чисел 33 и 11 вернёт 43, так как 33 это 00100001 , а 11 это 00001011

00100001
00001011
↓↓↓↓↓↓↓↓
00101011

Побитовое отрицание (оператор ~) работает не для отдельного бита, а для всего числа целиком. Оператор инверсии меняет ложь на истину, а истину на ложь, для каждого бита. Например,

Char a = 65; char b = ~a; printf("%d", b);

Выведет -66, так как 65 это 01000001 , а инверсия даст 10111110

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

Char a = 107; char b = ~a + 1; printf("a = %d, -a = %d", a, b);

Исключающее ИЛИ (оператор ^) применяет побитово операцию XOR. Например, для чисел

Char a = 12; char b = 85; char c = a ^ b; printf("%d", c);

будет выведено 89, так как a равно 00001100 , а b равно 01010101 . В итоге получим 01011001

Иногда логические операторы && и || путают с операторами & и |. Такие ошибки могут существовать в коде достаточно долго, потому что такой код в ряде случаев будет работать. Например, для чисел 1 и 0. Но так как в си истиной является любое ненулевое значение, то побитовое умножение чисел 3 и 4 вернёт 0, хотя логическое умножение должно вернуть истину.

Int a = 3; int b = 4; printf("a & b = %d\n", a & b); //выведет 0 printf("a && b = %d\n", a && b);//выведет не 0 (конкретнее, 1)

Операции побитового сдвига

О пераций сдвига две – битовый сдвиг влево (оператор <<) и битовый сдвиг вправо (оператор >>). Битовый сдвиг вправо сдвигает биты числа вправо, дописывая слева нули. Битовый сдвиг влево делает противоположное: сдвигает биты влево, дописывая справа нули. Вышедшие за пределы числа биты отбрасываются.

Например, сдвиг числа 5 влево на 2 позиции

00000101 << 2 == 00010100

Сдвиг числа 19 вправо на 3 позиции

00010011 >> 3 == 00000010

Независимо от архитектуры (big-endian, или little-endian, или middle-endian) числа в двоичном виде представляются слева направо, от более значащего бита к менее значащему. Побитовый сдвиг принимает два операнда – число, над которым необходимо произвести сдвиг, и число бит, на которое необходимо произвести сдвиг.

Int a = 12; printf("%d << 1 == %d\n", a, a << 1); printf("%d << 2 == %d\n", a, a << 2); printf("%d >> 1 == %d\n", a, a >> 1); printf("%d >> 2 == %d\n", a, a >> 2);

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

Float b = 10.0f; float c = (float) (*((unsigned int*)&b) >> 2); printf("%.3f >> 2 = %.3f", b, c);

Но мы, конечно же, получим не 5.0f, а совершенно другое число.

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

Unsigned int ua = 12; signed int sa = -11; printf("ua = %d, ua >> 2 = %d\n", ua, ua >> 2); printf("sa = %d, sa >> 2 = %d\n", sa, sa >> 2); printf("(unsigned) sa = %u, sa >> 2 = %u\n", sa, sa >> 2); printf("sa = %d, ((unsigned) sa) >> 2 = %d", sa, ((unsigned) sa) >> 2);

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

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

Int a = 10; int b = 1; a >>= 3; a ^= (b << 3); и т.д.

Примеры

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

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

Пусть имеется число 9

00001001

Нужно узнать, выставлен ли бит на позиции 3 (начиная с нуля). Для этого умножим его на число, у которого все биты равны нулю, кроме третьего:

00001001 & 00001000 = 00001000

Теперь узнаем значение бита в позиции 6

00001001 & 01000000 = 00000000

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

#include #include #include int checkbit(const int value, const int position) { int result; if ((value & (1 << position)) == 0) { result = 0; } else { result = 1; } return result; } void main() { int a = 3; size_t len = sizeof(int) * CHAR_BIT; size_t i; for (i = 0; i < len; i++) { printf("%d", checkbit(a, i)); } _getch(); }

Заметьте, что в функции условие записано так

(value & (1 << position)) == 0

Потому что без скобок сначала будет вычислено равенство нулю и только потом выполнено умножение.

Value & (1 << position) == 0

Функцию можно упростить

Int checkbit(const int value, const int position) { return ((value & (1 << position)) != 0); }

Функция, которая выставляет бит на n-й позиции в единицу.

Известно, что логическое сложение любого бита с 1 будет равно 1. Так что для установки n-го бита нужно логически сложить число с таким, у которого все биты, кроме нужного, равны нулю. Как получить такое число, уже рассмотрено.

Int setbit(const int value, const int position) { return (value | (1 << position)); }

Функция, которая устанавливает бит на n-й позиции в ноль.

Для этого нужно, чтобы все биты числа, кроме n-го, не изменились. Умножим число на такое, у которого все биты равны единице, кроме бита под номером n. Например

0001011 & 1110111 = 0000011

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

Int unsetbit(const int value, const int position) { return (value & ~(1 << position)); }

Функция, изменющая значение n-го бита на противоположное.

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

Int switchbit(const int value, const int position) { return (value ^ (1 << position)); }

Проверка

#include #include #include int checkbit(const int value, const int position) { return ((value & (1 << position)) != 0); } int setbit(const int value, const int position) { return (value | (1 << position)); } int unsetbit(const int value, const int position) { return (value & ~(1 << position)); } int switchbit(const int value, const int position) { return (value ^ (1 << position)); } void printbits(int n) { //CHAR_BIT опеределён в библиотеке limits.h //и хранит число бит в байте для данной платформы size_t len = sizeof(int)* CHAR_BIT; size_t i; for (i = 0; i < len; i++) { printf("%d", checkbit(n, i)); } printf("\n"); } void main() { int a = 3; size_t len = sizeof(int) * CHAR_BIT; size_t i; printbits(a); a = setbit(a, 5); printbits(a); a = unsetbit(a, 5); printbits(a); a = switchbit(a, 11); printbits(a); a = switchbit(a, 11); printbits(a); _getch(); }

Битовые флаги

Расммотрим синтетический пример. Пусть у нас есть три логические переменные, и нам нужно вывести определённое значение в зависимости от всех этих переменных сразу. Очевидно, что может быть 2 3 возможных вариантов. Запишем это условие в виде ветвления:

#include int main() { unsigned char a, b, c; a = 1; b = 0; c = 0; if (a) { if (b) { if (c) { printf("true true true"); } else { printf("true true false"); } } else { if (c) { printf("true false true"); } else { printf("true false false"); } } } else { if (b) { if (c) { printf("false true true"); } else { printf("false true false"); } } else { if (c) { printf("false false true"); } else { printf("false false false"); } } } _getch(); return 0; }

Мы получили 8 ветвей. Пусть теперь нам понадобилось добавить ещё одно условие. Тогда число ветвей удвоится, и программа станет ещё сложней для понимания и отладки. Перепишем пример.

Если каждое из наших логичесих значений сдвинуть на своё число бит влево и логически сложить, то мы получим свою уникальную комбинацию бит в зависимоти от значений a, b и c:

#include #include void printbits (int n) { int i; for (i = CHAR_BIT - 1; i >= 0; i--) { printf("%d", (n & (1 << i)) != 0); } printf("\n"); } int main() { unsigned char a, b, c; unsigned char res; a = 1; b = 0; c = 0; res = c | b << 1 | a << 2; printbits(res); a = 0; b = 1; c = 1; res = c | b << 1 | a << 2; printbits(res); a = 1; b = 0; c = 1; res = c | b << 1 | a << 2; printbits(res); _getch(); return 0; }

Используем этот подход к нашей задаче и заменим ветвеление на switch:

#include int main() { unsigned char a, b, c; unsigned char res; a = 1; b = 0; c = 0; res = c | b<< 1 | a << 2; switch (res) { case 0b00000000: printf("false false false"); break; case 0b00000001: printf("false false true"); break; case 0b00000010: printf("false true false"); break; case 0b00000011: printf("false true true"); break; case 0b00000100: printf("true false false"); break; case 0b00000101: printf("true false true"); break; case 0b00000110: printf("true true false"); break; case 0b00000111: printf("true true true"); break; } _getch(); return 0; }

Этот метод очень часто используется для назначения опций функций в разных языках программирования. Каждый флаг принимает своё уникальное название, а их совместное значение как логическая сумма всех используемых флагов. Например, библиотека fcntl.

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

Таким образом, неравнозначность двух высказываний Х1 и Х2 называют такое высказывание Y, которое истинно тогда и только тогда, когда одно из этих высказываний истинно, а другое ложно.

Определение данной операции может быть записано в виде таблицы истинности (таблица 6):

Таблица 6 – Таблица истинности операции «ИСКЛЮЧАЮЩЕЕ ИЛИ»

Как видно из таблицы 6, логика работы элемента соответствует его названию.

Это тот же элемент «ИЛИ» с одним небольшим отличием. Если значение на обоих входах равно логической единице, то на выходе элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ», в отличие от элемента «ИЛИ», не единица, а ноль.

Операция «ИСКЛЮЧАЮЩЕЕ ИЛИ» фактически сравнивает на совпадение два двоичных разряда.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет своё название и обозначение (таблица 7).

Таблица 7 – Основные логические операции

1. Порядок выполнения логических операций в сложном логическом выражении

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

При вычислении значения логического выражения принят определённый порядок выполнения логических операций.

1. Инверсия.

2. Конъюнкция.

3. Дизъюнкция.

4. Импликация.

5. Эквивалентность.

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

1. Логические выражения и таблицы истинности

   1. Логические выражения

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

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

Запишем в форме логического выражения составное высказывание «(2·2=5 или 2∙2=4) и (2∙2≠5 или 2∙2 ≠4)».

Проанализируем составное высказывание. Оно содержит два простых высказывания:

А = «2 2=5»-ложно (0),

В = «2 2=4»-истинно (1).

Тогда составное высказывание можно записать в следующей форме:

«(А или В ) и (Ā или В )».

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

инверсия, конъюнкция, дизъюнкция.

Для изменения указанного порядка могут использоваться скобки:

F = (A v В ) & (Ā v В ).

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

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

F = (A v В) & (Ā v В) = (0 v 1) & (1 v 0) = 1 & 1 = 1.

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

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

Простые высказывания обозначаются переменными (например, A и B).

При построении таблиц истинности целесообразно руководствоваться определённой последовательностью действий:

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

количество строк = 2 n .

В нашем случае логическая функция

имеет 2 переменные и, следовательно, количество строк в таблице истинности должно быть равно 4;

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

В нашем случае количество переменных равно двум: А и В, а количество логических операций - пяти (таблица 8), то есть количество столбцов таблицы истинности равно семи;

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

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

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

Таблица 8 – Таблица истинности логической функции

Бит — это минимальная единица измерения объёма информации, так как она хранит одно из двух значений — 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 логические операции. Используя эти логические операции, мы можем получить любой возможный результат. Подробно об использовании логических операций в С++ читаем .