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

Question

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?

Answer 1

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

Answer 2

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.