位运算是否满足加法分配律？

Question

我是一名有用的助手，可以为您进行文本翻译。以下是需要翻译的内容：

我正在研究一个算法，试图对其进行优化，它基本上是一些位操作，然后在紧密反馈中进行一些加法运算。如果我能够使用Carry-Save加法器进行加法运算，那么将真正帮助我加快速度，但我不确定是否可以将这些操作分配到加法中。

具体来说，如果我表示：

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

我能用 s 和 c 表示 (a >>> r) 吗？a | b 和 a & b 呢？

- gct

Answer 1

Think about it...

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!

再次通过反例来证明。

因此，逻辑右移也不能在加法上分配。

- Jonathan Leffler

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对所有自然数集合（{0,1，...}）中的所有C成立，因此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。

因此证明了！

- Anirban

---

我认为这提供了一个答案，但不是很好的答案。如果您提供一个示例来证明您所说的是正确的，那将会更好。 - Teepeemm

我已经编辑了我的答案，并添加了解释来证明我的答案。 - Anirban