37

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

8
  • Is the ternary operator allowed ?
    – cnicutar
    Aug 20, 2012 at 16:42
  • 1
    No, I guess you cannot use that too.
    – Pragyan
    Aug 20, 2012 at 16:43
  • 3
  • 1
    What's the motivation? Performance? Are you trying to solve a branch-predication failure by eliminating the branch? Intellectual curiosity? Homework? Something else? Aug 20, 2012 at 17:04
  • 2
    What is the proper answer for ABS(INT_MIN)? (use 8-bits for simplicity): ABS(-128) ideally should be 128. But the maximum signed 8-bit int is only 127!
    – abelenky
    Sep 4, 2014 at 15:18

11 Answers 11

101

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.

5
  • 4
    Upvote for the clear explanation, much better than the accepted answer!
    – Skiptomylu
    Aug 30, 2014 at 14:18
  • 1
    In C or C++, can't this result in undefined behavior? If x is INT_MIN, then the XOR operation will make x == INT_MAX, and adding 1 to INT_MAX is an overflow error (aka undefined behavior for signed integers) May 31, 2017 at 20:20
  • @JoshuaWise Well, I didn't assume a specific programming language, though. In that case, the signed right-shift would already be implementation-defined behaviour. Jul 26, 2017 at 15:37
  • Where should I start if I came here searching for ways to refine a solution I wrote on Hacker Rank and have literally no clue what any of the stuff in this answer means? For context: in my HR solution I implemented absolute value of i by checking if the value is less than 0 and, if so, doing i = i + (i * -2).
    – sixty4bit
    Oct 13, 2019 at 16:38
  • 1
    If you don't what any of the stuff in this answer means, I'm afraid you might have to look somewhere else. Your solution for the absolute value might work, too. It's not what was asked about, though. In general, for more information on how bitwise operations work, a general learning resource on those might work better than trying to crawl through SO answers. Oct 13, 2019 at 16:42
34
  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 
    
2
  • Keep in mind that not all languages intepret integer the same way. There are some that support positive and negative zero where abs(~int)-abs(int) results in 0 while your solution requires: abs(abs(~int)-abs(int)) beeing 1.
    – dhein
    Sep 22, 2015 at 13:19
  • @dhein What language has a -0 integer? I've not heard of any such language at this point. Maybe some really old hardware had such since it took a little bit of time for engineers to decide on which scheme to use, but I also don't know of any hardware that does that. As a side note, JavaScript does not have integers. They use double internally and handle the value as an integer in some cases. Jul 11, 2020 at 0:53
7

Assume int is of 32-bit.

int my_abs(int x)
{
    int y = (x >> 31);
    return (x ^ y) - y;
}
3

One can also perform the above operation as:

return n*(((n>0)<<1)-1);

where n is the number whose absolute need to be calculated.

3

In C, you can use unions to perform bit manipulations on doubles. The following will work in C and can be used for both integers, floats, and doubles.

/**
* Calculates the absolute value of a double.
* @param x An 8-byte floating-point double
* @return A positive double
* @note Uses bit manipulation and does not care about NaNs
*/
double abs(double x)
{
    union{
        uint64_t bits;
        double dub;
    } b;

    b.dub = x;

    //Sets the sign bit to 0
    b.bits &= 0x7FFFFFFFFFFFFFFF;

    return b.dub;
}

Note that this assumes that doubles are 8 bytes.

0
1

I wrote my own, before discovering this question.

My answer is probably slower, but still valid:

int abs_of_x = ((x*(x >> 31)) | ((~x + 1) * ((~x + 1) >> 31)));
1

If you are not allowed to use the minus sign you could do something like this:

int absVal(int x) {
  return ((x >> 31) + x) ^ (x >> 31);
}
0

For assembly the most efficient would be to initialize a value to 0, substract the integer, and then take the max:

pxor mm1, mm1 ; set mm1 to all zeros
psubw mm1, mm0 ; make each mm1 word contain the negative of each mm0 word
pmaxswmm1, mm0 ; mm1 will contain only the positive (larger) values - the absolute value
2
  • SSSE3 (Core2 and newer) directly has pabsw
    – harold
    Jan 25, 2018 at 17:00
  • yes indeed but question was tagged 'algorithm' so I assumed the author didn't want a library function or instruction that does the job automatically ;) Jan 25, 2018 at 17:22
0

In C#, you can implement abs() without using any local variables:

public static long abs(long d) => (d + (d >>= 63)) ^ d;

public static int abs(int d) => (d + (d >>= 31)) ^ d;

Note: regarding 0x80000000 (int.MinValue) and 0x8000000000000000 (long.MinValue):

As with all of the other bitwise/non-branching methods shown on this page, this gives the single non-mathematical result abs(int.MinValue) == int.MinValue (likewise for long.MinValue). These represent the only cases where result value is negative, that is, where the MSB of the two's-complement result is 1 -- and are also the only cases where the input value is returned unchanged. I don't believe this important point was mentioned elsewhere on this page.

The code shown above depends on the value of d used on the right side of the xor being the value of d updated during the computation of left side. To C# programmers this will seem obvious. They are used to seeing code like this because .NET formally incorporates a strong memory model which strictly guarantees the correct fetching sequence here. The reason I mention this is because in C or C++ one may need to be more cautious. The memory models of the latter are considerably more permissive, which may allow certain compiler optimizations to issue out-of-order fetches. Obviously, in such a regime, fetch-order sensitivity would represent a correctness hazard.

0

If you don't want to rely on implementation of sign extension while right bit shifting, you can modify the way you calculate the mask:

mask = ~((n >> 31) & 1) + 1

then proceed as was already demonstrated in the previous answers:

(n ^ mask) - mask
-1

What is the programming language you're using? In C# you can use the Math.Abs method:

int value1 = -1000;
int value2 = 20;
int abs1 = Math.Abs(value1);
int abs2 = Math.Abs(value2);
3
  • Well, I'm pretty sure that's also outruled by the question. Of course using a prebuilt functions is always easiest ;) Aug 20, 2012 at 16:51
  • I can see that now. Worth trying to help though. Good thing he got his answer. Aug 20, 2012 at 17:42
  • 2
    Always worth mentioning the obvious. Sometimes I find that the bitmask or branchless hacks that are supposed to be faster are really slower. All depends on the processor and the compiler. Oct 21, 2013 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.