CODEWITHSUNDEEP
cexpressionbitwise-operators
Mr Josh
Mr Josh

Reputation: 140

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));  
}

Upvotes: 4

Views: 3813

Answers (2)

dbush
dbush

Reputation: 224437

First let's look at this part:

-(x < y)

If the conditional is true, i.e. if x is less than y, than the parenthesized expression is 1 and the whole expression is -1. If the conditional is false then the expression has the value 0.

Now let's look at it in the context of the next level subexpression:

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

Based on the above condition, this will reduce to one of the following:

((x ^ y) & 0)     // x is larger or equal
((x ^ y) & -1)    // y is larger

Performing a bitwise AND with 0 results in all bits of the result being 0, so the first expression will be 0. The value -1, assuming two's complement representation, has all bits set to 1. So performing a bitwise AND with -1 will result in the value of the other operand.

So now looking at the full expression for max:

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

This translates to:

x ^ (0)        // x is larger or equal
x ^ (x ^ y)    // y is larger

In the first case, performing an XOR with 0 results in the value of the other operand so the final result is x. In the second case, ^ is associative so you can look at it as (x ^ x) ^ y XORing a number with itself results in 0, and XORing 0 with y gives you y.

The min function works similarly with y in place of x for the first operand:

y ^ (0)        // x is larger or equal
y ^ (x ^ y)    // y is larger

This will give the opposite result of max.

Upvotes: 4

sepp2k
sepp2k

Reputation: 370407

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.

Upvotes: 6

Related Questions