千万位运算分布于除？ [英] Do bitwise operations distribute over addition?

问题描述

我期待在一个算法我想优化，它基本上是一个很多位操作，随后在紧张的反馈一些补充。如果我可以用随身携带保存额外增加了加法器，这将真正帮助我加快速度，但我不知道我是否可以通过增加分配的操作。

I'm looking at an algorithm I'm trying to optimize, and it's basically a lot of bit twiddling, followed by some additions in a tight feedback. If I could use carry-save addition for the adders, it would really help me speed things up, but I'm not sure if I can distribute the operations over the addition.

特别是如果我再present：

Specifically if I represent:

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

我可以在S和C的角度重新present（A >>> R）？
怎么样| b和A和B'

can I represent (a >>> r) in terms of s and c? How about a | b and a & b?

推荐答案

想想吧...

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?

让我们尝试一些其他值：

Let's try some other values:

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或以上的补充。

So, proof by 4-bit counter example that you cannot distribute AND or OR over addition.

什么'>>>'（无符号或逻辑右移）。使用最后一个例子值，R = 1：

What about '>>>' (unsigned or logical right shift). Using the last example values, and 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?

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

Let's see whether that is coincidence too:

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!

再次反例证明。

所以逻辑右移不超过此外配电台无论是。

So logical right shift is not distributive over addition either.

这篇关于千万位运算分布于除？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！