Как рассчитать побитовое ИЛИ, используя AND, XOR и сдвиг?

Question

Вопрос кажется довольно хорошо сформулированным

У меня есть виртуальная машина, которая реализует только AND, XOR, SHL и SHR, но мне нужно выполнить операцию «OR 0x01».

Answer 1

Прежде всего достаточно правильного побитового вычисления для следующих двух переменных, поскольку они охватывают все комбинации:
A = 0101
В = 0011

Мы хотим
0101
0011
А или В
0111

для xor мы получаем

0101
0011
A xor B
0110

за и мы получаем

0101
0011 * +1021 * А и В
0001

поэтому, если мы соединим их с xor, то все готово.

(A xor B) xor (A и B)

Answer 2

Я бы просто начал с

a xor b = ((not a) and b) or (a and (not b))

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

a or b = <expression using only and, xor>

По общему признанию, это, вероятно, больше работы, чем выполнениеМаршрут «попробуй каждую мыслимую комбинацию битов», но потом ты попросил идеи решения домашней работы.:)

Answer 3

Таблица истинности в обобщенном виде в Википедии здесь и удушье, базовые вещи CS 101, Закон Де Моргана ....

AND
0 & 0   0
0 & 1   0
1 & 0   0
1 & 1   1


OR
0 | 0   0
0 | 1   1
1 | 0   1
0 | 0   1


XOR
0 ^ 0   0
0 ^ 1   1
1 ^ 0   1
1 ^ 1   0

Сдвиг влево включает сдвиг битов справа налево, предположим:

+-+-+-+-+-+-+-+-+
|7|6|5|4|3|2|1|0|
+-+-+-+-+-+-+-+-+
|0|0|0|0|0|1|0|0| = 0x4 hexadecimal or 4 decimal or 100 in binary
+-+-+-+-+-+-+-+-+

Shift Left by 2 places becomes
+-+-+-+-+-+-+-+-+
|7|6|5|4|3|2|1|0|
+-+-+-+-+-+-+-+-+
|0|0|0|1|0|0|0|0| = 0x10 hexadecimal or 16 decimal or 10000 in binary
+-+-+-+-+-+-+-+-+

Shift Right by 1 places becomes
+-+-+-+-+-+-+-+-+
|7|6|5|4|3|2|1|0|
+-+-+-+-+-+-+-+-+
|0|0|0|0|1|0|0|0| = 0x8 hexadecimal or 8 decimal or 1000 in binary
+-+-+-+-+-+-+-+-+

Тогда речь идет о комбинировании побитовых операций в соответствии с таблицей истинности, приведенной выше ...

Answer 4

Я бы просто расширил закон Деморгана : A or B = not(not A and not B). Вы можете вычислить not с помощью XORing со всеми 1 битами.