How does this min() function work?

Question

I came across this code:

int __min(int a, int b) {
    return ((a)-(((a)-(b))&((b)-(a))>>31));
}

I can imagine that it has something to do with the 2s complement, and that it only works for signed 32 bit integers, but after that I'm lost.

I found this question, but I don't think that the functions are related, or am I wrong?

So I have 2 questions:

1. Why does this function work?
2. Is there a situation where (a<b)?a:b wouldn't work and this function would, or is this function just overcomplicated for fun?

EDIT: The function is written for GPU, so I think @Banex might be right about the purpose of writing it like this being to avoid branching.

Answer 1

This is designed to work for 32 bit signed values. Let's break this down one step at a time.

((b)-(a))>>31)

The right shift operator essentially takes the highest bit in the 32 bit value, and sign-extends it to the remaining 31 bits. That's how the right shift operator works for signed values.

If b is greater than a, the result of the subtraction will be positive, the highest bit will be 0, and the result of this is 0.

If b is less than a, the result of the subtraction will be negative, the highest bit will be 1, and the result of this is -1. The highest bit gets shifted down to all the remaining bits. All bits in the 32 bit value will be set, which is -1.

You can verify this by yourself by writing a short program that places either a positive or a negative value into a 32 bit int, right-shifts it by 31 bits; then observing that the result will be either 0 or -1. As you know, in two-s complement arithmetic, the value -1 has all of its bits set.

((a)-(b)) & (0 or -1, as the result of the previous operation).

So, if b is less than a, the right hand side value has all bits set, and the result of the bitwise & operator is the left hand side value. or a-b.

If b is greater then a the right hand side value has all bits 0, and the result of the & is 0.

In conclusion:

If b is less than a, the above expression evaluates to:

a-(a-b)

or

a-a+b

or

b

And if b is greater than a, the result of the expression is

a - 0

or

a