Pascal Sommer Pascal Sommer - 1 month ago 5
C Question

How does this min() function work?

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

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
Comments