{"id":26106,"date":"2017-10-26T19:54:18","date_gmt":"2017-10-26T14:24:18","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26106"},"modified":"2017-10-26T19:54:18","modified_gmt":"2017-10-26T14:24:18","slug":"compute-minimum-maximum-two-integers-without-branching","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/compute-minimum-maximum-two-integers-without-branching\/","title":{"rendered":"Compute the minimum or maximum of two integers without branching"},"content":{"rendered":"

On some rare machines where branching is expensive, the below obvious approach to find minimum can be slow as it uses branching.<\/p>\n

C programming<\/span> <\/div> 
\/* The obvious approach to find minimum (involves branching) *\/int min(int x, int y){  return (x < y) ? x : y}<\/code><\/pre> <\/div>\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
y ^ ((x ^ y) & -(x < y))<\/pre>\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
x ^ ((x ^ y) & -(x < y));<\/pre>\n
 
 C programming<\/span> <\/div> 
#include<stdio.h> \/*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)); } \/* Driver program to test above functions *\/int main(){  int x = 15;  int y = 6;  printf("Minimum of %d and %d is ", x, y);  printf("%d", min(x, y));  printf("\\nMaximum of %d and %d is ", x, y);  printf("%d", max(x, y));  getchar();}<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
Method 2(Use subtraction and shift)<\/strong>
\nIf we know that<\/p>\n
INT_MIN <= (x - y) <= INT_MAX<\/pre>\n
then we can use the following, which are faster because (x – y) only needs to be evaluated once.<\/p>\n
Minimum of x and y will be<\/p>\n
y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))<\/pre>\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.
\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>\n
x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))<\/pre>\n
 
 C programming<\/span> <\/div> 
#include<stdio.h>#define CHAR_BIT 8 \/*Function to find minimum of x and y*\/int min(int x, int y){  return  y + ((x - y) & ((x - y) >>             (sizeof(int) * CHAR_BIT - 1))); } \/*Function to find maximum of x and y*\/int max(int x, int y){  return x - ((x - y) & ((x - y) >>            (sizeof(int) * CHAR_BIT - 1)));} \/* Driver program to test above functions *\/int main(){  int x = 15;  int y = 6;  printf("Minimum of %d and %d is ", x, y);  printf("%d", min(x, y));  printf("\\nMaximum of %d and %d is ", x, y);  printf("%d", max(x, y));  getchar();}<\/code><\/pre> <\/div>\n
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.<\/p>\n[ad type=”banner”]\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}]}}