Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to compute the integer absolute value

How to compute the integer absolute value without using if condition. I guess we need to use some bitwise operation. Can anybody help?

like image 962
Pragyan Avatar asked Aug 20 '12 16:08

Pragyan


People also ask

How do you find the absolute value of an integer?

The absolute value of an integer is its distance from zero on the number line. The absolute value of +3 is 3, and the absolute value of -3 is 3. Thus, opposite integers have the same absolute value. Mathematicians use the symbol || for absolute value.

What is an absolute integer?

Absolute value of an integer is its numerical value without taking the sign into consideration. The absolute values of -9 = 9; the absolute value of 5 = 5 and so on.

What is the absolute value of the integer 5?

The absolute value of 5 is the distance of 5 from the 0. So you go 1, 2, 3, 4, 5. 5 is exactly 5 to the right of 0.


2 Answers

Same as existing answers, but with more explanations:

Let's assume a twos-complement number (as it's the usual case and you don't say otherwise) and let's assume 32-bit:

First, we perform an arithmetic right-shift by 31 bits. This shifts in all 1s for a negative number or all 0s for a positive one (but note that the actual >>-operator's behaviour in C or C++ is implementation defined for negative numbers, but will usually also perform an arithmetic shift, but let's just assume pseudocode or actual hardware instructions, since it sounds like homework anyway):

mask = x >> 31; 

So what we get is 111...111 (-1) for negative numbers and 000...000 (0) for positives

Now we XOR this with x, getting the behaviour of a NOT for mask=111...111 (negative) and a no-op for mask=000...000 (positive):

x = x XOR mask; 

And finally subtract our mask, which means +1 for negatives and +0/no-op for positives:

x = x - mask; 

So for positives we perform an XOR with 0 and a subtraction of 0 and thus get the same number. And for negatives, we got (NOT x) + 1, which is exactly -x when using twos-complement representation.

like image 60
Christian Rau Avatar answered Oct 06 '22 14:10

Christian Rau


  1. Set the mask as right shift of integer by 31 (assuming integers are stored as two's-complement 32-bit values and that the right-shift operator does sign extension).

    mask = n>>31  
  2. XOR the mask with number

    mask ^ n  
  3. Subtract mask from result of step 2 and return the result.

    (mask^n) - mask  
like image 40
Mady Avatar answered Oct 06 '22 13:10

Mady