get absolute value without using abs function nor if statement

Question

I was thinking how to get the absolute value of an integer without using if statement nor abs(). At first I was using shift bits left (<<), trying to get negative sign out of the range, then shift bits right back to where it be, but unfortunately it doesn't work for me. Please let me know why it isn't working and other alternatives ways to do it.

Answer 1

From Bit Twiddling Hacks:

int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here 
int const mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;

Answer 2

int abs(int v) 
{
  return v * ((v>0) - (v<0));
}

This code multiplies the value of v with -1 or 1 to get abs(v). Hence, inside the parenthesis will be one of -1 or 1.

If v is positive, the expression (v>0) is true and will have the value 1 while (v<0) is false (with a value 0 for false). Hence, when v is positive ((v>0) - (v<0)) = (1-0) = 1. And the whole expression is: v * (1) == v.

If v is negative, the expression (v>0) is false and will have the value 0 while (v<0) is true (value 1). Thus, for negative v, ((v>0) - (v<0)) = (0-1) = -1. And the whole expression is: v * (-1) == -v.

When v == 0, both (v<0) and (v>0) will evaluate to 0, leaving: v * 0 == 0.

Answer 3

Branchless:

int abs (int n) {
    const int ret[2] = { n, -n };
    return ret [n<0];
}

_{Note 4.7 Integral Conversions / 4: [...] If the source type is bool, the value false is converted to zero and the value true is converted to one.}

Answer 4

I try this code in C, and it works.

int abs(int n){
   return n*((2*n+1)%2); 
}

Hope this answer will be helpful.

Answer 5

Assuming 32 bit signed integers (Java), you can write:

public static int abs(int x)
{
    return (x + (x >> 31)) ^ (x >> 31);
}

No multiplication, no branch.

BTW, return (x ^ (x >> 31)) - (x >> 31); would work as well but it is patented. Yup!

Note: This code may take more then 10x longer then conditional statement (8bit Verison). This may be useful for Hardware programming System C etc

Answer 6

Try the following:

int abs(int n) 
{
  return sqrt(n*n);
}

Answer 7

No branches or multiplication:

int abs(int n) {
    int mask = n >> 31;
    return (mask & -n) | (~mask & n);
}

Answer 8

Didn't saw this one. For two's complement representation and 32 bit int

( n >> 31 | 1 ) * n

Answer 9

Here is another approach without abs(), if nor any logical/conditional expression: assume int is 32-bit integer here. The idea is quite simple: (1 - 2 * sign_bit) will convert sign_bit = 1 / 0 to -1 / 1.

unsigned int abs_by_pure_math( int a ) {
   return (1 - (((a >> 31) & 0x1) << 1)) * a;
}

Answer 10

If your language allows bool to int cast (C/C++ like):

float absB(float n) {
    return n - n * 2.0f * ( n < 0.0f );
}

Answer 11

There are multiple reasons left shifting the sign bit out and right shifting back in place (v << 1 >> 1):

• left shifting a signed type with a negative value has undefined behavior so it should not be used at all.
• casting the value to unsigned would have the desired effect: (unsigned)v << 1 >> 1 does get rid of the sign bit, if there are no padding bits, but the resulting value is the absolute value of v only on systems with sign+magnitude representation, which are vanishingly rare nowadays. On the ubiquitous 2's complement architecture, the resulting value for negative v is INT_MAX+1-v

Hasturkun's solution unfortunately has implementation defined behavior.

Here is a variation that is fully defined for systems with 2's complement representation for signed values:

int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here 
unsigned int mask = -((unsigned int)v >> (sizeof(unsigned int) * CHAR_BIT - 1));

r = ((unsigned int)v + mask) ^ mask;

Answer 12

What about this one:

#include <climits>

long abs (int n) { // we use long to avoid issues with INT MIN value as there is no positive equivalents.
    const long ret[2] = {n, -n};
    return ret[n >> (sizeof(int) * CHAR_BIT - 1)];    // we use the most significant bit to get the right index.
}

Answer 13

Bit-shifting is (in principle) implementation-defined, but conversion to a wider signed-integer-type will extend the sign-bit. If you interpret the hi-bits as an integer, they will be 0 or -1, which will let you invert the 2's complement:

int32_t abs(int32_t in)
{
  int64_t in64 = (int64_t)in;
  int32_t* ptr = (int32_t*)&in64;
  int32_t hi = *(++ptr); // assumes little-endian
  int32_t out = (in ^ hi) - hi;
  return out;
}

The above mechanism is the result of compiling the naive implementation with optimization turned on:

mov         eax,ecx  
cdq  
xor         eax,edx  
sub         eax,edx  

Answer 14

A simple one that avoids bitshifting:

value -= (value < 0) * value * 2;

• If value is positive, value < 0 evaluates to 0 so the multiplication result is 0. Nothing is subtracted from value.
• If value is 0, the multiplication result is also 0.
• If value is negative, value < 0 is true, which evaluates as 1, which is then multiplied by value * 2. Essencially you're subtracting the double of value from value, netting you its corresponding positive.

Answer 15

Bit shifting signed integers in the way you consider is undefined behaviour and thus not an option. Instead, you can do this:

int abs(int n) { return n > 0 ? n : -n; }

No if statements, just a conditional expression.

Answer 16

how about that:

value = value > 0 ? value: ~value + 1

its based on the fact that negative numbers are stored as 2's complement to there positive equivalent, and that one can build the 2's complement by first building the 1's complement and adding 1, so

 5 ->   0000 0101b
-5 ->  (1111 1010b) + 1 -> 1111 1011b 

what I did was basically to reverse this, so

-5 ->  1111 1011b
 5 -> (0000 0100b) + 1 -> 0000 0101b

I know it's a bit late but just had the same issue and landed here, hope this helps.

Answer 17

Use division (and wider math) to form an "if". Perhaps not efficient, yet branchless.

int abs_via_division(int v) {
  // is_neg:0 when v >= 0
  //        1 when v < 0
  int is_neg = (int) ((4LL * v) / (4LL * v + 1));
  return  v * (1 - is_neg*2);
}

Works for all int when long long wider than int, aside from the usual trouble with |INT_MIN|.

Answer 18

Use the ternary operator:

y = condition ? value_if_true : value_if_false;