Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

how does this bitwise expression help in finding the minimum and maximum between two integers?

https://www.geeksforgeeks.org/compute-the-minimum-or-maximum-max-of-two-integers-without-branching/

I was trying to find alternative ways of finding maximum and minimum between two integer and came across the following code which is used for the operation.can anyone please clarify the working and role of the bitwise operator in the code:

/*Function to find minimum of x and y*/
int min(int x, int y) 
{ 
    return y ^ ((x ^ y) & -(x < y)); 
} 

/*Function to find maximum of x and y*/
int max(int x, int y) 
{ 
    return x ^ ((x ^ y) & -(x < y));  
}
like image 849
Mr Josh Avatar asked Oct 21 '25 06:10

Mr Josh


1 Answers

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

-(x < y) will be 0 if x >= y and -1 (i.e. an int with all bits set) if x < y. Note that foo & -1 == foo and foo & 0 == 0 for all foo. So if x < y, we get y ^ x ^ y, which is equal to x because y ^ y cancels out. And otherwise we get y ^ 0, which is y. So we get x if x < y and y otherwise, which is exactly what you'd want from a function named min.

For max it's the same thing, except we return y if x < y and x otherwise.

like image 196
sepp2k Avatar answered Oct 22 '25 20:10

sepp2k