Trivia for the weekend: MIN and MAX without conditional statements

Reply

CryptoKnight replied on 02-20-2006 2:08 AM

rated by 0 users

cvega wrote:

Obtain the MIN and MAX value of two given integers WITHOUT using any C# conditional statements:

int a = 1001;
int b = 2002;

int min = GetMinValue( a, b );
int max = GetMaxValue( a, b );

MessageBox.Show( "MIN = " + min.ToString() +
                 "; MAX = " + max.ToString() );

Replace GetMinValue and GetMaxValue with your calculation. Again, let me remind you that there will be no usage of conditional statements.

You cant do this:
           int min = ( a > b ? b : a );

Neither this:
       int min; if ( a > b ) min = b; else min = a;

The solution is doable in pure managed code, thus can also be done in VB.NET.
I'll post the answer in Tuesday, if no one got the correct answer. It would be better if you can do this without the help of google

Comment: Dont use Math.Min and Math.Max too (Thanks Jeff!)

Cheers,

-chris

Reply

cvega replied on 02-20-2006 7:09 PM

rated by 0 users

Here's the answer for the current problem

Formula:

The general formula in getting the max (highest amongst) and min (lowest amongst) between two integers (a and b) are these:

  min = ( ( a + b ) - abs( a - b ) ) / 2
  max = ( ( a + b ) + abs( a - b ) ) / 2

Or in much lower level approach of using sign-bit, are these:

  min = a + ( ( signbit( b - a ) ) and ( b - a ) )
  max = b - ( ( signbit( b - a ) ) and ( b - a ) )

Using the formula above, we can complete the solution to the problem as following:

First approach, using the first formula

int a = 1001;
int b = 2002;

// Bit shifting 1 step to the right is equivalent to
// "divide by 2", and abs is available in Math class
int min = ( ( a + b ) - Math.Abs( a - b ) ) >> 1;
int max = ( ( a + b ) + Math.Abs( a - b ) ) >> 1;

MessageBox.Show( "MIN = " + min.ToString() +
                 "; MAX = " + max.ToString() );

Second approach, using the second formula

int a = 1001;
int b = 2002;

// Bit shifting 31 step to the right means we are
// extracting the most significant bit of a 32-bit
// integer, which is treated as a sign-bit in a
// two's complement method.
int min = a + ( ( ( b - a ) >> 31 ) & ( b - a ) );
int max = b - ( ( ( b - a ) >> 31 ) & ( b - a ) );

MessageBox.Show( "MIN = " + min.ToString() +
                 "; MAX = " + max.ToString() );


And the winners

From the 6 submissions I received, CryptoKnight got the most accurate solution using the first approach, here is his submission:

Here's my SQL code
    declare @n1 int, @n2 int
    SET @n1 = 0
    SET @n2 = 123
    SELECT 'MAX', (abs(@n1 + @n2) + abs(@n1 - @n2)) / 2
    SELECT 'MIN', (abs(@n1 + @n2) - abs(@n1 - @n2)) / 2

Here's the C# conversion...
    private int GetMinValue(int a, int b)
    {
        return ((a + b) - Math.Abs(a - b)) / 2;
    }

    private int GetMaxValue(int a, int b)
    {
        return ((a + b) + Math.Abs(a - b)) / 2;
    }

And punzie got the solution riding on the same line as second approach, by using the sign-bit to index an array of two elements (he sent this solution few minutes after I posted the question):

public int MyMin(int x, int y)
{
    int[] holder = new int[2];
    holder[0] = x;
    holder[1] = y;
    int signBit = ((y - x) >> 31) & 1;
    return holder[signBit];
}

public int MyMax(int x, int y)
{
    int[] holder = new int[2];
    holder[0] = x;
    holder[1] = y;
    int signBit = ((x - y) >> 31) & 1;
    return holder[signBit];
}

The other 4 solutions I received also solved the problem, and all 4 solutions are in the same line of Array sorting, and reversing; same the what posted by Keith above.


Practical usage

One of the 6 who respond asked a question "what is the practical use of this"? Well, I could say that this is designed mainly for programming challenges and there's no actual practical usage; however I did used this on one of my project few years ago, when I was adding line numbers and collapsing feature in a RichTextBox control, where I used the second approach to calculate which line has the most and least number of characters in the entire RTB contents, and this is the exact functions I used that time (it accepts number of characters per line in an array, or an array of integers in general):

  private int GetMinInArray(int [] array)
  {
   int min = int.MaxValue/2;
   int ubound = array.Length;

   for(int i=0; i<ubound; i++) 
   {
    min = min + ( ( ( array[ i ] - min ) >> 31 ) &
                    ( array[ i ] - min ) );
   }
   return min;
  }

  private int GetMaxInArray(int [] array)
  {
   int max = int.MinValue/2;
   int ubound = array.Length;

   for(int i=0; i<ubound; i++)
   {
    max = max - ( ( ( max - array[ i ] ) >> 31 ) &
                    ( max - array[ i ] ) );
   }
   return max;
  }

And this is the code for I created just now for testing the above functions:

   int [] ary = new int[30]
       {
        2100, 2002, 5005, 501, 3003,
        2001, 999, 5602, 120, 1203,
        892, 8391, 119, 3102, 4001,
        192, 5112, 3621, 6721, 0122,
        6310, 8921, 4325, 1011, 0912,
        7683, 3999, 1102, 9123, 0184
       };

   int min = GetMinInArray(ary);
   int max = GetMaxInArray(ary);

   MessageBox.Show( "MIN = " + min.ToString() +
    "; MAX = " + max.ToString() );


Closing

Again, thanks for participating in this problem solving; and complements to all who got the right solution. Hope to see you again on our next problem solving.

Best regards to all,

-chris