On some rare machines where branching is expensive, the below obvious approach to find minimum can be slow as it uses branching.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%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\u201d message=\u201dC programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Below are the methods to get minimum(or maximum) without using branching. Typically, the obvious approach is best, though.<\/p>\n
Method 1(Use XOR and comparison operator)<\/strong><\/p>\n Minimum of x and y will be<\/p>\n 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<\/p>\n Method 2(Use subtraction and shift)<\/strong> then we can use the following, which are faster because (x \u2013 y) only needs to be evaluated once.<\/p>\n Minimum of x and y will be<\/p>\n 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. Note that the 1989 ANSI C specification doesn\u2019t 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.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":" Compute the minimum or maximum of two integers without branching – Bit Algorithm – On some rare machines where branching is expensive below obvious approach <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,74852],"tags":[77109,77102,77107,77088,77108,77119,72715,77120,77112,69875,77117,77121,70501,77098,77087,77095,77111,74094,77097,77122,77116,77100,77092,74067,77094,77114,69884,77096,77099,77090,69870,72829,77113,77105,77089,77118,77101,77086,77093,77103,77106,77104,77115,77091,77110,72871,77085,74073,74062,74078],"class_list":["post-26106","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-bit-algorithms","tag-__gcd","tag-2-bit-adder-truth-table","tag-arduino-min","tag-atoi-header-file","tag-c-language-max","tag-c-max-function","tag-c-program-to-find-smallest-number-in-an-array","tag-code-for-gcd","tag-common-divisor","tag-find-hcf","tag-find-the-gcd-of-two-numbers","tag-flowchart-to-find-gcd-of-two-numbers","tag-gcd","tag-gcd-calculator","tag-gcd-code-in-c","tag-gcd-formula","tag-gcd-greatest-common-divisor","tag-gcd-in-c","tag-gcd-math","tag-gcd-number","tag-gcd-of-n-numbers","tag-gcd-of-three-numbers","tag-gcd-of-two-numbers","tag-gcd-program-in-c","tag-gcd-program-in-java","tag-gcd-properties","tag-hcf-of-two-numbers","tag-how-to-calculate-gcd","tag-how-to-find-gcd","tag-how-to-find-gcd-of-two-numbers","tag-how-to-find-hcf","tag-inarray","tag-java-math-min","tag-math-functions-in-c","tag-math-gcd","tag-math-max","tag-max-c","tag-max-inc","tag-max-number","tag-maximum-and-minimum","tag-mil","tag-min","tag-min-math","tag-program-for-gcd-in-c","tag-qlikview-absolute-value","tag-smallest-element","tag-stdlib-h","tag-write-a-program-to-find-gcd-of-two-numbers","tag-write-ac-program-for-finding-gcd-of-two-given-numbers","tag-write-ac-program-to-find-gcd-of-two-numbers"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26106","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26106"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26106\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26106"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26106"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26106"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}y ^ ((x ^ y) & -(x < y))<\/pre>\n
x ^ ((x ^ y) & -(x < y));<\/pre>\n[pastacode lang=\u201dc\u201d manual=\u201d%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\u201d message=\u201dC programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n
\nIf we know that<\/p>\nINT_MIN <= (x - y) <= INT_MAX<\/pre>\n
y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))<\/pre>\n
\nSo if x >= y, we get minimum as y + (x-y)&0 which is y.
\nIf x < y, we get minimum as y + (x-y)&1 which is x. Similarly, to find the maximum use<\/p>\nx - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))<\/pre>\n[pastacode lang=\u201dc\u201d manual=\u201d%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\u201d message=\u201dC programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n