Question

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.

Specifically if I represent:

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

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

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?

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!

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

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!

Proof by counter-example again.

So logical right shift is not distributive over addition either.

Answer 2

No, you cannot distribute AND or OR over binary operators.

Explanation

Let P be a proposition where P: (A+B)&C = A&C + B&C

let us take A=2,B=3 =>A+B=5.

We are to prove A&C + B&C != (A+B)&C

A=2= 010

B=3= 011

let 010&C = x, where x is some integer whose value is the resultant of bitwise AND of 010 and C

similarly 011&C = y, where y is some integer whose value is the resultant of bitwise AND of 011 and C

since we cannot say P holds for all C in the set of Natural numbers ( {0,1,...} ), consequently P is false.

In this case, take C=2=010

x=010 & 010 = 010 = 2

y=011 & 010 = 010 = 2

5&2=101 & 010 = 000 = 0

clearly, x+y!=0 , which means (A+B)&C != A&C + B&C.

Hence proved!

友情链接