{"id":26004,"date":"2017-10-26T09:31:37","date_gmt":"2017-10-26T04:01:37","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26004"},"modified":"2017-10-26T09:31:37","modified_gmt":"2017-10-26T04:01:37","slug":"compute-integer-absolute-value-abs-without-branching","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/compute-integer-absolute-value-abs-without-branching\/","title":{"rendered":"Compute the integer absolute value (abs) without branching"},"content":{"rendered":"

We need not to do anything if a number is positive. We want to change only negative numbers. Since negative numbers are stored in 2\u2019s complement form, to get the absolute value of a negative number we have to toggle bits of the number and add 1 to the result.<\/p>\n

For example -2 in a 8 bit system is stored as follows 1 1 1 1 1 1 1 0 where leftmost bit is the sign bit. To get the absolute value of a negative number, we have to toggle all bits and add 1 to the toggled number i.e, 0 0 0 0 0 0 0 1 + 1 will give the absolute value of 1 1 1 1 1 1 1 0. Also remember, we need to do these operations only if the number is negative (sign bit is set).<\/p>\n

Method 1<\/strong>
\n1) Set the mask as right shift of integer by 31 (assuming integers are stored using 32 bits).<\/p>\n

mask = n>>31<\/pre>\n
For negative numbers, above step sets mask as 1 1 1 1 1 1 1 1 and 0 0 0 0 0 0 0 0 for positive numbers. Add the mask to the given number.<\/p>\n
 mask + n<\/pre>\n
3) XOR of mask +n and mask gives the absolute value.<\/p>\n
 (mask + n)^mask<\/pre>\n
Implementation:<\/strong><\/p>\n
 
 c<\/span> <\/div> 
#include <stdio.h>#define CHAR_BIT 8 \/* This function will return absoulte value of n*\/unsigned int getAbs(int n){  int const mask = n >> (sizeof(int) * CHAR_BIT - 1);  return ((n + mask) ^ mask);} \/* Driver program to test above function *\/int main(){  int n = -6;  printf("Absoute value of %d is %u", n, getAbs(n));   getchar();  return 0;}Run on IDE<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
Method 2:<\/strong>
\n1) Set the mask as right shift of integer by 31 (assuming integers are stored using 32 bits).<\/p>\n
 mask = n>>31<\/pre>\n
2) XOR the mask with number<\/p>\n
 mask ^ n<\/pre>\n
3) Subtract mask from result of step 2 and return the result.<\/p>\n
(mask^n) - mask<\/pre>\n
Implementation:<\/strong><\/p>\n
 <\/p>\n
 
 c<\/span> <\/div> 
\/* This function will return absoulte value of n*\/unsigned int getAbs(int n){  int const mask = n >> (sizeof(int) * CHAR_BIT - 1);  return ((n ^ mask) - mask);}<\/code><\/pre> <\/div>\n
On machines where branching is expensive, the above expression can be faster than the obvious approach, r = (v < 0) ? -(unsigned)v : v, even though the number of operations is the same.<\/p>\n[ad type=”banner”]\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Compute the integer absolute value without branching – Bit Algorithm – We need not do anything if a no is positive. We want to change only negative numbers.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[74852,83577],"tags":[75277,76557,76561,76550,76575,76566,76555,76576,76577,76559,76574,76556,76572,76560,76570,76568,76571,76563,76558,75266,75115,75083,75079,75269,75109,76549,75098,76564,76565,76552,76567,75281,76562,76554,75431,76578,76569,76573,76579,75291,76551,75118,75086,76553],"class_list":["post-26004","post","type-post","status-publish","format-standard","hentry","category-bit-algorithms","category-integer","tag-2-power-32-value","tag-abs-absolute","tag-abs-float","tag-abs-function","tag-abs-i","tag-abs-math-h","tag-absolute-abs","tag-absolute-square","tag-absolute-value-function","tag-absolute-value-graph","tag-absolute-value-in-math","tag-absolute-value-of-functions","tag-absolute-value-of-integers","tag-absolute-value-of-sinx","tag-absolute-value-problems","tag-absolute-value-sql","tag-absolute-value-symbol","tag-absolute-value-worksheets","tag-arduino-absolute-value","tag-binary-operation","tag-bit-manipulation","tag-bitwise-operations-in-c","tag-bitwise-operator-in-c","tag-bitwise-operators","tag-c-xor","tag-clearbit-absolute-value","tag-for-bit","tag-fortran-absolute-value","tag-how-to-calculate-absolute-value","tag-intabs","tag-latex-absolute-value","tag-magic-bit","tag-math-h-abs","tag-math-h-absolute-value","tag-math-operations","tag-mathematical-operators","tag-opencv-flip","tag-properties-of-absolute-value","tag-python-logical-operators","tag-twiddle","tag-twos-complement-calculator","tag-xor-operation-in-c","tag-xor-operator-in-c","tag-xslt-absolute-value"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26004","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=26004"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26004\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26004"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26004"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26004"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}