Explain this snippet which finds the maximum of tw

Question

Find the maximum of two numbers. You should not use if-else or any other comparison operator. I found this question on online bulletin board, so i thought i should ask in StackOverflow

EXAMPLE Input: 5, 10 Output: 10

I found this solution, can someone help me understand these lines of code

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

Answer 1

Here's what those lines are doing:

c is a-b. if c is negative, a<b.

k is 32nd bit of c which is the sign bit of c (assuming 32 bit integers. If done on a platform with 64 bit integers, this code will not work). It's shifted 31 bits to the right to remove the rightmost 31 bits leaving the sign bit in the right most place and then anding it with 1 to remove all the bits to the left (which will be filled with 1s if c is negative). So k will be 1 if c is negative and 0 if c is positive.

Then max = a - k * c. If c is 0, this means a>=b, so max is a - 0 * c = a. If c is 1, this means that a<b and then a - 1 * c = a - (a - b) = a - a + b = b.

In the overall, it's just using the sign bit of the difference to avoid using greater than or less than operations. It's honestly a little silly to say that this code doesn't use a comparison. c is the result of comparing a and b. The code just doesn't use a comparison operator. You could do a similar thing in many assembly codes by just subtracting the numbers and then jumping based on the values set in the status register.

I should also add that all of these solutions are assuming that the two numbers are integers. If they are floats, doubles, or something more complicated (BigInts, Rational numbers, etc.) then you really have to use a comparison operator. Bit-tricks will not generally do for those.

Answer 2

int max(int i, int j) {
    int m = ((i-j) >> 31);
    return (m & j) + ((~m) & i);
}

This solution avoids multiplication. m will either be 0x00000000 or 0xffffffff

Answer 3

The logic described in a problem can be explained as if 1st number is smaller then 0 will be subtracted else difference will be subtracted from 1st number to get 2nd number. I found one more mathematical solution which I think is bit simpler to understand this concept.

Considering a and b as given numbers

c=|a/b|+1;
d=(c-1)/b;
smallest number= a - d*(a-b);

Again,The idea is to find k which is wither 0 or 1 and multiply it with difference of two numbers.And finally this number should be subtracted from 1st number to yield the smaller of the two numbers. P.S. this solution will fail in case 2nd number is zero

Answer 4

getMax() Function Without Any Logical Operation-

int getMax(int a, int b){
    return (a+b+((a-b)>>sizeof(int)*8-1|1)*(a-b))/2;
}

---

Explanation:

Lets smash the 'max' into pieces,

max
= ( max + max ) / 2
= ( max + (min+differenceOfMaxMin) ) / 2
= ( max + min + differenceOfMaxMin ) / 2
= ( max + min + | max - min | ) ) / 2

So the function should look like this-

getMax(a, b)
= ( a + b + absolute(a - b) ) / 2

Now,

absolute(x)
= x [if 'x' is positive] or -x [if 'x' is negative]
= x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] )

In integer positive number the first bit (sign bit) is- 0; in negative it is- 1. By shifting bits to the right (>>) the first bit can be captured.

During right shift the empty space is filled by the sign bit. So 01110001 >> 2 = 00011100, while 10110001 >> 2 = 11101100.

As a result, for 8 bit number shifting 7 bit will either produce- 1 1 1 1 1 1 1 [0 or 1] for negative, or 0 0 0 0 0 0 0 [0 or 1] for positive.

Now, if OR operation is performed with 00000001 (= 1), negative number yields- 11111111 (= -1), and positive- 00000001 (= 1).

So,

absolute(x)
= x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] )
= x * ( ( x >> (numberOfBitsInInteger-1) ) | 1 )
= x * ( ( x >> ((numberOfBytesInInteger*bitsInOneByte) - 1) ) | 1 )
= x * ( ( x >> ((sizeOf(int)*8) - 1) ) | 1 )

Finally,

getMax(a, b)
= ( a + b + absolute(a - b) ) / 2
= ( a + b + ((a-b) * ( ( (a-b) >> ((sizeOf(int)*8) - 1) ) | 1 )) ) / 2

---

Another way-

int getMax(int a, int b){
    int i[] = {a, b};
    return i[( (i[0]-i[1]) >> (sizeof(int)*8 - 1) ) & 1 ];
}

Answer 5

Here we go: (a + b) / 2 + |a - b| / 2

Answer 6

(sqrt( a*a + b*b - 2*a*b ) + a + b) / 2

This is based on the same technique as mike.dld's solution, but it is less "obvious" here what I am doing. An "abs" operation looks like you are comparing the sign of something but I here am taking advantage of the fact that sqrt() will always return you the positive square root so I am squaring (a-b) writing it out in full then square-rooting it again, adding a+b and dividing by 2.

You will see it always works: eg the user's example of 10 and 5 you get sqrt(100 + 25 - 100) = 5 then add 10 and 5 gives you 20 and divide by 2 gives you 10.

If we use 9 and 11 as our numbers we would get (sqrt(121 + 81 - 198) + 11 + 9)/2 = (sqrt(4) + 20) / 2 = 22/2 = 11