如何使用AND、XOR和移位运算符计算按位或？

Question

这个问题似乎已经很好地表述了。

我有一个只实现了AND、XOR、SHL和SHR的虚拟机，但我必须执行“OR 0x01”的操作。

- Flavius

---

听起来像是一个作业问题。 - oefe

我不需要解决方案，只需要至少一个想法。这是一项作业，但坦率地说，我已经做了比解决问题所需更多的工作。例如，我发明了一种调用约定来更好地模块化我的代码。因此，问题本身并不是作业，只是我需要知道的东西。@KennyTM：这是一台16位机器。 - Flavius

@KennyTM：它是一台16位机器。 - Flavius

Answer 1

首先，正确的位运算计算以下两个变量是足够的，因为它们涵盖了所有组合：
A=0101
B=0011

我们想要：
0101
0011
A或B
0111

对于异或，我们得到

0101
0011
A异或B
0110

对于与，我们得到

0101
0011
A与B
0001

所以如果我们用异或将它们连接起来，就完成了。

(A异或B)异或(A与B)

- user282727

Answer 2

我会从以下内容开始：

我会从以下内容开始：

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

并运用布尔代数对其进行处理，直到它看起来像这样：

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

不可否认，实际上这可能比尝试“尝试每种可能的位组合”路线更需要工作量，但是您确实要求了家庭作业解决方案的想法。 :)

- ndim

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 十六进制或 4 十进制或 100 二进制
+-+-+-+-+-+-+-+-+
左移 2 位变成
+-+-+-+-+-+-+-+-+
|7|6|5|4|3|2|1|0|
+-+-+-+-+-+-+-+-+
|0|0|0|1|0|0|0|0| = 0x10 十六进制或 16 十进制或 10000 二进制
+-+-+-+-+-+-+-+-+
右移 1 位变成
+-+-+-+-+-+-+-+-+
|7|6|5|4|3|2|1|0|
+-+-+-+-+-+-+-+-+
|0|0|0|0|1|0|0|0| = 0x8 十六进制或 8 十进制或 1000 二进制
+-+-+-+-+-+-+-+-+

然后根据上面的真值表组合位运算即可...

- t0mm13b

Answer 4

我只是想扩展德摩根定律：A或B = not(not A and not B)。你可以通过与所有1位进行XOR运算来计算not。

- Chris Dodd