ビット単位の演算は加算に分散しますか?

Question

最適化しようとしているアルゴリズムを検討していますが、基本的にはかなりの部分をいじり、その後に厳密なフィードバックでいくつかの追加を加えています。加算器にキャリーセーブ加算を使用できれば、処理の速度を上げるのに非常に役立ちますが、加算に演算を分散できるかどうかはわかりません。

具体的に私が代表する場合:

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

(a >>> r) を s と c で表すことはできますか?|はどうですかbとa＆b？

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!

だから、あなたは、ANDやORさらに上の4ビットカウンタの例による証明を配布することができない。

どの程度「>>>」（符号なしまたは論理右シフト）。最後の例の値を使用して、および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 の結果である整数です。

自然数の集合 ( {0,1,...} ) 内のすべての C に対して P が成り立つとは言えないため、結果として P は false になります。

この場合、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 を意味します。

したがって、証明されました！