help in these Bit operations...

not_an_xpert
not_an_xpert used Ask the Experts™
on
Hello all,
Recently I had hit upon a document on efficient C optimisations... most of them are bit manipulation operations
as i was going thro' the doc. i'd some doubts.. cud the experts throw some light on these

1) (x+y) equals ((x&y)+(x|y)) equals ((x^y)+2*(x&y)).  How is this possible
2) Given 2's complement integer values x and y, the minimum can be computed without any branches
     as x+(((y-x)>>(WORDBITS-1))&(y-x)).  how can they arrive on this
3) Similarly  Given a 2's complement binary integer value x, (x&-x) is the least significant 1 bit.

It s not any Home work question(S).
I can provide the doc. if reqd.

TIA
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Hi agan not_an_xpert,

Starting with the easy question first, :)

Your third question addresses a very common technique for determining the rightmost 1-bit in a word.  Let's assume an integer with a value of 8.  According to the formula that you've given:


00001000  (binary value of 8)
11111000  (binary value of -8)
------------   & operation
00001000  Result


In this case the result isn't very impressive, but watch what happens when you use a value with more bits.

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



Question 1 is similar.  88 was a nice number.  Let's add it to 43

01011000  (binary value of 88)
00101011  (binary value of 43)
------------   + operation
10000011   (131)


Now let's do it with the math in the formula:

01011000  (88)
00101011  (43)
------------   & operation
00001000  (Save this)


01011000  (88)
00101011  (43)
------------   | operation
01111011  (Save this too)

00001000  (Save 1)
01111011  (Save 2)
------------   + Operation
10000011   (Looks like we got 131 again :)  )



01011000  (88)
00101011  (43)
------------   ^ operation
01110011  (Save 3)

00001000  (Save 1 -- x&y)
00000010  (2)
------------   * (Multiply)
00010000  (Save 4)

01110011  (Save 3)
00010000  (Save 4)
------------   + Operation
10000011  (131 again.  Son of a gun)


Question 2 is the longest to fully explain.  The short explanation is the 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/s of the difference:

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

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


Kent


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

Commented:
How are these manipulations to be considered optimizations?
Should you be charging more for IT Services?

Do you wonder if your IT business is truly profitable or if you should raise your prices? Learn how to calculate your overhead burden using our free interactive tool and use it to determine the right price for your IT services. Start calculating Now!


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

Commented:
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).

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

Author

Commented:
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

Commented:
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

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial