On some rare machines where branching is expensive, the below obvious approach to find minimum can be slow as it uses branching.
[pastacode lang=”c” manual=”%2F*%20The%20obvious%20approach%20to%20find%20minimum%20(involves%20branching)%20*%2F%0Aint%20min(int%20x%2C%20int%20y)%0A%7B%0A%20%20return%20(x%20%3C%20y)%20%3F%20x%20%3A%20y%0A%7D” message=”C programming” highlight=”” provider=”manual”/]Below are the methods to get minimum(or maximum) without using branching. Typically, the obvious approach is best, though.
Method 1(Use XOR and comparison operator)
Minimum of x and y will be
y ^ ((x ^ y) & -(x < y))
It works because if x < y, then -(x < y) will be all ones, so r = y ^ (x ^ y) & ~0 = y ^ x ^ y = x. Otherwise, if x >= y, then -(x < y) will be all zeros, so r = y ^ ((x ^ y) & 0) = y. On some machines, evaluating (x < y) as 0 or 1 requires a branch instruction, so there may be no advantage. To find the maximum, use
x ^ ((x ^ y) & -(x < y));[pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%20%0A%2F*Function%20to%20find%20minimum%20of%20x%20and%20y*%2F%0Aint%20min(int%20x%2C%20int%20y)%0A%7B%0A%20%20return%20y%20%5E%20((x%20%5E%20y)%20%26%20-(x%20%3C%20y))%3B%0A%7D%0A%20%0A%2F*Function%20to%20find%20maximum%20of%20x%20and%20y*%2F%0Aint%20max(int%20x%2C%20int%20y)%0A%7B%0A%20%20return%20x%20%5E%20((x%20%5E%20y)%20%26%20-(x%20%3C%20y))%3B%20%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0Aint%20main()%0A%7B%0A%20%20int%20x%20%3D%2015%3B%0A%20%20int%20y%20%3D%206%3B%0A%20%20printf(%22Minimum%20of%20%25d%20and%20%25d%20is%20%22%2C%20x%2C%20y)%3B%0A%20%20printf(%22%25d%22%2C%20min(x%2C%20y))%3B%0A%20%20printf(%22%5CnMaximum%20of%20%25d%20and%20%25d%20is%20%22%2C%20x%2C%20y)%3B%0A%20%20printf(%22%25d%22%2C%20max(x%2C%20y))%3B%0A%20%20getchar()%3B%0A%7D” message=”C programming” highlight=”” provider=”manual”/] [ad type=”banner”]
Method 2(Use subtraction and shift)
If we know that
INT_MIN <= (x - y) <= INT_MAX
then we can use the following, which are faster because (x – y) only needs to be evaluated once.
Minimum of x and y will be
y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))
This method shifts the subtraction of x and y by 31 (if size of integer is 32). If (x-y) is smaller than 0, then (x -y)>>31 will be 1. If (x-y) is greater than or equal to 0, then (x -y)>>31 will be 0.
So if x >= y, we get minimum as y + (x-y)&0 which is y.
If x < y, we get minimum as y + (x-y)&1 which is x. Similarly, to find the maximum use
x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))[pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%23define%20CHAR_BIT%208%0A%20%0A%2F*Function%20to%20find%20minimum%20of%20x%20and%20y*%2F%0Aint%20min(int%20x%2C%20int%20y)%0A%7B%0A%20%20return%20%20y%20%2B%20((x%20-%20y)%20%26%20((x%20-%20y)%20%3E%3E%20%0A%20%20%20%20%20%20%20%20%20%20%20%20(sizeof(int)%20*%20CHAR_BIT%20-%201)))%3B%20%0A%7D%0A%20%0A%2F*Function%20to%20find%20maximum%20of%20x%20and%20y*%2F%0Aint%20max(int%20x%2C%20int%20y)%0A%7B%0A%20%20return%20x%20-%20((x%20-%20y)%20%26%20((x%20-%20y)%20%3E%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20(sizeof(int)%20*%20CHAR_BIT%20-%201)))%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0Aint%20main()%0A%7B%0A%20%20int%20x%20%3D%2015%3B%0A%20%20int%20y%20%3D%206%3B%0A%20%20printf(%22Minimum%20of%20%25d%20and%20%25d%20is%20%22%2C%20x%2C%20y)%3B%0A%20%20printf(%22%25d%22%2C%20min(x%2C%20y))%3B%0A%20%20printf(%22%5CnMaximum%20of%20%25d%20and%20%25d%20is%20%22%2C%20x%2C%20y)%3B%0A%20%20printf(%22%25d%22%2C%20max(x%2C%20y))%3B%0A%20%20getchar()%3B%0A%7D” message=”C programming” highlight=”” provider=”manual”/]
Note that the 1989 ANSI C specification doesn’t specify the result of signed right-shift, so above method is not portable. If exceptions are thrown on overflows, then the values of x and y should be unsigned or cast to unsigned for the subtractions to avoid unnecessarily throwing an exception, however the right-shift needs a signed operand to produce all one bits when negative, so cast to signed there.
[ad type=”banner”]