CODEWITHSUNDEEP
algorithm
Eight
Eight

Reputation: 4284

How does this code work to find the largest of three numbers without using any comparison operator?

Here is the function that finds the greater of two numbers:

int larger(int a,int b)
{
    int c=a-b;
    int k=c>>31&1;
    int max=a-k*c;
    return max;
 }

To find the greatest of three numbers, call it such as:

larger(a,larger(b,c));

How does this work?

Upvotes: 6

Views: 1382

Answers (3)

gsn16
gsn16

Reputation: 51

try this.. it is lengthy, sorry :P

while(x && y && z)
{
        x--;y--;z--;c++;
}


if(x && y)
{
while(x && y)
{
    x--;y--;c++;
}
if(x) c+=x;
if(y) c+=y;
}


if(z && y)
{   
while(z && y)
{
    z--;y--;c++;
}
if(z) c+=z;
if(y) c+=y;
}

if(x && z)
{
while(x && z)
{
    x--;z--;c++;
}
if(x) c+=x;
if(z) c+=z;
}

return c;

Upvotes: -3

James Waldby - jwpat7
James Waldby - jwpat7

Reputation: 8711

This only works for 32-bit integers, of course.

k=c>>31&1 isolates the sign bit, which is 0 or 1.

If k is 0, then a>=b and max = a - 0*(a-b) = a.

If k is 1, then a<b and max = a - 1*(a-b) = a-a+b = b.

Historically, instruction pipelining was the main reason for using code that avoids an if test. If the pipeline is deep and the processor doesn't use branch prediction, a half-dozen integer operations can take less time to do than the time lost due to pipeline refilling and dealing with speculative stores, if any. With branch prediction, code with an if (or equivalent) might be faster. Either way, the cost of the nanoseconds saved or lost might never exceed the program-maintainance costs for that code.

Upvotes: 5

codaddict
codaddict

Reputation: 455252

int c=a-b;

cwill be negative if a < b else it will positive. Now a negative number will have its most significant bit(MSB) set. 

int k=c>>31&1;

This step assumes that sizeof(int) is 4 bytes and extracts the MSB of c in k. So k is either 0 or 1

int max=a-k*c;

replacing c = a-b in this we get max = a-k*(a-b). So when 

k = 0, max = a-0*(a-b)
           = a

k = 1, max = a-1*(a-b)
           = b

Upvotes: 17

Related Questions