按位运算是否分布于加法？

Question

我正在研究一个我正在尝试优化的算法，它基本上是很多麻烦，然后在严格的反馈中添加了一些内容。如果我可以对加法器使用进位保存加法，它确实会帮助我加快速度，但我不确定是否可以将操作分配给加法。

具体来说，如果我表示：

  a = sa+ca  (state + carry)
  b = sb+cb

我可以用s和c表示(a>>>r)吗？ 怎么样？ b和a&乙？

Answer 1

想想看...

sa = 1    ca = 1
sb = 1    cb = 1
a = sa + ca = 2
b = sb + cb = 2
(a | b) = 2
(a & b) = 2
(sa | sb) + (ca | cb) = (1 | 1) + (1 | 1) = 1 + 1 = 2 # Coincidence?
(sa & sb) + (ca & cb) = (1 & 1) + (1 & 1) = 1 + 1 = 2 # Coincidence?

让我们尝试一些其他值：

sa = 1001   ca = 1   # Binary
sb = 0100   cb = 1
a = sa + ca = 1010
b = sb + cb = 0101
(a | b) = 1111
(a & b) = 0000
(sa | sb) + (ca | cb) = (1001 | 0101) + (1 | 1) = 1101 + 1 = 1110 # Oh dear!
(sa & sb) + (ca & cb) = (1001 & 0101) + (1 & 1) = 0001 + 1 = 2    # Oh dear!

因此，通过 4 位计数器示例证明您不能将 AND 或 OR 分配给加法。

'>>>' 怎么样？ （无符号或逻辑右移）。使用最后一个示例值，并且 r = 1：

sa = 1001
ca = 0001
sa >>> 1 = 0101
ca >>> 1 = 0000
(sa >>> 1) + (ca >>> 1) = 0101 + 0000 = 0101
(sa + ca) >>> 1 = (1001 + 0001) >>> 1 = 1010 >>> 1 = 0101  # Coincidence?

让我们看看这是否也是巧合：

sa = 1011
ca = 0001
sa >>> 1 = 0101
ca >>> 1 = 0000
(sa >>> 1) + (ca >>> 1) = 0101 + 0000 = 0101
(sa + ca) >>> 1 = (1011 + 0001) >>> 1 = 1100 >>> 1 = 0110  # Oh dear!

再次通过反例证明。

因此逻辑右移也不具有加法的分配性。

Answer 2

不可以，您不能将 AND 或 OR 分配给二元运算符。

解释

设P是一个命题，其中P：(A+B)&C = A&C + B&C

让我们取A=2,B=3 =>A+B=5 。

我们要证明 A&C + B&C != (A+B)&C

A=2= 010

B=3= 011

让 010&C = x，
其中 x 是某个整数，其值是 010 和 C 的按位 AND 的结果

，类似地 011&C = y，其中 y 是某个整数，其值是 011 和 C 的按位 AND 的结果，

因为我们不能说 P 对于所有 C 都成立在自然数集合 ( {0,1,...} ) 中，因此 P 为假。

在这种情况下，取C=2=010

x=010 & 010 = 010 = 2

y=011 & 010 = 010 = 2

5&2=101& 010 = 000 = 0

显然， x+y!=0 ，这意味着 (A+B)&C != A&C + B&C。

由此证明！