Sie bitweise Operationen verteilen über hinaus?

Question

Ich betrachte einen Algorithmus ich zu optimieren bin versucht, und es ist im Grunde eine Menge bisschen Fummeln, durch einige Ergänzungen in einem engen Feedback gefolgt. Wenn ich für die Addierer Carry-Save-Zusatz verwenden könnte, wäre es wirklich hilft mir, die Dinge zu beschleunigen, aber ich bin nicht sicher, ob ich die Operationen über den Zusatz verteilen kann.

Insbesondere wenn ich vertrete:

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

kann ich darstellen (ein >>> r) in Bezug auf s und c? Wie wäre es a | b und a & b?

Answer 1

Denken Sie darüber nach ...

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?

Lassen Sie uns einige andere Werte versuchen:

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!

Also, Beweis von 4-Bit-Zählern Beispiel, dass Sie nicht AND oder OR über hinaus verteilen.

Was ist '>>>' (unsigned oder logische Verschiebung nach rechts). Mit den letzten Beispiel Wert und 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?

Lassen Sie uns sehen, ob das Zufall ist auch:

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!

Der Nachweis von Gegenbeispiel wieder.

So logische Verschiebung nach rechts ist entweder nicht distributiv über hinaus.

Answer 2

Nein, Sie können nicht verteilen AND oder OR über Binäroperatoren.

Erklärung

Es sei P ein Satz sein, wobei P: (A + B) und C = A & C + B & C

nehmen wir A = 2, B = 3 => A + B = 5.

Wir sind zu beweisen, A & C + B & C! = (A + B) & C

A = 2 = 010

B = 3 = 011

let 010 x C =, wobei x eine gewisse ganze Zahl, deren Wert die Resultierende der bitweisen UND-010 und C

in ähnlicher Weise 011 & C = Y, wobei Y für einige ganze Zahl, deren Wert ist die Resultierende der bitweisen UND-011 und C

da wir können nicht sagen, P für alle C in der Menge der natürlichen Zahlen enthält ({0,1, ...}), folglich P falsch ist.

In diesem Fall nehmen C = 2 = 010

x = 010 & 010 = 010 = 2

y = 011 & 010 = 010 = 2

5 & 2 = 101 & 010 = 000 = 0

klar, x + y! = 0, was bedeutet, (A + B) & C! = A & C + B & C.

Damit bewiesen!