Re: Subtract smaller or larger number from x?
- From: Dave <solomons_dad.w.marks_and_whom@xxxxxxxxxx>
- Date: Thu, 30 Mar 2006 18:01:55 +0100
Gerry Quinn wrote:
In article <20060329145340.f93b3f3b.steveo@xxxxxxxxxx>, steveo@xxxxxxxxxx says...
So in addition to doing the subtraction and a test it is doing a
function call and perhaps a negation - whereas the original is doing a test
and a subtraction. Seems pretty certain to be less efficient to me.
This version might be more efficient but I doubt it, it probably
compiles to pretty much the same code as the original. It is perhaps a
little prettier.
diff = (y > x) ? y - x : x - y;
On an old fashioned CPU, the following might be closest to the most efficient assembly:
int val = y - x;
if ( val < 0 )
{
val = -val;
}
The reason being that a comparison is effectively a subtraction that sets the relevant flags but leaves the data unchanged. So you might as well do the subtraction immediately to get the sign flag. It would look something like:
move A, y
sub A, x
jump on not negative END
add A, x ; if no 2-s complement operator available
add A, x
END:
But if conditional jumps are expensive but the CPU has a built-in abs operation, that's going to be best.
- Gerry Quinn
On any CPU this is probably the least efficient, but it doesn't use a conditional:
x=10; y=20;
diff=y-x;
int num7f=unsigned(-1)>>1;
int msb=~num7f;
int diff_and_msb = diff & msb;
int diff_lt0 = unsigned(diff_and_msb)>>(sizeof(int)*8-1);
diff=(diff^(unsigned(-1)*diff_lt0))+diff_lt0;
which extracts the most significant bit from the difference and does an effectively conditional two's complement on it.
Flattened out not to use any intermediates, and if you want to do it in just one line of completely unreadable code (not that this isn't already completely unreadable), just substitute (y-x) for flatdiff throughout:
int flatdiff=y-x;
flatdiff=(flatdiff^(unsigned(-1)*(unsigned(flatdiff & ~(unsigned(-1)>>1))>>(sizeof(int)*8-1))))+(unsigned(flatdiff & ~(unsigned(-1)>>1))>>(sizeof(int)*8-1));
This might be useful for when people post homework assignments...
Dave.
.
- References:
- Subtract smaller or larger number from x?
- From: eksamor
- Re: Subtract smaller or larger number from x?
- From: upeksharuvani
- Re: Subtract smaller or larger number from x?
- From: Steve O'Hara-Smith
- Re: Subtract smaller or larger number from x?
- From: Gerry Quinn
- Subtract smaller or larger number from x?
- Prev by Date: Re: Recursive Question
- Next by Date: ALgorithm Solution
- Previous by thread: Re: Subtract smaller or larger number from x?
- Next by thread: Re: Subtract smaller or larger number from x?
- Index(es):
Relevant Pages
|
