XOR только от ИЛИ И И

Question

Как выполнить битовую операцию XOR, если доступны только операции AND и OR?

Answer 1

Таблица правды для ИЛИ

  A  B  AND
  T  T  T
  T  F  F
  F  T  F
  F  F  F
  

Таблица правды для ИЛИ

  A  B  OR
  T  T  T
  T  F  T
  F  T  T
  F  F  F
  

Таблица правды для ИЛИ

  A  B  XOR
  T  T  F
  T  F  T
  F  T  T
  F  F  F
  

Итак, XOR похож на ИЛИ,за исключением того, что это ложно, если A и B истинны.

Итак, (A ИЛИ B) И (НЕ (A И B)), то есть (A ИЛИ B) И (A И НЕ B)

  A  B  OR  AND NAND [(A OR B) AND (A NAND B)]
  T  T  T    T    F        F
  T  F  T    F    T        T
  F  T  T    F    T        T
  F  F  F    F    T        F
  

Не уверен, что это можно сделать без NOT или NAND

Answer 2

"Системы ({T, F} и) и ({T, F} или) являются моноидами."

"Система ({T, F}, xor) является абелевойгруппа ", которая обладает свойством обратимости в отличие от моноидов.

Следовательно, 'и' и 'или' не могут создать операцию 'xor'.

Источник: https://en.wikipedia.org/wiki/Exclusive_or#Relation_to_modern_algebra

Answer 3

Если у вас есть арифметические операторы, такие как + и - в дополнение к побитовым AND (&) и OR (|), тогда вы можете сделать битовое XOR следующим образом:

int bitwise_XOR(int a, int b)
{
    return (a + b) - (a & b) - (a & b);
}

Причина, по которой это работает, заключается в том, что мы делаем полное добавление, которое эквивалентно XOR, когда сумма для каждой заданной позиции бита <= 1, а затем мы исправляем случай, когда генерируется перенос (1 +1) вычитая <code>2 * (a & b).

Обратите внимание, что это работает, даже если промежуточные члены переполняются, предполагая, что у нас есть "нормально себя ведущие" целые числа (дополнение 2, обход по модулю 2 для переполнения и т.д.).

Answer 4

Запись Википедии о XOR подробно описывает это.Вероятно, это хорошее первое место, чтобы проверить перед тем, как задавать SO-вопрос.

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

Answer 5

(a XOR b) = ((a OR b) - (a AND b)), или, другими словами, набор объединений минус набор пересечений.

Пример кода (в javascript):

var a = 5;
var b = 12;
var xor = (a | b) - (a & b); // result: 9

Answer 6

Создание моего собственного языка сценариев - ChrisScript - вам просто нужно что-то вроде:

#!/bin/chrish

bit XOR (bit A, bit B)
{
   bit notA;
   bit notB;

   IF (A == 0) notA = 1 ELSE notA = 0;
   IF (B == 0) notB = 1 ELSE notB = 0;

   F = ((A && notB) || (notA && B));

   RETURN F;
}

Даже без NOT, его можно подражать такНо это лучшее решение, которое вы получите без инвертора.Мне трудно поверить, что у вас нет какой-либо формы инвертора - какую среду сценариев вы используете?

Answer 7

В С: x ^ y = (x & ~y) | (~x & y)

Answer 8

Я уверен, что приведенная ниже формула верна:

a xor b = нет ((a и b) или нет (a + b))

Answer 9

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