Реализовать XOR в терминах ADD, SUB, AND и разветвить на равные / не равные? - PullRequest
Новая
       56

Реализовать XOR в терминах ADD, SUB, AND и разветвить на равные / не равные?

0 голосов
/ 12 декабря 2018

У меня был вопрос об использовании XOR в терминах ADD / SUB и ветвей: Реализовать операцию Xor между двумя числами, используя только следующие команды:

  1. Добавить
  2. Sub
  3. Ветвь, если она равна
  4. Ветвь, если она не равна
  5. И

Вы можете использовать регистры r3 и r4 в качестве дополнительного пробела.Предположим, что регистр r1 хранит первое число, а r2 хранит второе число

Ответы [ 2 ]

0 голосов
/ 12 декабря 2018

С SUB вы можете получить НЕ 

~a = ~0 - a

или, если используется два дополнения 

~a = -a - 1

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

XOR from NAND

t = a NAND b
a ^ b = (a NAND t) NAND (b NAND t)

В качестве альтернативы

Another way

a ^ b = (b NAND ~a) NAND (a NAND ~b)

, который можно перевести на что-то вроде этого 

r3 = ~0 - r1  # ~a
r4 = r2 & r3  # b & ~a
r4 = ~r4      # b NAND ~a
r2 = ~0 - r2  # ~b
r2 = r2 & r1  # a & ~b
r2 = ~r2      # a NAND ~b
r1 = r2 & r4
r1 = ~r1      # a ^ b

, но это будет не так эффективно, как непосредственное использование свойства сумматора

Вы можете найти многодругие способы из исключительные или эквивалентные 

a ^ b = (a | b) & ~(a & b) = ~(~a & ~b) & ~(a & b)
a ^ b = ~(a & b) & (a | b) = ~(a & b) & ~(~a & ~b)

См. Является ли XOR комбинацией операторов AND и NOT?

Похожие: XORтолько из ИЛИ И И

0 голосов
/ 12 декабря 2018

Поскольку a + b может быть расширен до (a ^ b) + ((a & b) << 1), если доступны +, -, & -операторы, выполняется следующее:

a ^ b == a + b - (a & b) - (a & b).

Фактически gcc 8.2.1оптимизирует следующую c-функцию 

unsigned foo(unsigned a, unsigned b)
{
   return a + b - (a & b) - (a & b);
}

до следующей сборки x86-64 с помощью -O3: 

foo:
    movl    %edi, %eax
    xorl    %esi, %eax
    ret

Следовательно, ни инструкции перехода не требуются, ни болеетри регистра (далее псевдосборка): 

$r1 = a          //first argument
$r2 = b          //second argument
$r3 = $r1 & $r2  //one temp register is enough
$r1 = $r1 + $r2
$r1 = $r1 - $r3
$r1 = $r1 - $r3  //$r1 is the return value
...