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

Question

Here is a function that finds the larger of two numbers:

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

To find the largest of the three numbers, name it like this:

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

How it works?

Answer 1

 int c=ab; 

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

 int k=c>>31&1; 

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

 int max=ak*c; 

replacing c = ab , we obtain max = ak*(ab) . That's why when

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

Answer 2

This only works for 32-bit integers.

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

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

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

Historically, pipelining of instructions has been the main reason for using code that avoids the if test. If the pipeline is deep and the processor does not use branch prediction, half a dozen whole operations may take less time than wasting time refueling the pipeline and working with speculative stores, if any. With branch prediction, code with if (or equivalent) can be faster. In any case, the cost of saved or lost nanoseconds may never exceed the cost of maintaining the program for this code.

Answer 3

try this .. long, 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;