How to compute the integer absolute value without using if
condition.
I guess we need to use some bitwise operation.
Can anybody help?
-
Is the ternary operator allowed ?– cnicutarAug 20, 2012 at 16:42
-
1No, I guess you cannot use that too.– PragyanAug 20, 2012 at 16:43
-
3graphics.stanford.edu/~seander/bithacks.html#IntegerAbs– ltjaxAug 20, 2012 at 16:54
-
1What's the motivation? Performance? Are you trying to solve a branch-predication failure by eliminating the branch? Intellectual curiosity? Homework? Something else?– Adrian McCarthyAug 20, 2012 at 17:04
-
2What 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!– abelenkySep 4, 2014 at 15:18
11 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 1
s for a negative number or all 0
s 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.
-
4Upvote for the clear explanation, much better than the accepted answer! Aug 30, 2014 at 14:18
-
1In 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 checkingif
the value is less than 0 and, if so, doingi = i + (i * -2)
. Oct 13, 2019 at 16:38 -
1If 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
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
XOR the mask with number
mask ^ n
Subtract mask from result of step 2 and return the result.
(mask^n) - mask
-
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 in0
while your solution requires:abs(abs(~int)-abs(int))
beeing 1.– dheinSep 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 usedouble
internally and handle the value as an integer in some cases. Jul 11, 2020 at 0:53
Assume int
is of 32-bit.
int my_abs(int x)
{
int y = (x >> 31);
return (x ^ y) - y;
}
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.
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.
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)));
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);
}
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
-
-
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
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)
and0x8000000000000000 (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 forlong.MinValue
). These represent the only cases where result value is negative, that is, where the MSB of the two's-complement result is1
-- 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.
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
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);
-
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
-
2Always 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