Não operações bit a bit distribuir mais além?

Question

Eu estou olhando para um algoritmo que estou tentando otimizar, e é basicamente um monte de pouco twiddling, seguido por algumas adições em um feedback apertado. Se eu pudesse usar carry-save adição para as víboras, seria realmente me ajudar a acelerar as coisas, mas eu não tenho certeza se eu posso distribuir as operações durante a adição.

Especificamente, se eu represento:

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

I pode representar (a >>> r) em termos de s e c? Como cerca de um | b e a & b?

Answer 1

Pense nisso ...

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?

Vamos tentar alguns outros valores:

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!

Assim, a prova de contra-exemplo de 4 bits que você não pode distribuir E ou OU mais além.

E '>>>' (deslocamento para a direita sem sinal ou lógica). Usando os últimos valores de exemplo, e 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?

Vamos ver se isso é coincidência demasiado:

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!

A prova de contra-exemplo novamente.

deslocamento para a direita Então lógica não é distributiva sobre a adição quer.

Answer 2

Não, você não pode distribuir E ou OU sobre os operadores binários.

Explicação

Seja P ser uma proposta em que P: (A + B) e C = A & C + B & C

Vamos dar uma = 2, B = 3 => A + B = 5.

Estamos a provar A & C + B & C! = (A + B) e C

= 2 = 010

B = 3 = 011

deixou 010 & C = x, em que x é um número inteiro cujo valor é a resultante de bit a bit E de 010 e C

semelhante 011 & C = Y, em que y é um número inteiro cujo valor é a resultante de bit a bit E de 011 e C

desde que nós não podemos dizer P vale para todo C no conjunto dos números naturais ({0,1, ...}), conseqüentemente P é falsa.

Neste caso, tomar C = 2 = 010

x = 010 & 010 = 010 = 2

y = 011 & 010 = 010 = 2

5 & 2 = 101 & 010 = 000 = 0

claramente, x + y! = 0, o que significa (A + B) & C! = A & C + B & C.

Assim provou!