Mathematically Find Max Value without Conditional Comparison

Question

----------Updated ------------

codymanix and moonshadow have been a big help thus far. I was able to solve my problem using the equations and instead of using right shift I divided by 29. Because with 32bits signed 2^31 = overflows to 29. Which works!

Prototype in PHP

$r = $x - (($x - $y) & (($x - $y) / (29)));

Actual code for LEADS (you can only do one math function PER LINE!!! AHHHH!!!)

DERIVDE1 = IMAGE1 - IMAGE2;
DERIVED2 = DERIVED1 / 29;
DERIVED3 = DERIVED1 AND DERIVED2;
MAX = IMAGE1 - DERIVED3;

----------Original Question----------- I don't think this is quite possible with my application's limitations but I figured it's worth a shot to ask.

I'll try to make this simple. I need to find the max values between two numbers without being able to use a IF or any conditional statement.

In order to find the the MAX values I can only perform the following functions

Divide, Multiply, Subtract, Add, NOT, AND ,OR

Let's say I have two numbers

A = 60;
B = 50;

Now if A is always greater than B it would be simple to find the max value

MAX = (A - B) + B;
ex. 
10 = (60 - 50)
10 + 50 = 60 = MAX

Problem is A is not always greater than B. I cannot perform ABS, MAX, MIN or conditional checks with the scripting applicaiton I am using.

Is there any way possible using the limited operation above to find a value VERY close to the max?

Answer 1

It depends which language you're using, but the Ternary Operator might be useful.

But then, if you can't perform conditional checks in your 'scripting application', you probably don't have the ternary operator.

Answer 2

Hmmm. I assume NOT, AND, and OR are bitwise? If so, there's going to be a bitwise expression to solve this. Note that A | B will give a number >= A and >= B. Perhaps there's a pruning method for selecting the number with the most bits.

To extend, we need the following to determine whether A (0) or B (1) is greater.

truth table:

0|0 = 0  
0|1 = 1
1|0 = 0
1|1 = 0

!A and B

therefore, will give the index of the greater bit. Ergo, compare each bit in both numbers, and when they are different, use the above expression (Not A And B) to determine which number was greater. Start from the most significant bit and proceed down both bytes. If you have no looping construct, manually compare each bit.

Implementing "when they are different":

(A != B) AND (my logic here)

Answer 3

If you can't trust your environment to generate the appropriate branchless operations when they are available, see this page for how to proceed. Note the restriction on input range; use a larger integer type for the operation if you cannot guarantee your inputs will fit.

Answer 4

finding the maximum of 2 variables:

max = a-((a-b)&((a-b)>>31))

where >> is bitwise right-shift (also called SHR or ASR depeding on signedness).

Instead of 31 you use the number of bits your numbers have minus one.

Answer 5

try this, (but be aware for overflows) (Code in C#)

    public static Int32 Maximum(params Int32[] values)
    {
        Int32 retVal = Int32.MinValue;
        foreach (Int32 i in values)
            retVal += (((i - retVal) >> 31) & (i - retVal));
        return retVal;        
    }

Answer 6

Using logical operations only, short circuit evaluation and assuming the C convention of rounding towards zero, it is possible to express this as:

int lt0(int x) {
    return x && (!!((x-1)/x));
}

int mymax(int a, int b) {
    return lt0(a-b)*b+lt0(b-a)*a;
}

The basic idea is to implement a comparison operator that will return 0 or 1. It's possible to do a similar trick if your scripting language follows the convention of rounding toward the floor value like python does.

Answer 7

#region GetMaximumNumber
/// <summary>
/// Provides method to get maximum values.
/// </summary>
/// <param name="values">Integer array for getting maximum values.</param>
/// <returns>Maximum number from an array.</returns>
private int GetMaximumNumber(params int[] values)
{
  // Declare to store the maximum number.
  int maximumNumber = 0;
  try
  {
    // Check that array is not null and array has an elements.
    if (values != null &&
        values.Length > 0)
    {
      // Sort the array in ascending order for getting maximum value.
      Array.Sort(values);

      // Get the last value from an array which is always maximum.
      maximumNumber = values[values.Length - 1];
    }
  }
  catch (Exception ex)
  {
    throw ex;
  }
  return maximumNumber;
}
#endregion

Answer 8

I guess this one would be the most simplest if we manage to find difference between two numbers(only the magnitude not sign)

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

where |a-b|=magnitude of difference between a & b

Answer 9

function Min(x,y:integer):integer;
  Var
   d:integer;
   abs:integer;
 begin
  d:=x-y;
  abs:=d*(1-2*((3*d) div (3*d+1)));
  Result:=(x+y-abs) div 2;
 end;