What other fundamentally different ways of implementing the min and max functions do you know?

To prepare a video lecture on the min and max functions, I would like to learn from the community about fundamentally different ways to implement these functions, which I do not know about. Fundamentally different-these are those that differ in their logical meaning, and not in their implementation. I will write what I know, and in the answers I ask you to write what I might have missed. Let's consider only signed numbers, with unsigned ones the general principle is the same, but the formulas are slightly different. other.

First: normal comparison:

max = a>b?a:b;
min = a<b?a:b;

Second: first we define the function doz(a,b), which is equal to a-b if a>=b, and zero otherwise. This function can be implemented in many ways:

doz = a>=b?a-b:0;

Or

doz = (a-b)&-(a>=b)

Or

d = a-b;
doz = (d&(~(d^((a^b)&(d^a))) >> 31));

Then just write:

max = b + doz(a,b);
min = a - doz(a,b);

Or, combining ideas:

max = ((a^b)&-(a>=b))^b;
min = ((a^b)&-(a<=b))^b;

Third: if we know for sure that there will be no overflow or loan in the intermediate calculations, then we consider doz as follows:

doz = (a-b)&~((a-b)>>31);

At the same time, min and max are calculated using doz as above.

Fourth: we also assume that the difference and the sum do not overflow the variables:

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

At the same time, we implement the abs function in a variety of ways (several options can be found here), this does not change the idea.

That's all I know (I hope I didn't make any typos). Are there any other ways that differ from these fundamentally, that is, not by rearranging operations or replacing some actions with similar ones (otherwise, you can add a dozen more formulas), namely, by the idea itself? That's what I'm asking you to share.

Author: Zealint, 2016-04-06

1 answers

All methods except the first one are extremely bad ideas.

The fact is that the functions min and max are defined on any linearly ordered sets - and can be applied to them. In other words, in order for the functions min and max to make sense, a single comparison operator is sufficient.

All alternative methods use additional operators - and therefore cannot be applied on those sets where these operations are not defined.

Such tasks occur more often than you think:

  1. Lines. The lexicographic order is defined on the lines - but the lines cannot be added and subtracted. Even if you define addition as a concatenation, it has the wrong properties in relation to lexicographic order.

  2. Real numbers. The min/max implementation based on the comparison does not lose accuracy. Implementations through addition and subtraction lead to a loss of accuracy. Bit operations are not defined.

  3. Structures. For structures, you can define the "minBy/maxBy" operations - finding the minimum or maximum for a certain field. At the same time, you may not be able to add or subtract the entire structure (for example, if there is a string or an array in another field).

 3
Author: Pavel Mayorov, 2016-11-23 10:40:09