Geek Answers Handbook

Are bitwise addition operations broken up?

I look at an algorithm that I am trying to optimize, and it is mostly a lot of bits, and then some additions in tight feedback. If I could use the carryover add-on for additives, it would really help me speed up the process, but I'm not sure if I can distribute add-on operations.

In particular, if I submit:

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

Is it possible to represent (a →> r) in terms of s and c? How about | b and a and b?

+4
source share
2 answers

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?

Try 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, the proof with a 4-bit counter example is that you cannot distribute AND or OR over the addition.

How about "→>" (unsigned or logical shift to the right). Using the latest 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 if this is also a match:

 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!

The proof is again a counter example.

Thus, a logical shift to the right does not apply to addition.

+7
source

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

Explanation

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

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

We must prove that 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 result of bitwise AND 010 and C

similar to 011 & C = y, where y is some integer whose value is the resulting bitwise AND of 011 and C

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

In this case, take C = 2 = 010

x = 010 and 010 = 010 = 2

y = 011 and 010 = 010 = 2

5 & ​​2 = 101 and 010 = 000 = 0

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

Therefore, it is proved!

+1
source

More articles:


All Articles