help in these Bit operations...

Geez, you'd think that I'd never typed before.  Plus I failed to simplify.  The last dozen lines of the previous post should read:

Question 2 is the longest to fully explain.  The short explanation is that a min() function can be performed logically or arithmetically.  You're used to seeing a min() function defined logically:

#define min(a,b) (a < b ? a : b)


Arithmetically, min(a,b) is the average, - 1/2 of the difference:

#define min(a,b) (((a+b)/2) - (abs(a-b)/2)

Which can be written more simply as:

#define min(a,b) ((a+b - abs(a-b)) / 2)

The formula that you've given is an extension of this simple definition.


Kent

How are these manipulations to be considered optimizations?

Hi klopex,

At the programming level, they're certainly no simpler or shorter than the straightforward math.

But at the hardware level the magic of mathematics can be used to simplify a lot of processes.  It's not necessary to define gates for all of the logical operations.  XOR is a function of AND and OR, etc.

After all, the fastest 1's complement machines in the world couldn't add -- they inverted the second operand and subtracted.


Kent

These are "optimizations" in the sense that a smart programmer or a smart compiler
could say, hmmm, at this instant in the code, the adder is busy, but the logical processor
is idle-- let's do this next add in the logical unit.   (This assumes a CPU that can issue
several instructions in parallel, and has separate adders and logical (boolean) units).

I never considered stategically taking advantage of Tomasulo's architecture...That's brilliant!

hello all,
thanks for the explanantions provided so far (Kdo for q. 2) but iam still not clear how q.1 and q2 the equi-valent operations have been derived.  cus sumone clarify?
TIA

Question 1 goes right to the heart of mathematics.  It's how the add unit in the CPU works.

1) (x+y) equals ((x&y)+(x|y)) equals ((x^y)+2*(x&y)).

We have three formulas that are claimed to be equivalent in nature.  The first one (x+y) is trivial and the "base" -- the other equations are equivalent to it.

The second equation ((x&y)+(x|y)) is the first step in building an adder.  (x&y) generates a result (mask) that indicates which bits are common to the operands (x and y).  This result shows which bit positions are guaranteed to generate a carry when the original values (x and y) are added together.  (in binary, 1+1 = 0 carry the 1.)  (x|y) produces a result (mask) that indicates which bit positions in either operand contained a 1.  Those positions MAY produce a carry when the addition is complete.  0+0+carry is the only combination guaranteed to not generate a carry.  The second mask identifies all other bit positions.

Adding the two masks together is essentially how we add in base 10, except that we do it one bit (column) at a time.

But notice that the result is still generated by adding two logically derived masks.  Hardly more efficient.  ;)

The third equation is an extension of the previous.  (x^y) generates a result (mask) that indicates which bits are set in exactly one of the operands.  (x&y) has been explained -- it's the "carry" mask.  2*(x&y) is simply the carry mask shifted left one bit.

Add the unique bits of the two operands to the carry mask and you've generated the sum.


Question 3 relies on a trick that's unique to 2's complement math.  The least significant 1 bit in a positive value is in the same position as the value's arithmetic complement (negative value).

(any positive value) & (0 - (any positive value)) = the low order bit.

Using my earlier example you can see that the ONLY common bit between 88 and -88 is the lowest 1 bit in either.  In this case, 2**3.

01011000  (binary vaue of  88)
10101000  (binary value of -88)
------------   & operation
00001000  Result


It's kind of hard to describe all of this in a few short paragraphs and without good pictures.  But it's all right out of Computer Science 101.  You might find an old text book and review adders.

Kent

They didn't teach that in CS 101 where I went to Grad School!!  Some Software Engeneering enthusiasts took over the curriculum structuring and they taught GUI JAVA for 101 and 102.  Those kids didn't have a clue about what a computer was or what it does after they left that course!  Depressing to a C enthusiast!  

<furtherRanting>
They actually tried to teach relationships between objects, data passing in functions, etc. before they ever taught if statements!!!  ARGGGH!  (I was one of the Grad Assistants who helped teach the Lab sections.  So, we were the ones who actually had to deal with desperate students who had no clue how to program.  Issues like logic and thinking are hard to teach, especially the day before a project is due!
</furtherRanting>

Thanks for the smart posts.

Hi klopex,

Man, oh man, but your first statement is depressing.  When I went to school there wasn't a true Computer Science curriculum offered, nor was there EE.  CS was taught through the Math department so that the study (and label on one's degree) actually said "Applied Mathematics with special emphasis on Computer Science".  (It would be fun to have one hanging on the wall, but alas, I are, er... AM, a dropout.  ;) )

Even so, we were taught 1's and 2's complement math, the components/wiring of a bit and all of the common gates, how to wire them into useful devices like adders and shifters, etc.

I have trouble understanding how CS, even without the EE components, has been reduced to "This is how it's done in Windows".  :(


Kent