Finding minimum using bit manipulation

Question

Can anybody explain to me the following line of code. It is used to find the minimum of two numbers.

int min(int x, int y)

{

  return  y + ((x - y) & ((x - y) >>
            (sizeof(int) * CHAR_BIT - 1)));

}

Thanks in advance.

Answer 1

This part has the value -1 if x<y, and 0 otherwise:

(x - y) >> (sizeof(int) * CHAR_BIT - 1)

It accomplishes this by an arithmetic shift of 31 bits (or 63 if using 64-bit ints, etc). An arithmetic shift preserves the sign-bit, so for negative values you'll get a result where all bits are 1, and for positive values you'll get a result where all bits are 0. So for example, if x=2 and y=4:

(2 - 4) >> (sizeof(int) * CHAR_BIT - 1)
== (-2) >> (4 * 8 -1)
== (-2) >> 31
== 0xFFFFFFFE >> 31
== 0xFFFFFFFF 
== -1

This value is then used to mask (x - y). That is, you'll get (x - y) & -1 == (x - y) if x<y, and (x - y) & 0 == 0 otherwise.

Finally, that value is added to y, resulting in either y + (x - y) == x, or y + 0 == y.