Побитовые операторы: используя только & и ~, чтобы получить ^ - PullRequest
Новая
       69

Побитовые операторы: используя только & и ~, чтобы получить ^

0 голосов
/ 05 марта 2020

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

  • дать х ^ у, используя только ~ и &
  • Предположим, что машина использует два дополнения, 32-битные представления целых чисел.

Я пробовал много разных комбинаций, а также пытался выписать лог c оператор ^, но это не сработало. Любые советы или помощь будут высоко оценены!

Ответы [ 3 ]

3 голосов
/ 05 марта 2020

Сначала предположим, что у вас есть каждый из операторов &, | и ~. Не могли бы вы реализовать ^ таким образом?

Далее, посмотрите, сможете ли вы найти способ express | исключительно в терминах & и ~.

Наконец Объедините эти идеи вместе.

Удачи!

3 голосов
/ 05 марта 2020

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

A NAND B = NOT (A AND B)

A XOR B = (A NAND (A NAND B)) NAND (B NAND (A NAND B))

Как описано выше по математике:

https://math.stackexchange.com/questions/38473/is-xor-a-combination-of-and-and-not-operators

2 голосов
/ 05 марта 2020

Вы можете попытаться нарисовать таблицы истинности для XOR , И и, ИЛИ 

a b  a^b
0 0   0
0 1   1
1 0   1
1 1   0

a b  a|b
0 0   0
0 1   1
1 0   1
1 1   1

a b  a&b
0 0   0
0 1   0
1 0   0
1 1   1

, затем найдите, как используйте | и & для построения

a|b, чтобы все три первых строки были правильными, a&b - для другой строки. Если мы отрицаем это, это может быть использовано для маскировки нужных строк! Таким образом, мы можем сформулировать xor следующим образом:

(a или b) , но не когда (a и b)

В булевой алгебре нет , но , поэтому она становится и , что приводит к этому: 

(a|b)&~(a&b)

Редактировать: Указано Я отвечаю не на тот вопрос, используйте закон Деморгана для построения или 

~(~a & ~b)

дает ответ, равный 

~(~a&~b)&~(a&b)
...