Find out max & min of two number without using If else?

Question

I am able to find out the logic from: Here

r = y ^ ((x ^ y) & -(x < y)); // min(x, y)
r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

It says it is faster then doing

r = (x < y) ? x : y

Can someone explain a bit more about it to understand it with example. How it could be faster?

Answer 1

Discussing optimization without a specific hardware in mind doesn't make any sense. You really can't tell which alternative that is fastest without going into details of a specific system. Boldly making a statement about the first alternative being fastest without any specific hardware in mind, is just pre-mature optimization.

The obscure xor solution might be faster than the comparison alternative if the given CPU's performance relies heavily on branch prediction. In other words, if it executes regular instructions such as arithmetic ones very fast, but gets a performance bottleneck at any conditional statement (such as an if), where the code might branch on several ways. Other factors such as the amount instruction cache memory etc. also matter.

Many CPUs will however execute the second alternative much faster, because it involves fewer operations.

So to sum it up, you'll have to be an expert of the given CPU to actually tell in theory which code that will be the fastest. If you aren't such an expert, simply benchmark it and see. Or look at the disassembly for notable differences.

Answer 2

In the link that you provided, it is explicitly stated:

On some rare machines where branching is very expensive and no condition move instructions exist, the [code] might be faster than the obvious approach, r = (x < y) ? x : y

Later on, it says:

On some machines, evaluating (x < y) as 0 or 1 requires a branch instruction, so there may be no advantage.

In short, the bit manipulation solution is only faster on machines that have poor branch execution, as it operates solely on the numerical values of the operands. On most machines the branching approach is just as fast (and sometimes even faster) and should be preferred for its readability.