Find the maximum (or minimum) of two numbers (or morenumbers) without use of comparison operators or if-else

Problem

Write a method which finds the maximum of two numbers You should not use if-else or any other comparison operator
EXAMPLE
Input: 5, 10
Output: 10

Solution

Method 1 - Using arithematic operator
Let a is greater than b, and M is the mid point, then:

then

max = (a + b) / 2 + |a - b| / 2

Method 2 - Using most significant bit
Let’s try to solve this by “re-wording” the problem We will re-word the problem until we get something that has removed all if statements
Rewording 1: If a > b, return a; else, return b
Rewording 2: If (a – b) is negative, return b; else, return a
Rewording 3: If (a – b) is negative, let k = 1; else, let k = 0. Return a – k * (a – b)
Rewording 4: Let c = a – b. Let k = the most significant bit of c. Return a – k * c


We have now reworded the problem into something that fits the requirements for this is below:

int getMax(int a, int b) {
    int c = a - b;
    int k = (c >> 31) & 0x1;
    int max = a - k * c;
    return max;
}

What is the significance of :

int k = (c >> 31) & 0x1;

It tells us the sign of the c i.e. a-b. So, we do following
max = a - k *(a-b)

int max = a - k * c;

If a < b, then k == 1 and k * c = c = a - b, and so

a - k * c = a - (a - b) = a - a + b = b

Which is the correct max, since a < b.

Otherwise, if a >= b, then k == 0 and

a - k * c = a - 0 = a

Assumptions
In virtually all modern computers, numbers are stored in a format called two's complement in which the highest bit of the number is 0 if the number is positive and 1 if the number is negative. Moreover, most ints are 32 bits. (c >> 31) shifts the number down 31 bits, leaving the highest bit of the number in the spot for the lowest bit.

The next step of taking this number and ANDing it with 1 (whose binary representation is 0 everywhere except the last bit) erases all the higher bits and just gives you the lowest bit. Since the lowest bit of c >> 31 is the highest bit of c, this reads the highest bit of c as either 0 or 1. Since the highest bit is 1 iff c is 1, this is a way of checking whether c is negative (1) or positive (0). Combining this reasoning with the above, k is 1 if a < b and is 0 otherwise.

What if want min of 2 numbers without comparison operator?
Answer to this is again similar to above.

Using method 1, we will have

min = (a+b)/2 - |a-b|/2

Similarly using method 2, gives us:

c = a - b;
k = (c >> 31) & 0x1;
max = b+ k*c

What if want to find the min of 3 numbers without using comparison operator?

Answer is simple,

min(a,b,c) = min(a,min(b,c))

Similarly for max.

Please let me know if you have other suggestions.

References

• http://tianrunhe.wordpress.com/2012/05/14/find-the-maximum-of-two-numbers-without-use-of-comparison-operators-or-if-else/
• http://stackoverflow.com/questions/4772780/find-the-maximum-of-two-numbers-without-using-if-else-or-any-other-comparison-op 
• http://souvikpal.wordpress.com/2013/02/10/findmax-without-if-else/