Исключающее «или»

Введение

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

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

Определение

Назовем A и B двумя рассматриваемыми операндами. Согласимся представлять их стоимость следующим образом:

1 = ИСТИНА

0 = ЛОЖЬ

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

Как мы видим, логический оператор XOR, или исключающее ИЛИ, может быть определен следующим предложением:

Результат — ИСТИНА, если один и только один из операндов А и В ИСТИНА.

или же

Результат будет ИСТИНА, если два операнда A и B имеют разные значения.

или же

Результат — ИСТИНА, если нечетное количество входов истинно (это особенно применимо, когда два или более логических оператора XOR соединены каскадом (генераторы битов четности )

Он отличается от включающего оператора ИЛИ, потому что дает ЛОЖНЫЙ результат, когда А и В одновременно ИСТИНА. Его символ также отличается от включающего оператора ИЛИ, символ которого представляет собой просто «ПЛЮС»: «+».

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

С логическими элементами И / ИЛИ A XOR B = (A AND не B) OR (не A AND B).

Функция XOR является примером функции четности .

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

Основные бинарные операции, расположенные в порядке уменьшения приоритета:

• * — умножение;
• — деление;
• + — сложение;
• — — вычитание;
• % — остаток от целочисленного деления.

Основные унарные операции:

• ++ — инкрементирование (увеличение на 1);
• –– — декрементирование (уменьшение на 1);
• — — изменение знака.

Результат вычисления выражения, содержащего операции инкрементирования или декрементирования, зависит от того, где расположен знак операции (до объекта или после него). Если операция расположена до объекта, то сначала происходит изменение значения переменной на 1, а потом это значение используется для выполнения следующих операций. Если операция ++ или — расположена после переменной, то сначала выполняется операция, а потом значение переменной изменяется на 1.Пример:

Бинарные арифметические операции могут быть объединены с операцией присваивания:

• объект *= выражение; // объект = объект * выражение
• объект /= выражение; // объект = объект / выражение
• объект += выражение; // объект = объект + выражение
• объект -= выражение; // объект = объект — выражение
• объект %= выражение; // объект = объект % выражение

Логический оператор OR

Синтаксис:Операнд_1 OR Операнд_2

Оператор OR выполняет логическую дизъюнкцию.

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

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

Оператор OR можно использовать для нескольких операндов:

(5

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

Операторы AND и OR можно комбинировать:

((5

Оператор логического ИЛИ |

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

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

В следующем примере правый операнд оператора является вызовом метода, который выполняется независимо от значения левого операнда:

также вычисляет логическое ИЛИ для своих операндов, но не вычисляет правый операнд, если левый операнд имеет значение .

Для операндов целочисленных типов оператор вычисляет своих операндов.

Логические схемы «ИЛИ» на транзисторах

На рис. 5, а приведена схема ИЛИ на транзисторах для положительной логики. Схема имеет два входа А и В и один выход. 

Рис. 5. Схема ИЛИ на транзисторах

Транзисторы типа n — p — n соединены параллельно и играют роль ключей. При наличии на входе сигнала 0 соответствующий транзистор закрыт напряжением смещения Е_см; если на второй вход подан сигнал 1 с напряжением больше, чем Е_см, то второй транзистор открыт и на выходе возникает сигнал 1. Схема ИЛИ для отрицательной логики (рис. 5, б) построена по такому же принципу, однако используются транзисторы типа р — n — р и изменена полярность сигналов и напряжений смещения и питания.

Возможность перегрузки оператора

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

Определяемый пользователем тип не может перегружать условные логические операторы и . При этом, если определяемый пользователем тип каким-либо образом перегружает операторы true и false и операторы и , операция или может быть применена для операндов этого типа. Дополнительные сведения см. в разделе в Спецификации языка C#.

Логические операции

Логические операции делятся на две группы:

• условные;
• побитовые.

Условные логические операции чаще всего используются в операциях проверки условия if и могут выполняться над любыми объектами. Результат условной логической операции:

• 1 если выражение истинно;
• если выражение ложно.

Вообще, все значения, отличные от нуля, интерпретируются условными логическими операциями как истинные.
Основные условные логические операции:

• && — И (бинарная) — требуется одновременное выполнение всех операций отношения;
• || — ИЛИ (бинарная) — требуется выполнение хотя бы одной операции отношения;
• ! — НЕ (унарная) — требуется невыполнение операции отношения.

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

• & конъюнкция (логическое И) — бинарная операция, результат которой равен 1 только когда оба операнда единичны (в общем случае — когда все операнды единичны);
• | дизъюнкция (логическое ИЛИ) — бинарная операция, результат которой равен 1 когда хотя бы один из операндов равен 1;
• ~ инверсия (логическое НЕ) — унарная операция, результат которой равен 0 если операнд единичный, и равен 1, если операнд нулевой;
• ^ исключающее ИЛИ — бинарная операция, результат которой равен 1, если только один из двух операндов равен 1 (в общем случае если во входном наборе операндов нечетное число единиц).

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

Пример:

1234567

unsigned char a = 14;    // a = 0000 1110unsigned char b = 9;     // b = 0000 1001unsigned char c, d, e, f;c = a & b;               // c = 8 = 0000 1000d = a | b;               // d = 15 = 0000 1111e = ~a;                  // e = 241 = 1111 0001f = a ^ b;               // f = 7 = 0000 0111

маскирование битов

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

12

unsigned char a = 3;a = a | 0x04;  // a = 7, бит 2 установлен

12

unsigned char a = 3;a = a & (~0x02);  // a = 1, бит 1 сброшен

• объект &= выражение; // объект = объект & выражение
• объект |= выражение; // объект = объект | выражение
• объект ^= выражение; // объект = объект ^ выражение

Логическое НЕ (!)

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

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

<?php
 
  $a1 = 10;
 
  var_dump((11 == 11));   // true
  
  // оператора ! инвертирует значение
  var_dump(!(11 == 11));  // false
  
  // преобразует в логическое значение
  var_dump(!!$a1);      // true

?>

С этой темой смотрят:

• Выражения и операторы
• Арифметические операторы
• Операторы сравнения
• Побитовые операторы

Альтернативные символы

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

+, знак плюс, преимущество которого состоит в том, что все обычные алгебраические свойства математических колец и полей можно использовать без лишних слов; но знак плюс также используется для инклюзивной дизъюнкции в некоторых системах обозначений; обратите внимание, что исключительная дизъюнкция соответствует сложению по модулю 2, которое имеет следующую таблицу сложения, явно изоморфную приведенной выше:

• ⊕{\ displaystyle \ oplus}, измененный знак плюса; этот символ также используется в математике для прямой суммы алгебраических структур
• J, как в J pq
• Инклюзивный символ дизъюнкции ( ), который каким-либо образом модифицируется, например
  ∨{\ Displaystyle \ lor}
  • ∨_{\ displaystyle {\ underline {\ lor}}}
  • ∨˙{\ displaystyle {\ dot {\ vee}}}
• ^, каретка , используемая в нескольких языках программирования , таких как C , C ++ , C # , D , Java , Perl , Ruby , PHP и Python , обозначающая побитовый оператор XOR; не используется вне контекста программирования, потому что его слишком легко спутать с другими вариантами использования каретки
• , иногда пишется как
  • > <
  • > — <
• = 1, в символике IEC

Некоторые математические свойства

• В⊕Взнак равно{\ Displaystyle A \ oplus A = 0}(легко проверить по таблице 2 возможных значения A )
• В⊕знак равноВ{\ displaystyle A \ oplus 0 = A}
• В⊕1знак равноВ¯{\ displaystyle A \ oplus 1 = {\ bar {A}}}
• В⊕В¯знак равно1{\ displaystyle A \ oplus {\ bar {A}} = 1}
• Коммутативность В⊕Bзнак равноB⊕В{\ Displaystyle A \ oplus B = B \ oplus A}
• Ассоциативность где — функция совпадения.В⊕(B⊕ПРОТИВ)знак равно(В⊕B)⊕ПРОТИВзнак равноВ⊙(B⊙ПРОТИВ)знак равно(В⊙B)⊙ПРОТИВ{\ Displaystyle A \ oplus (B \ oplus C) = (A \ oplus B) \ oplus C = A \ odot (B \ odot C) = (A \ odot B) \ odot C}⊙{\ displaystyle \ odot}
• В⊕Bзнак равно(В+B)⊕В⋅B{\ Displaystyle A \ oplus B = (A + B) \ oplus A \ cdot B}
• В⊕Bзнак равно{\ displaystyle A \ oplus B = 0}если и только если (в некотором смысле, это немедленно, в другом, используя свойство ассоциативности и владение: )Взнак равноB{\ displaystyle A = B}В⊕знак равноВ{\ displaystyle A \ oplus 0 = A}
• В⊕Bзнак равноВ¯⋅B+В⋅B¯{\ displaystyle A \ oplus B = {\ bar {A}} \ cdot B + A \ cdot {\ bar {B}}}Мы выводим из этого свойства: или даже снова: и даже снова:В⊕B¯знак равноВ⋅B+В¯⋅B¯{\ displaystyle {\ overline {A \ oplus B}} = A \ cdot B + {\ bar {A}} \ cdot {\ bar {B}}}В⊕B¯знак равноВ¯⊕Bзнак равноВ⊕B¯{\ displaystyle {\ overline {A \ oplus B}} = {\ overline {A}} \ oplus B = A \ oplus {\ overline {B}}}В⊕Bзнак равноВ¯⊕B¯{\ displaystyle A \ oplus B = {\ overline {A}} \ oplus {\ overline {B}}}
• В⊕Bзнак равноПРОТИВ{\ Displaystyle A \ oplus B = C}так иПРОТИВ⊕Bзнак равноВ{\ Displaystyle C \ oplus B = A}В⊕ПРОТИВзнак равноB{\ Displaystyle A \ oplus C = B}
• (В⊕B)⊕Bзнак равноВ{\ Displaystyle (A \ oplus B) \ oplus B = A} (Следствие первых двух свойств и ассоциативности — полезно в криптографии (см. Ниже))
• Набор {0; 1} с двумя законами внутренней композиции, исключающим ИЛИ и И, является конечным полем .

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

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

#include <stdio.h>

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 <stdio.h>
#include <limits.h>

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 <stdio.h>

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:

char *fp = "/home/ec2-user/file.txt";
int flag = O_RDWR | O_CREAT | O_TRUNC | O_APPEND;
int fd = open(fp, flag, 0644);

Q&A

Всё ещё не понятно? – пиши вопросы на ящик

Программирование [ | ]

В языках /C++ , Java , , Ruby , PHP , JavaScript , Python и т. д. битовая операция поразрядного дополнения обозначается символом « ^ », в языках Паскаль , Delphi , Ada , Visual Basic — зарезервированным словом xor , в языке ассемблера — одноимённой логической командой. При этом сложение по модулю 2 выполняется для всех битов левого и правого операнда попарно. Например,

Если

A
=
01100101
2
{\displaystyle a=01100101_{2}}

B
=
00101001
2
{\displaystyle b=00101001_{2}}
, начиная со стандарта C99 , оператор « ^ » над операндами логического типа возвращает результат применения логической операции XOR. В С++ оператор « ^ » для логического типа bool возвращает результат согласно описанным правилам, для остальных же типов производится его побитовое применение.

Обозначения[править | править код]

Запись может быть префиксной («польская запись») — знак операции ставится перед операндами, инфиксной — знак операции ставится между операндами и постфиксной — знак операции ставится после операндов. При числе операндов более 2 префиксная и постфиксная записи экономичнее инфиксной записи. Чаще всего встречаются следующие варианты записи:⊕2(a,b), a{\displaystyle \oplus _{2}(a,b),~a} ^ b, a⊕b,a⊕2b,a+2b,{\displaystyle b,~a\oplus b,a\oplus _{2}b,a+_{2}b,} a ≠ b, a≠b,(a,b)⊕2,a XOR b{\displaystyle a\neq b,(a,b)\oplus _{2},a~XOR~b}

В Юникоде есть символы для сложения по модулю 2: U+22BB ⊻ xor, U+2295 ⊕ circled plus и U+2A27 ⨧ plus sign with subscript two, U+2A52 ⩒ logical or with dot above, а также символ для суммы по модулю 2: U+2A0A ⨊ modulo two sum.

Связь с естественным языком

В естественном языке операция «сложение по модулю» эквивалентна двум выражениям:

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

Часто указывают на сходство между сложением по модулю 2 и конструкцией «либо … либо …» в естественном языке. Составное утверждение «либо A, либо B» считается истинным, когда истинно либо A, либо B, но не оба сразу; в противном случае составное утверждение ложно. Это в точности соответствует определению операции в булевой алгебре, если «истину» обозначать как 1{\displaystyle 1}, а «ложь» как {\displaystyle 0}.

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

1. A∨B{\displaystyle A\lor B} истинно, если истинно A{\displaystyle A} или B{\displaystyle B}, или оба сразу («хотя бы один из двух»).
2. A⊕B{\displaystyle A\oplus B} истинно, если истинно A{\displaystyle A} или B{\displaystyle B}, но не оба сразу («только один из двух»).

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

Программирование[править | править код]

В языках C/C++, Java, C#, Ruby, PHP, JavaScript, Python и т. д. битовая операция поразрядного дополнения обозначается символом «^», в языках Паскаль, Delphi, Ada, Visual Basic — зарезервированным словом xor, в языке ассемблера — одноимённой логической командой. При этом сложение по модулю 2 выполняется для всех битов левого и правого операнда попарно. Например,

если

a=011001012{\displaystyle a=01100101_{2}}

b=001010012{\displaystyle b=00101001_{2}}

то

a ^b=010011002{\displaystyle a{\hat {\ }}b=01001100_{2}}

Выполнение операции исключающее «или» для значений логического типа (true, false) производится в разных языках программирования по-разному. Например, в Delphi используется встроенный оператор XOR (пример: условие1 xor условие2). В языке C, начиная со стандарта C99, оператор «^» над операндами логического типа возвращает результат применения логической операции XOR. В C++ оператор «^» для логического типа bool возвращает результат согласно описанным правилам, для остальных же типов производится его побитовое применение.

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

Отношение к современной алгебре

Хотя операторы ( конъюнкция ) и ( дизъюнкция ) очень полезны в логических системах, они не позволяют получить более обобщаемую структуру следующим образом:
∧{\ Displaystyle \ клин}∨{\ Displaystyle \ lor}

Системы и являются моноидами , но ни одна из них не является группой . К сожалению, это препятствует объединению этих двух систем в более крупные структуры, такие как математическое кольцо .
({Т,F},∧){\ Displaystyle (\ {Т, F \}, \ клин)}({Т,F},∨){\ Displaystyle (\ {T, F \}, \ lor)}

Тем не менее, система , использующая исключающее или является абелева группа . Комбинация операторов и элементов over дает хорошо известное поле . Это поле может представлять любую логику, доступную с помощью системы, и имеет дополнительное преимущество арсенала инструментов алгебраического анализа для полей.
({Т,F},⊕){\ displaystyle (\ {T, F \}, \ oplus)} ∧{\ Displaystyle \ клин}⊕{\ displaystyle \ oplus}{Т,F}{\ displaystyle \ {T, F \}} F2{\ displaystyle F_ {2}}(∧,∨){\ Displaystyle (\ земля, \ лор)}

Более конкретно, если связать с 0 и с 1, можно интерпретировать логическую операцию «И» как умножение и операцию «исключающее ИЛИ» как сложение :
F{\ displaystyle F}Т{\ displaystyle T}F2{\ displaystyle F_ {2}}F2{\ displaystyle F_ {2}}

рзнак равноп∧q⇔рзнак равноп⋅q(мод2)рзнак равноп⊕q⇔рзнак равноп+q(мод2){\ displaystyle {\ begin {matrix} r = p \ land q & \ Leftrightarrow & r = p \ cdot q {\ pmod {2}} \\ r = p \ oplus q & \ Leftrightarrow & r = p + q {\ pmod {2}} \\\ end {matrix}}}

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

Булева алгебра

В булевой алгебре сложение по модулю 2 — это функция двух, трёх и более переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества {,1}{\displaystyle \{0,1\}}. Результат также принадлежит множеству {,1}{\displaystyle \{0,1\}}. Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений ,1{\displaystyle 0,1} может использоваться любая другая пара подходящих символов, например false,true{\displaystyle false,true} или F,T{\displaystyle F,T} или «ложь», «истина», но при этом необходимо доопределять старшинство, например, true>false{\displaystyle true>false}.

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

для бинарного сложения по модулю 2 (применяется в двоичных полусумматорах):55–61:

Правило: результат равен {\displaystyle 0}, если оба операнда равны; во всех остальных случаях результат равен 1{\displaystyle 1}.

для тернарного сложения по модулю 2 (применяется в двоичных полных сумматорах):

Правило: результат равен {\displaystyle 0}, если нет операндов, равных 1{\displaystyle 1}, либо их чётное количество.

Логический оператор AND

Синтаксис:Операнд_1 AND Операнд_2

Оператор AND выполняет логическую конъюнкцию.

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

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

Оператор AND можно использовать для нескольких операндов:

(5

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

В любом другом случае результатом будет False

Обратите внимание, что операнды заключаются в круглые скобки

Побитовое И (&), Побитовое ИЛИ (|), Сложение по модулю два (^)

Битовые операторы выполняют свои расчеты на уровне битов переменных. Они помогают решать широкий круг общих проблем программирования. Хорошую статью по битовым операциям можно найти на Википедии.

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

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

    0  0  1  1    операнд1
    0  1  0  1    операнд2
    ----------
    0  0  0  1    результат (операнд1 & операнд2)

В среде разработки Arduino тип int это 16-битное значение, таким образом оператор побитовое И между двумя int выражениями делает 16 одновременных И операций. Иллюстрация:

int a =  92;    // в двоичном виде: 0000000001011100
int b = 101;    // в двоичном виде: 0000000001100101
int c = a & b;  // результат:    0000000001000100, или 68 в десятичном представлении

Каждый бит значений a и b проходит операцию побитового И, в результате все 16 битов попадают в переменную c, полученное значение будет 01000100, что равносильно 65 в двоичном представлении.
Наиболее часто операция побитового И используется для выбора конкретного бит (или битов) от целого значения, часто называемая маска. См. пример ниже.

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

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

    0  0  1  1    операнд1
    0  1  0  1    операнд2
    ----------
    0  1  1  1    (операнд1 | операнд2) - результат

Пример использования операции побитового ИЛИ в фрагменте кода на C++:

int a =  92;    // в бинарном виде: 0000000001011100
int b = 101;    // в бинарном виде: 0000000001100101
int c = a | b;  // результат:    0000000001111101, или 125 в десятичном виде.

Пример программы

Основная область примернения операторов побитовое И/ИЛИ это операции чтение/записи в порт. В микроконтроллерах порт это 8-битовое число, через которое можно получить информацию о состоянии контактов. Записи в порт контролирует все контакты сразу.

PORTD является встроенной константой, которая относится к выходному состоянию цифровых выводов 0,1,2,3,4,5,6,7. Если в каком-то бите установлена 1, значит на выводе состояние HIGH. Вывод при этом должен быть установлен как выход командой pinMode(). Таким образом, если записать PORTD = B00110001; мы установим выводы 2,3 и 7 в состояние логической 1.

Наш алгоритм будет выглядеть вот так:

• Получить значение PORTD и очистить биты относящиеся к выводам, значение которые мы хотим изменить (с помощью побитового И).
• Скомбинировать значение PORTD с нашим новым значением (через операцию побитового ИЛИ).

int i;     // переменная счетчика
int j;
 
void setup(){
DDRD = DDRD | B11111100; 
// установить биты направлений для выводов с 2 по 7, 
// оставить нетронутыми для выводов 0 и 1 (xx | 00 == xx)
// это тоже самое что и оператор pinMode(pin, OUTPUT) для выводов с 2 по 7
Serial.begin(9600);
}
 
void loop(){
for (i=0; i<64; i++){
 
PORTD = PORTD & B00000011;  
// очистить биты с 2 по 7, оставить биты (а занчить и выводы) 0 и 1 неизмененными (xx & 11 == xx)
j = (i << 2);               
// сдвинуть переменную на два бита влево к пинам 2 -7, чтобы не затронуть пины 0 и 1
PORTD = PORTD | j;          
// скомбинирвать значение порта с новым значением
Serial.println(PORTD, BIN); 
// для отладки выведем значение порта в терминал
delay(100);
   }
}

побитовое XOR или исключающее ИЛИ (^)

Еще один побитовый оператор, немного похожий на обычное бинарное ИЛИ, но небольшим отлиием — он вернет 0, если оба бита будут равны 1. Обозначается символом ^.

    0  0  1  1    операнд1
    0  1  0  1    операнд2
    ----------
    0  1  1  0    (операнд1 ^ операнд2) - результат

Другими словами, после операции илсключающего ИЛИ будет 1 в том случае, если входные биты различны или оба равны 0.

Пример кода:

int x = 12;     // в бинарном представлении: 1100
int y = 10;     // в бинарном представлении: 1010
int z = x ^ y;  // в бинарном представлении: 0110, или десятчиная 6

Оператор ^ часто используется для переключения (т.е. чтобы изменить 0 на 1 или 1 на 0) каких-либо битов в цифровом представлении. Пример программы для переключения цифрового вывода 5.

void setup(){
DDRD = DDRD | B00100000; // установили цифровой вывод 5 как выход
Serial.begin(9600);
}

void loop(){
PORTD = PORTD ^ B00100000;  
// переключили бит 5 (цифровой вывод 5),
// остальные оставили нетронутыми
delay(100);
}

Оператор логического И &

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

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

В следующем примере правый операнд оператора является вызовом метода, который выполняется независимо от значения левого операнда:

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

Для операндов целочисленных типов оператор вычисляет своих операндов. Унарный оператор является оператором .

Связь с естественным языком[править | править код]

В естественном языке операция «сложение по модулю» эквивалентна двум выражениям:

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

Часто указывают на сходство между сложением по модулю 2 и конструкцией «либо … либо …» в естественном языке. Составное утверждение «либо A, либо B» считается истинным, когда истинно либо A, либо B, но не оба сразу; в противном случае составное утверждение ложно. Это в точности соответствует определению операции в булевой алгебре, если «истину» обозначать как 1{\displaystyle 1}, а «ложь» как {\displaystyle 0}.

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

1. A∨B{\displaystyle A\lor B} истинно, если истинно A{\displaystyle A} или B{\displaystyle B}, или оба сразу («хотя бы один из двух»).
2. A⊕B{\displaystyle A\oplus B} истинно, если истинно A{\displaystyle A} или B{\displaystyle B}, но не оба сразу («только один из двух»).

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

Сложение по модулю 2

Но в базовой реализации алгоритм крайне не стоек.

Алгоритм XOR-шифрования основан на применении бинарной логической операции исключающего или. В табличном представлении функция выглядит следующим образом:

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

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

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

Рассмотрим алгоритм XOR-шифрования более подробно:

1. На входе получаем указатели на исходный и результирующий файлы и строку пароля (которая не должна быть пустой).
2. Читаем очередной символ (байт) из исходного файла.
3. Применяем операцию XOR к прочитанному байту и очередному символу пароля.
4. Результат операции записываем в результирующий файл.
5. Если не достигнут конец исходного файла, переходим на шаг 2.

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

Необходимо реализовать процедуру:

procedure XOR_CoDec (const SourceFile, DestFile, Password: string);

Где в качестве параметров передаются:

SourceFile – имя исходного файла.

DestFile – имя результирующего файла.

Password – пароль.

Исключительное «или» на естественном языке

Дизъюнкция часто понимается исключительно на естественных языках . В английском языке дизъюнктивное слово «or» часто понимается исключительно, особенно когда оно используется с частицей «либо». Приведенный ниже пример на английском языке обычно понимается в разговоре как подразумевающий, что Мэри не одновременно певица и поэт.

1. Мэри — певица или поэтесса.

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

2. Мэри либо певица, либо поэт, либо и то, и другое.

3. Никто не ел ни риса, ни бобов.

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

Такое поведение английского «или» встречается и в других языках. Однако во многих языках есть дизъюнктивные конструкции, которые строго исключают друг друга, например, французский soit … soit .

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

И последняя
базовая операция работы с битами – исключающее ИЛИ (ее еще называют XOR). Она задается
оператором ^ и имеет такую
таблицу истинности:

Из нее видно,
что данная операция позволяет переключать биты числа, то есть, если они были
равны 0, то станут 1 и, наоборот, если были 1 – станут 0. Продемонстрируем это
на таком примере.

byte flags = 9;  //двоичный вид:  00001001
byte mask = 1;   //двоичный вид:  00000001
 
flags = (byte)(flags ^ mask);     //двоичная запись 00001000 (число 8)
System.out.println(flags);
 
flags ^= mask;    //двоичная запись 00001001 (число 9)
System.out.println(flags);

Интересной
особенностью операции XOR является отсутствие потерь данных при
ее работе. Что это значит? Смотрите, какую бы маску мы не взяли, дважды
примененная маска дает исходное число.

byte flags = 9;    //двоичный вид:  00001001
byte mask = 111;   //двоичный вид:  01101111
 
System.out.println(flags);
 
flags ^= mask;    //двоичная запись 01100110 (число 102)
System.out.println(flags);
 
flags ^= mask;    //двоичная запись 00001001 (число 9)
System.out.println(flags);

Это связано с
эффектом переключения бит, а значит, двойное переключение даст исходный
результат. Где этот эффект можно применить? Самое простое – в шифровании
данных. Например, у нас есть сообщение в виде строки, и маска – как
шифровальный ключ.

String msg = "Привет мир!";
byte key = 111;
 
System.out.println(msg);
 
char str = msg.toCharArray();
for(int i=;i < msg.length();++i)
    stri ^= key;
 
msg = new String(str);
System.out.println(msg);
 
for(int i=;i < msg.length();++i)
    stri ^= key;
 
msg = new String(str);
System.out.println(msg);

В частности по
такому принципу устроена защита по паролю в архиваторе zip. Причем, сам
пароль является ключом, который накладывается по XOR на
заархивированные данные.

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

Обозначения [ | ]

Запись может быть префиксной («польская запись ») — знак операции ставится перед операндами, инфиксной — знак операции ставится между операндами и постфиксной — знак операции ставится после операндов. При числе операндов более 2 префиксная и постфиксная записи экономичнее инфиксной записи. Чаще всего встречаются следующие варианты записи:
⊕
2
(a
,
b)
,
a
{\displaystyle \oplus _{2}(a,b),~a}
^
b
,
a
⊕
b
,
a
⊕
2
b
,
a
+
2
b
,
{\displaystyle b,~a\oplus b,a\oplus _{2}b,a+_{2}b,}
a ≠ b,
a
≠
b
,
(a
,
b)
⊕
2
,
a
X
O
R
b
{\displaystyle a\neq b,(a,b)\oplus _{2},a~XOR~b}

В таблице символов Юникод есть символы для сложения по модулю 2: XOR — U+22BB (⊻), CIRCLED PLUS — U+2295 (⊕) и PLUS SIGN WITH SUCSCRIPT TWO — U+2A27 (⨧), а также символ для суммы по модулю 2: MODULO TWO SUM — U+2A0A (⨊).

Похожие записи:

Как выставить зажигание с помощью стробоскопа? Сигнализация действия защиты и автоматики Подключение потолочного светильника со светодиодами Книги по ардуино Правильная пайка проводов паяльником Птф солярис