To prepare a video lecture on min and max functions, I would like to learn from the community about fundamentally different ways of implementing these functions, which I don’t know about. Fundamentally different - they are different in their logical sense, and not in implementation. I will write what I know, and in the answers I ask you to write what I could miss. Let's consider only signed numbers, with unsigned, the general principle is the same, but the formulas are slightly different.

First , the usual comparison:

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

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

 doz = a>=b?ab:0;

or

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

or

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

Then just write:

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

or by 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 borrowing during intermediate calculations, then we assume that doz is:

 doz = (ab)&~((ab)>>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 overwhelm the variables:

 max = (a+b)/2 + abs(ab)/2; min = (a+b)/2 - abs(ab)/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.

This is 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 still make a dozen formulas), namely the very idea? This is what I ask to share.

  • one
    Take Warren's book "Algorithmic Tricks for Programmers" - there are many such things ... - Harry
  • Unfortunately, there are only ways 2 and 3 from my list (at least in my edition), in two versions: with a sign and without a sign. - Zealint pm
  • one
    I think you are confusing abstraction and data storage. The int type is an abstraction that consists of 32 bits and it has clearly defined work rules, and the storage method (exactly how bits and bytes are in memory) is already the real location of the operand in memory. The compiler does this: it hides from the user the question of how and where it is stored, providing a data type that is clearly defined by the language standard. Moreover, if desired, all 32 bits can even be in different parts of memory, the compiler's task is to take this into account and perform the shift correctly. - Zealint
  • one
    I decided to systematize my views on the issue and wrote two articles. 1. The functions min (a, b) and max (a, b) for numbers with a sign 2. The functions min (a, b) and max (a, b) for unsigned numbers Articles are attached to the articles. In addition to the basic theory, experimental results are proposed. - Zealint
  • 3
    @Zealint you are mistaken. UB should be avoided even when doing dirty tricks. - Pavel Mayorov

1 answer 1

All methods except the first - very bad ideas.

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

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

Such tasks arise more often than you think:

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

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

  3. Structures. For structures, you can define the operation "minBy / maxBy" - finding the minimum or maximum for some field. At the same time, adding or subtracting structures as a whole may not be possible (for example, if in another field there is a string or an array).

  • With real numbers, I would argue. The fact is that, at least in IEEE-754, their comparison is performed through the interpretation of numbers as integers. If the numbers of the same sign are the integer representations of these numbers are ordered in the same way as their real values. - Zealint
  • @Zealint yes, but the language does not give access to the integer representations of real numbers - Pavel Mayorov
  • that is another question. My question was, what are the ways, you argue that the language does not allow something to do. In fact, there are languages ​​that give it to do. For example, assembler, c ++ and c. - Zealint
  • @Zealint is not, I argue that the question does not make sense. - Pavel Mayorov
  • 2
    Let's do it. I understand that I am for you - no one. This is good, and I even like it. But try to write to Henry Warren Jr., That most of his book about algorithmic stunts is bullshit, which has no meaning. The second point: the bug does not show up for the simple reason that when solving extremely difficult computational problems (for which everything is started), the implementation is sharpened for a specific machine and a specific compiler, when your UB, which everyone is so afraid of, has completely predictable behavior. Therefore, I propose to complete the deliberately losing argument for you - Zealint