How does this MIN macro work?

Question

Forgive me if this is a stupid question. I can't figure out how the following MIN works:

#define MIN(x, y) (y) ^ ((x ^ y) & -(x < y)) 

Answer 1

A macro is a preprocessor directive, which means that wherever it is used, it will be replaced by the corresponding code fragment.

If you are editing MIN in your macro, I or someone else here should be able to explain this.

Example:

 #include<stdio.h> #define PLUS + int main() { printf("%d", (1 PLUS 3)); } 

That should just output 4 .

EDIT

Let your macro break.

We have

 (y) ^ ((x ^ y) & -(x < y)) 

• Take the last part, (x < y) . This is 1 if x less than y and 1 else. Therefore, -(x < y) will be 0xffffffff if x less and 0 else.

• So now ((x ^ y) & -(x < y)) becomes ((x ^ y) & 0xffffffff) , i.e. (x ^ y) if x is less than y and ((x ^ y) & 0) , i.e. 0 else.

• Therefore, the whole macro becomes (y) ^ (x ^ y) , i.e. x if x is less and (y) ^ 0 , i.e. y else. This is really required MIN .

Answer 2

If x is less than y, then:

• (x < y) is 1.
• -(x < y) is -1.
• ((x ^ y) & -(x < y)) is ((x ^ y) & -1) , which is (x ^ y) because (anything & -1) == anything , because -1 - all '1' bits.
• y ^ (x ^ y) is x because XOR is commutative and y is canceled.

If y is less than or equal to x, then:

• (x < y) is 0.
• -(x < y) is 0.
• ((x ^ y) & -(x < y)) is ((x ^ y) & 0) , which is 0 because (anything & 0) == 0 , because 0 is all the '0' bits .
• y ^ 0 - y .

Currently, a macro has a serious error: it needs parentheses around an external expression, or it will get confused with the operator precedence when used in other expressions. For example, MIN(2, 3) * 4 is currently expanding to (3) ^ ((2 ^ 3) & -(2 < 3)) * 4 , which evaluates to 7 instead of the correct 8, because the multiplication is done to the final XOR. It would also be nice to put parentheses around each argument substitution for the same reason:

 #define MIN(x, y) ((y) ^ (((x) ^ (y)) & -((x) < (y)))) 

The macro still only works if the platform uses two integer additions , and this may not be faster than the obvious MIN definition, which

 #define MIN(x, y) ((x) < (y) ? (x) : (y)) 

Answer 3

Note that if x < y , the result -(x < y) will be only 0. Thus, this will be equivalent:

 y ^ 0 

What is y .

• < doesn't really matter, it means less

Answer 4

In addition to the explanations posted by others in the comments, you should also be aware of side effects in macros when an argument is evaluated more than once during macro expansion.

In the case of the usual C-style definition of MIN(x,y) (for example, as indicated by @Boann), note that x, y expand twice . Your original definition extends x and y twice three times. Before reaching the points of sequence and short circuit evaluation, let's just say that the results can be unpredictable, to say the least (and may even vary depending on the compiler). This is one of the reasons many C ++ programmers believe that preprocessor macros are evil.

To see this in action, try both definitions with MIN(x++, y++) . For an even more evil possibility, we consider the case

 result = MIN( x, ShouldOnlyBeCalledOnce_BecauseThisFunctionHasSideEffects(y)); 

While the preprocessor still has its place (and there are things you can do with it that just cannot be done in any other way), in particular, C ++ is usually a good idea to determine what represents whether the preprocessor solution is in itself.
For example: when overloaded, the C ++ implementation initially gave us things like

 int min(int x, int y) { return (x < y) ? x : y); } some_other_type min(some_other_type x, some_other_type y) { return (x < y) ? x : y; } 

The templates gave us much more, as in:

 template <class T> const T& min (const T& a, const T& b) { return !(b < a) ? a : b; } 

Convenience of the macro, but without the side effects that may occur when the parameter is expanded more than once. By the way, if you are wondering why the test !( b < a) ? a : b; !( b < a) ? a : b; compared to (a < b) ? a : b; (a < b) ? a : b; , this is because if (a == b) , a must be returned and because it is less than the only relation that needs to be defined for a given type to support a wide range of containers (among other things).