О битовых операциях. Что такое исключающее или.

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

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

a	b	a∧b
1
	1
1	1	1

Ссылка

a	b	a∨b
1		1
	1	1
1	1	1

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

a	b	a⊕b
1		1
	1	1
1	1

Влияние

a	b	a→b
		1
1
	1	1
1	1	1

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

a	b	ab
		1
1
	1
1	1	1

тире Шеффера

a	b	a∣b
		1
1		1
	1	1
1	1

Прикосновение Пирса

a	b	a↓b
		1
1
	1
1	1

Отказ

В программировании:

• Конъюнкция = AND = И = ∧ = &
• Дизъюнкция = OR = ИЛИ = ∨ = |
• Сложение по модулю 2 = XOR = ИСКЛЮЧАЮЩЕЕ ИЛИ = ⊕ = ~
• Отрицание = NOT = НЕ = ¬ = !

Практические применения

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

1. увеличение размера регистров, в которых битовые операции выполняются не по одной, а сразу на множестве 8, 16, 32, 64 битах
2. экспериментальные устройства, где обобщают битовые операции с двоичной системы, на троичные и прочие системы счисления (так например, разработана теория работы с четверичной системой (ДНК-компьютер), так же делаются исследования в области квантового компьютера).

Физическая реализация битовых операций

Реализация побитовых операций в принципе может быть любой: механической (включая гидравлическую и пневматическую), химической, термической, электрической, магнитной и электромагнитной (диапазоны — ИК, видимая оптика, УФ и далее с уменьшением длины волны), а также в виде комбинаций, например, электромеханики.

В первой половине 20-го века до изобретения транзисторов использовались электромеханические реле и электронные лампы.

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

Наиболее распространенными электронными реализациями поразрядных операций с транзисторами являются резисторно-транзисторная логика (RTL), диодно-транзисторная логика (DTL), логика с эмиттерной связью (ESL), транзисторно-транзисторная логика (TTL), N-MOS логика, КМОП логика и т.д.

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

Схемы аппаратной логики

Результат операции ИЛИ-НЕ или ИЛИ всех битов двоичного регистра проверяет, равно ли значение регистра нулю или нет; результат операции исключающего ИЛИ двух регистров проверяет, соответствуют ли их значения друг другу.

Битовые операции используются в генераторах сигналов и графических адаптерах; их роль была особенно велика в адаптере EGA для 16-цветных операций; разумное сочетание логики аппаратного обеспечения адаптера с логическими инструкциями центрального процессора позволяет считать EGA первым в истории графическим ускорителем.

Использование в программировании

Благодаря своей реализации в цифровом логическом блоке (ALU) процессора, многие операции с битами регистра в низкоуровневых языках доступны аппаратно. Большинство процессоров реализуют регистр NOT как инструкцию, регистр AND, OR, исключительное OR, проверку нуля (см. выше), три типа сдвига битов и циклический сдвиг битов.

Функция регистра AND используется для:

• проверки бита на 0 или 1
• установки 0 в указанный бит (сброса бита)

Функция регистра OR используется для:

Установка 1 в определенный бит.

Функция исключающего ИЛИ используется для инвертирования битов регистра путем маскирования.

Сдвиг влево/вправо используется для умножения/инвертирования на 2 и разделения битов.

Например, в сетевых технологиях Интернета для определения принадлежности адреса к подсети используется операция AND между значением IP-адреса и значением маски подсети.

Булева логика

В булевой логике импликация — это функция двух переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества>. Результат также принадлежит множеству>. Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений ,1 может использоваться любая другая пара подходящих символов, например false,true ,\operatorname>или F,T или ‘ложный’, ‘истинный’.

Импликация как булева функция ложна только в том случае, если предпосылка истинна, а импликация ложна. Другими словами, импликация A→B является сокращением для выражения ¬A∨B.

прямое умозаключение (от a к b) (материальное умозаключение, условное материальное умозаключение).

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

А — босс. Он может приказать «работать» (1) или сказать: «Делай, что хочешь» (0). Б — подчиненный. Он может работать (1) или ничего не делать (0).

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

Обратная импликация (из b в a, A∨(¬B)).

Обратная энтитема — это отрицание (негация, реверсия) инкрементного познания (от 0 до 1, приращение).

Отрицание (инверсия, отрицание) прямой импликации

Отрицание (реверсия, негация) обратной импликации (¬A∧B), облегчение кредита в .

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

Введение

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

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

• | (Побитовое ИЛИ (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₂ή 55.₁₀.

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

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

Пример работы побитового AND в выражениях 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₂, ή 36₁₀.

Оператор побитового AND можно использовать для проверки того, является ли число четным или нечетным. Для целых чисел, если младший значащий бит равен 1, то число нечетное (на основе преобразования двоичных чисел в десятичные). Зачем мне это нужно, если я могу просто использовать %2? На моем компьютере, например, &1 работает на 66% быстрее. Я могу сказать, что это довольно большой прирост производительности.

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

Оператор XOR называется ^.

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

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

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

String msg = «This is a message»; char message = msg.toCharArray(); String key = «.*)»; String encryptedString = new String(); for(int i = 0; i

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

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

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

Результат зависит от состояния бита. Если он находится в состоянии ноль, то результатом операции будет единица, и наоборот. Это очень просто.

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

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

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

Выделение краев и градиентов.

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

Схема для выполнения выделения и усечения краев.

Теория — это хорошо, но вы должны применять ее на практике ЗДЕСЬ.

Классификация логических элементов

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

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

В зависимости от типа используемых материалов различают следующие виды стружки:

1. Диодно-резисторная логика. Использование схем, разработанных по этой технологии, возможно только с полупроводниковыми триодами. Для самостоятельного применения этих элементов характерны большие потери.
2. Диодно-транзисторная логика. Операции при этой технологии реализуются посредством диодных цепей, а усиление и инверсия сигнала происходят благодаря транзистору.
3. Резисторно-транзисторная логика. Данный класс чипов базируется на резисторах и биполярных транзисторах.
4. Транзисторно-транзисторная логика. За триодом, выполняющим логическую операцию, подключают выходной инвертор для четкости сигнала на выходе.

Примеры основных логических элементов

Микросхемы логических действий выполняют основные функции:

• конъюнкция — умножение;
• дизъюнкция — сложение;
• инверсия — отрицание;
• сложение по модулю 2.

Логический элемент «И»

Микросхема «И» устанавливает связь с входной информацией. Микросхема «И» имеет 2-8 входов и один выход.

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

Логический элемент «ИЛИ»

Сложение входных данных выполняется элементом ИЛИ. Это устройство может иметь 2 или более входов и только один выход.

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

Логический элемент «НЕ»

Операция отрицания выполняется элементом ‘NOT’. Поскольку он имеет один вход и один выход, его называют инвертором.

Характерной особенностью элемента NOT является инверсия входной информации. Логическая единица на входе приводит к логическому нулю, и наоборот, ноль на входе приводит к единице.

Логический элемент «И-НЕ»

«И-НЕ» имеет функцию отрицания результата конъюнкции. Название происходит от начала элемента: «И-НЕ» — это элемент «И», дополненный элементом «НЕ». И-НЕ», таким образом, выполняет обратную функцию элемента «И».

Логический элемент «ИЛИ-НЕ»

Комбинация ‘OR-NE’ выполняет функцию отрицания дизъюнкции. Этот элемент противоположен элементу ИЛИ, т.е. входные и выходные значения этих элементов также обратны друг другу.

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

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

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

Обозначения логических элементов на схеме

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

Элемент ИЛИ обозначается функцией умножения, как в ИС: «2И» = 2 входа, «3И» = 3 входа и т.д:

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

На рисунке показан пример символа «2I-NE»:

Символ «2I-NE» имеет следующее значение:

Исключающее ИЛИ» обычно представляется следующим образом:

Экономия памяти

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

// храним флаги как 1 бит // макросы #define B_TRUE(bp,bb) (bp) |= (bb) #define B_FALSE(bp,bb) (bp) &= ~(bb) #define B_READ(bp,bb) bool((bp) & (bb)) // так мы храним наши флаги, значения обязательно в виде степени двойки! #define B_FLAG_1 1 #define B_FLAG_2 2 #define B_LED_STATE 4 #define B_BUTTON_STATE 8 #define B_BUTTON_FLAG 16 #define B_SUCCESS 32 #define B_END_FLAG 64 #define B_START_FLAG 128 // в этом байте мы храним 8 бит байта boolPack1 = 0; void setup()>void loop()

// пример упаковки битовых флагов в байты // с помощью функций Arduino byte myFlags = 0; // все флаги в false // вы можете назвать // числа в порядке 0-7 #define FLAG1 0 #define FLAG2 1 #define FLAG3 2 #define FLAG4 3 #define FLAG5 4 #define FLAG6 5 #define FLAG7 6 #define FLAG8 7 void setup()>void loop()<>

// вариант упаковки флагов в массив. ЛУЧШЕ И УДОБНЕЕ ПРЕДЫДУЩИХ ПРИМЕРОВ! #define NUM_FLAGS 30 // количество флагов byte flagsNUM_FLAGS / 8 + 1; // массив сжатых флагов // ============== МАКРОСЫ ДЛЯ РАБОТЫ С ПАЧКОЙ ФЛАГОВ ============== // поднять флаг (пачка, номер) #define setFlag(flag, num) bitSet(flag(num)>>3, (num) & 0b111) // опустить флаг (пачка, номер) #define clearFlag(flag, num) bitClear(flag(num)>>3, (num) & 0b111) // записать флаг (пачка, номер, значение) #define writeFlag(flag, num, state) ((state) ? setFlag(flag, num) : clearFlag(flag, num)) // прочитать флаг (пачка, номер) #define readFlag(flag, num) bitRead(flag(num)>>3, (num) & 0b111) // опустить все флаги (стек) #define clearAllFlags(flag) memset(flag, 0, sizeof(flag)) // поднять все флаги (стек) #define setAllFlags(flag) memset(flag, 255, sizeof(flag)) // ============== MACROSS TO WORK WITH FLAG PAGE ============== void setup()void loop()

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

Пример сжатия 1

Таким же образом можно упаковать любые другие данные в другие размеры для удобства хранения или сжатия. Например: RRRRRRRGGGG GGGBBBB. Мы сжимаем и упаковываем: для каждого цвета есть три переменные, r, g, b :

“Трюки” с битами

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

Сбросить ритм

Перемотайте один бит слева направо, т.е. сформируйте последовательность 0b10000000, 0b010000, 0b00100000, 0b00010000, 0b00001000, 0b00000100, 0b000010, 0b000001, 0b10000000, или 128, 64, 32, 16, 8, 4, 2, 1, 128

Установка n-го бита

Деактивация n-го бита

инверсия n-го бита

Округление до следующей степени двойки

unsigned int v; // работает только с 32 битными числами v--; v |= v>>1; v |= v>>2; v |= v>>4; v |= v>>8; v |= v>>16; v++;

Возьмите максимальное целое число

int maxInt = ~(1>1;

Получить минимальное целое число

int minInt = 1 
Умножить на 2
Разделить на 2
Умножение на m-ю степень двойки
Деление на m-ю степень двойки
Баланс разделения
n & 0b1; // на 2 n & 0b11; // на 4 n & 0b111; // на 8 // .
Проверка равенства
(a ^ b) == 0; // a == b !(a ^ b) // Использовать внутри if()
проверка равенства (кратно 2)
Обмен ценностями
a = a ^ b ^ (b = a),
проверить наличие одинаковой метки
Обменные знаки
i = ~i + 1; // или i = (i ^ -1) + 1; // i = -i
Возврат 2 n
Это сила 2
остаток от деления на 2 n на m
среднее арифметическое
(x + y)>>1; ((x ^ y)>>1) + (x & y),
Извлечение m-го бита из n (от младшего к старшему)
Получение m-го бита из n (от младшего до старшего)
Проверьте, включен ли n-й бит
Выделите самый правый активированный бит
Выберите самый правый деактивированный бит
Выберите самый правый включенный бит
Выберите самый правый деактивированный бит
Получение отрицательного значения
если (x == a) x = b; если (x == b) x = a
Изменить соседние биты
((n & 10101010)>>1) | ((n & 01010101) 
Быстрый обратный квадратный корень
float Q_rsqrt( float number )conv = ; conv.i = 0x5f3759df - ( conv.i>>1 ); conv.f *= 1.5 - number * 0.5 * conv.f * conv.f; return conv.f;>
Быстрый квадратный корень (2 байта)
uint16_t root2(uint16_t x)>= 1; if (x>= b)m>>= 2;>return y;>
Быстрый квадратный корень (4 байта)
uint32_t root4(uint32_t x)= 1ul; if (x>= b)m>>= 2ul;>return y;>
Разделить плавающее число на битовый массив (unsigned uint32_t)
Приоритет операций
Чтобы избежать образования круглых скобок, необходимо знать порядок старшинства операций. На языке C++ это выглядит следующим образом:

Набор GyverKIT – большой стартовый набор Arduino моей разработки, продаётся в России
Каталог ссылок на дешёвые Ардуины, датчики, модули и прочие железки с AliExpress у проверенных продавцов
Подборка библиотек для Arduino, самых интересных и полезных, официальных и не очень
Полная документация по языку Ардуино, все встроенные функции и макросы, все доступные типы данных
Сборник полезных алгоритмов для написания скетчей: структура кода, таймеры, фильтры, парсинг данных
Видео уроки по программированию Arduino с канала “Заметки Ардуинщика ” – одни из самых подробных в рунете
Поддержать автора за работу над уроками
Обратная связь – сообщить об ошибке в уроке или предложить дополнение по тексту (email protected)