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

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| is a magnitude of difference between a and b.

Answer 2

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 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

Solution without conditionals. Cast to uint then back to int to get abs.

int abs (a) { return (int)((unsigned int)a); }
int max (a, b) { return (a + b + abs(a - b)) / 2; }

int max3 (a, b, c) { return (max(max(a,b),c); }

Answer 5

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 6

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;

Answer 7

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 8

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 9

//Assuming 32 bit integers 
int is_diff_positive(int num)
{
    ((num & 0x80000000) >> 31) ^ 1; // if diff positive ret 1 else 0
}
int sign(int x)
{
   return ((num & 0x80000000) >> 31);
}

int flip(int x)
{
   return x ^ 1;
}

int max(int a, int b)
{
  int diff = a - b;

  int is_pos_a = sign(a);
  int is_pos_b = sign(b);

  int is_diff_positive = diff_positive(diff);
  int is_diff_neg = flip(is_diff_positive);

  // diff (a - b) will overflow / underflow if signs are opposite
  // ex: a = INT_MAX , b = -3 then a - b => INT_MAX - (-3) => INT_MAX + 3
  int can_overflow = is_pos_a ^ is_pos_b;
  int cannot_overflow = flip(can_overflow);
  int res = (cannot_overflow * ( (a * is_diff_positive) + (b * 
            is_diff_negative)) + (can_overflow * ( (a * is_pos_a) + (b * 
            is_pos_b)));

  return res;

}

Answer 10

This is my implementation using only +, -, *, %, / operators

using static System.Console;

int Max(int a, int b) => (a + b + Abs(a - b)) / 2;
int Abs(int x) => x * ((2 * x + 1) % 2);

WriteLine(Max(-100, -2) == -2); // true
WriteLine(Max(2, -100) == 2);   // true

Answer 11

I just came up with an expression: (( (a-b)-|a-b| ) / (2(a-b)) )*b + (( (b-a)-|b-a| )/(2(b-a)) )*a which is equal to a if a>b and is equal to b if b>a

when a>b: a-b>0, a-b = |a-b|, (a-b)-|a-b| = 0 so the coeficcient for b is 0

b-a<0, b-a = -|b-a|, (b-a)-|b-a| = 2(b-a) so the coeficcient for a is 2(b-a)/2(b-a) which is 1 so it would ultimately return 0*b+1*a if a is bigger and vice versa

Answer 12

Find MAX between n & m

MAX = ( (n/2) + (m/2) + ( ((n/2) - (m/2)) * ( (2*((n/2) - (m/2)) + 1) % 2) ) )

Using #define in c:

#define MAX(n, m) ( (n/2) + (m/2) + ( ((n/2) - (m/2)) * ( (2*((n/2) - (m/2)) + 1) % 2) ) )

or

#define ABS(n) ( n * ( (2*n + 1) % 2) )  // Calculates abs value of n
#define MAX(n, m) ( (n/2) + (m/2) + ABS((n/2) - (m/2)) )  // Finds max between n & m
#define MIN(n, m) ( (n/2) + (m/2) - ABS((n/2) - (m/2)) )  // Finds min between n & m

Answer 13

You can express this as a series of arithmetic and bitwise operations, e.g.:

int myabs(const int& in) {
  const int tmp = in >> ((sizeof(int) * CHAR_BIT) - 1);
  return tmp - (in ^ tmp(;
}

int mymax(int a, int b) {
    return ((a+b) + myabs(b-a)) / 2;
}

Answer 14

please look at this program.. this might be the best answer till date on this page...

#include <stdio.h>

int main()
{
    int a,b;
    a=3;
    b=5;
    printf("%d %d\n",a,b);
    b = (a+b)-(a=b); // this line is doing the reversal
    printf("%d %d\n",a,b);
    return 0;
}

Answer 15

If A is always greater than B .. [ we can use] .. MAX = (A - B) + B;

No need. Just use: int maxA(int A, int B){ return A;}

(1) If conditionals are allowed you do max = a>b ? a : b.

(2) Any other method either use a defined set of numbers or rely on the implicit conditional checks.

(2a) max = a-((a-b)&((a-b)>>31)) this is neat, but it only works if you use 32 bit numbers. You can expand it arbitrary large number N, but the method will fail if you try to find max(N-1, N+1). This algorithm works for finite state automata, but not a Turing machine.

(2b) Magnitude |a-b| is a condition |a-b| = a-b>0 a-b : b-a

What about:

Square root is also a condition. Whenever c>0 and c^2 = d we have second solution -c, because (-c)^2 = (-1)^2*c^2 = 1*c^2 = d. Square root returns the greatest in the pair. I comes with a build in int max(int c1, int c2){return max(c1, c2);}

Without comparison operator math is very symmetric as well as limited in power. Positive and negative numbers cannot be distinguished without if of some sort.

Answer 16

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 17

using System;
namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            float a = 101, b = 15;
            float max = (a + b) / 2 + ((a > b) ? a - b : b - a) / 2;            
        }
    }
}

Answer 18

#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