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

Guess we can just multiply the numbers with their bitwise comparisons eg:

int max=(a>b)*a+(a<=b)*b;

Answer 2

static int mymax(int a, int b)

    {
        int[] arr;
        arr = new int[3];
        arr[0] = b;
        arr[1] = a;
        arr[2] = a;
        return arr[Math.Sign(a - b) + 1];

    }

If b > a then (a-b) will be negative, sign will return -1, by adding 1 we get index 0 which is b, if b=a then a-b will be 0, +1 will give 1 index so it does not matter if we are returning a or b, when a > b then a-b will be positive and sign will return 1, adding 1 we get index 2 where a is stored.

Answer 3

There is one way

 public static int Min(int a, int b)
  {
   int dif = (int)(((uint)(a - b)) >> 31);
   return a * dif + b * (1 - dif);
  }

and one

return (a>=b)?b:a;

Answer 4

The code which I am providing is for finding maximum between two numbers, the numbers can be of any data type(integer, floating). If the input numbers are equal then the function returns the number.

double findmax(double a, double b)
{
    //find the difference of the two numbers
    double diff=a-b;
    double temp_diff=diff;
    int int_diff=temp_diff;
    /*
      For the floating point numbers the difference contains decimal
      values (for example 0.0009, 2.63 etc.) if the left side of '.' contains 0 then we need
      to get a non-zero number on the left side of '.'
    */
    while ( (!(int_diff|0)) && ((temp_diff-int_diff)||(0.0)) )
    {
       temp_diff = temp_diff * 10;
       int_diff = temp_diff;
    }
    /*
      shift the sign bit of variable 'int_diff' to the LSB position and find if it is 
      1(difference is -ve) or 0(difference is +ve) , then multiply it with the difference of
      the two numbers (variable 'diff') then subtract it with the variable a.
    */
    return a- (diff * ( int_diff >> (sizeof(int) * 8 - 1 ) & 1 ));
}

Description

• The first thing the function takes the arguments as double and has return type as double. The reason for this is that to create a single function which can find maximum for all types. When integer type numbers are provided or one is an integer and other is the floating point then also due to implicit conversion the function can be used to find the max for integers also.
• The basic logic is simple, let's say we have two numbers a & b if a-b>0(i.e. the difference is positive) then a is maximum else if a-b==0 then both are equal and if a-b<0(i.e. diff is -ve) b is maximum.

• The sign bit is saved as the Most Significant Bit(MSB) in the memory. If MSB is 1 and vice-versa. To check if MSB is 1 or 0 we shift the MSB to the LSB position and Bitwise & with 1, if the result is 1 then the number is -ve else no. is +ve. This result is obtained by the statement:

  int_diff >> (sizeof(int) * 8 - 1 ) & 1

Here to get the sign bit from the MSB to LSB we right shift it to k-1 bits(where k is the number of bits needed to save an integer number in the memory which depends on the type of system). Here k= sizeof(int) * 8 as sizeof() gives the number of bytes needed to save an integer to get no. of bits, we multiply it with 8. After the right shift, we apply the bitwise & with 1 to get the result.

• Now after obtaining the result(let us assume it as r) as 1(for -ve diff) and 0(for +ve diff) we multiply the result with the difference of the two numbers, the logic is given as follows:

  1. if a>b then a-b>0 i.e., is +ve so the result is 0(i.e., r=0). So a-(a-b)*r => a-(a-b)*0, which gives 'a' as the maximum.
  2. if a < b then a-b<0 i.e., is -ve so the result is 1(i.e., r=1). So a-(a-b)*r => a-(a-b)*1 => a-a+b =>b , which gives 'b' as the maximum.

• Now there are two remaining points 1. the use of while loop and 2. why I have used the variable 'int_diff' as an integer. To answer these properly we have to understand some points:

  1. Floating type values cannot be used as an operand for the bitwise operators.
  2. Due to above reason, we need to get the value in an integer value to get the sign of difference by using bitwise operators. These two points describe the need of variable 'int_diff' as integer type.
  3. Now let's say we find the difference in variable 'diff' now there are 3 possibilities for the values of 'diff' irrespective of the sign of these values. (a). |diff|>=1 , (b). 0<|diff|<1 , (c). |diff|==0.
  4. When we assign a double value to integer variable the decimal part is lost.
  5. For case(a) the value of 'int_diff' >0 (i.e.,1,2,...). For other two cases int_diff=0.
  6. The condition (temp_diff-int_diff)||0.0 checks if diff==0 so both numbers are equal.
  7. If diff!=0 then we check if int_diff|0 is true i.e., case(b) is true
  8. In the while loop, we try to get the value of int_diff as non-zero so that the value of int_diff also gets the sign of diff.

Answer 5

The simplest answer is below.

#include <math.h>

int Max(int x, int y)
{
    return (float)(x + y) / 2.0 + abs((float)(x - y) / 2);
}

int Min(int x, int y)
{
    return (float)(x + y) / 2.0 - abs((float)(x - y) / 2);
}

Answer 6

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

Let's dissect this. This first line seems like it out to be straightforward - it stores the difference of a and b. This value is negative if a < b and is nonnegative otherwise. There's actually a bug here - if the difference of the numbers a and b is so big that it can't fit into an integer, this will lead to undefined behavior - oops! So let's assume that doesn't happen here.

In the next line, which is

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

the idea is to check if the value of c is negative. 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.

The final step is to do this:

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

Which is also the correct max.