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?

Solution 1

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.

Solution 2

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.

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

Solution 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); }

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

View more solutions

Comments

[ChssPly76]

Can't do this without shift (and knowing the size of type in bytes).

[Roee Adler]

+1 Note this is only for 32 bits. If the numbers are 8/16/64 bits - the "31" needs to be altered accordingly.

[Stefan Kendall]

Yes you can. Just and with 2**bit_index to get your comparison numbers.

[Alex]

If you are not allowed to do shifts: int max(int a, int b){ int c = a - b; int d = c & 0x7000; int e = d * -1; int f = e + 1; int g = f & 0x1; return (g * a) | ((g*-1) * b); } I used different variables so you can see what happens at each step.

[strager]

In C, sign extension is not required, IIRC, so your code may not work. Also, to be more portable, replace 31 with sizeof(type)*8-1.

[Stefan Kendall]

Remember that "shift" is just multiply/divide by 2.

[Brian Postow]

I'm sure if they can't use if, they can't use ?: either

[Almost Famous]

No conditional statements available in the language.

[Nightwolf]

iftrue, is there a way to implement "and when they are different" without a conditional?

[codymanix]

but not if the shift involves the sign-bit which is the case in my proposal (>>31)

[Almost Famous]

@codymanix: An undocumented scripting language used through a weather applications called LEADS.

[pavium]

@Brian, that what I said, and got downvoted for it. Maybe conditional statements aren't allowed in answers, too.

[Almost Famous]

I did try to implement this method and did not achieve desired results. This did help me figure out that my values are not being rounded down but unfort being converted to doubles. AHH!

[Ajay Yadav]

myabs(-6) and myabs(6) is giving -6. so it should be return (in ^ tmp) - tmp;

[tsenapathy]

right shift a negative number behaviour is implementation dependent, as shown here

[Roman Dzhabarov]

Absolutely irrelevant and for max number in array inefficient.

[Brian S]

This answer was exceptionally helpful. It also led me to min = ((a+b)-|a-b|)/2. Thanks a bunch!

[sixtytrees]

It translates symmetric relative to zero (-c;c) pair to asymmetric relative to zero pair (1;0) pair. This is done by implicit if embedded in rounding convention.

[Luxspes]

Actually, sqrt does not have a second solution, not for a particular input, sqrt is a function: brilliant.org/wiki/plus-or-minus-square-roots

[Et7f3XIV]

what it this langage ? natural langage ? beautiful you only use elementary operator

[Martheen]

Years ago I have a calculator that allows storing simple formulas, but no conditionals or functions like abs or min/max. I wish I know this back then, so many possibilities.

[dubek]

@Et7f3XIV this looks like Pascal programming language.

[chux - Reinstate Monica]

In C, this abs (a) does not return the absolute value when a < 0.

[Ran Marciano]

Please don't post only code as an answer, but also provide an explanation of what your code does and how it solves the problem of the question. Answers with an explanation are usually more helpful and of better quality, and are more likely to attract upvotes

[BDL]

The question asks for a solution without Conditional Comparison. The ? operator is a conditional comparison.

[Shmil The Cat]

does not work when a == b