Find the minimum or maximum of two integers without using branching

Given two integers, find their minimum and maximum without using branching.


 

Approach 1:

To find the minimum(x, y), we can use the expression y ^ ((x ^ y) & -(x < y))
 

Now if x is less than y, then -(x < y) will be -1 (all 1’s in binary representation), so

r = y ^ ((x ^ y) & -(x < y))
r = y ^ ((x ^ y) & -1)
r = y ^ (x ^ y)
r = x

If x is more than y, then -(x < y) will be 0, so

r = y ^ ((x ^ y) & -(x < y))
r = y ^ ((x ^ y) & 0)
r = y ^ 0
r = y
 

To find the maximum(x, y), we can use the expression x ^ ((x ^ y) & -(x < y))
 

Now if x is less than y, then -(x < y) will be -1 (all 1’s in binary representation), so

r = x ^ ((x ^ y) & -(x < y))
r = x ^ ((x ^ y) & -1)
r = x ^ (x ^ y)
r = x

If x is more than y, then -(x < y) will be 0, so

r = x ^ ((x ^ y) & -(x < y))
r = x ^ ((x ^ y) & 0)
r = x ^ 0
r = x

C++

Download   Run Code

Output:

min(2, 4) is 2
max(2, 4) is 4

 


 

Approach 2:

To find the minimum(x, y), we can use the expression y + ((x – y) & ((x – y) >> 31))
 

Now if x is less than y, then (x – y) >> 31 will be -1 (all 1’s in binary representation), so

r = y + ((x – y) & ((x – y) >> 31))
r = y + ((x – y) & -1)
r = y + (x – y)
r = x

If x is more than y, then (x – y) >> 31 will be 0, so

r = y + ((x – y) & ((x – y) >> 31))
r = y + ((x – y) & 0)
r = y + (0)
r = y

Similarly, we can find the maximum(x, y) by using x – ((x – y) & ((x – y) >> 31)). The explanation is left for the users as an exercise.

C++

Download   Run Code

Output:

min(2, 4) is 2
max(2, 4) is 4


 

References: https://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
 

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)
Loading...

 
Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of