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.
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:
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.
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.
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).