Which is the fastest way to get the absolute value of a number

There is a great trick to calculate the absolute value of a 2s-complement integer without using an if statement. The theory goes, if the value is negative you want to toggle the bits and add one, otherwise you want to pass the bits through as is. A XOR 1 happens to toggle A and A XOR 0 happens to leave A intact. So you want do something like this:

  uint32_t temp = value >> 31;     // make a mask of the sign bit
  value ^= temp;                   // toggle the bits if value is negative
  value += temp & 1;               // add one if value was negative

In principle, you can do it in as few as three assembly instructions (without a branch). And you'd like to think that the abs() function that you get with math.h does it optimally.

No branches == better performance. Contrary to @paxdiablo's response above, this really matters in deep pipelines where the more branches you have in your code, the more likely you are to have your branch predictor get it wrong and have to roll-back, etc. If you avoid branching where possible, things will keep moving along at full throttle in your core :).

Conditionals are slower than plain arithmetic operations, but much, much faster than something as silly as calculating the square root.

Rules of thumb from my assembly days:

• Integer or bitwise op: 1 cycle
• Floating-point add/sub/mul: 4 cycles
• Floating-point div: ~30 cycles
• Floating-point exponentiation: ~200 cycles
• Floating-point sqrt: ~60 cycles depending on implementation
• Conditional branch: avg. 10 cycles, better if well-predicted, much worse if mispredicted

Calculating the square root is probably one of the worst things you could do because it is really slow. Usually there is a library function for doing this; something like Math.Abs(). Multiplying with -1 is also unnecessary; just return -x. So a good solution would be the following.

(x >= 0) ? x : -x

The compiler will probably optimize this to a single instructions. Conditions may be quite expensive on modern processors because of the long execution pipelines -the calculations must be thrown away if a branch was misspredicted and the processor started executing the instructions from the wrong code path. But because of the mentioned compiler optimization you need not care in this case.

The if variant will almost certainly be blindingly fast compared to the square root, since it normally translates to a conditional jump instruction at the machine code level (following the evaluation of the expression, which may be complex, but not in this case since it's a simple check for less than 0).

Taking the square root of a number is likely to be much slower (Newton's method, for example, would use many many if statements at the machine code level).

The likely source of confusion is the fact that if invariably lead to changing the instruction pointer in a non-sequential manner. This can slow down processors that pre-fetch instructions into a pipeline since they have to re-populate the pipeline when the address changes unexpectedly.

However, the cost of that would be minuscule compared to performing a square root operation as opposed to a simple check-and-negate.

The modulo operation is used to find a remainder, you mean absolute value. I modified the question because it should be if !pos(x) then x = x*-1. (not was missing)

I wouldn't worry about the efficiency of an if statement. Instead focus on the readability of your code. If you identify that there is an efficiency problem, then focus on profiling your code to find real bottlenecks.

If you want to keep an eye out for efficiency while you code, you should only worry about the big-O complexity of your algorithms.

If statements are very efficient, it evaluates whatever expression and then simply changes the program counter based on that condition. The program counter stores the address of the next instruction to be executed.

Mulitplication by -1 and checking if a value is greater than 0 both can be reduced to a single assembly instruction.

Finding the root of a number and squaring that number first is definitely more operations than the if with a negation.

The time taken to do a square root is much greater than the time taken to do an conditional. If you have been taught to avoid conditionals because they are slow, then you have been misinformed. They are a good deal slower than trivial operations like adding or subtracting integers or bit shifting - which is why unrolling loops can be of benefit only if you are doing such trivial operations. But in the grand scheme of things conditionals are good and fast, not bad and slow. To do something as complicated as call a function or calculate a square root to avoid a conditional statement is crazy.

Also, instead of (x = x * -1) why not do (x = 0 - x)? Maybe the compiler will optimize them the same, but isn't the second one simpler anyway?

Are you using 8086 assembly? ;-)

                ; abs value of AX
   cwd          ; replicate the high bit into DX
   xor  ax, dx  ; take 1's complement if negative; no change if positive
   sub  ax, dx  ; AX is 2's complement if it was negative The standard
                : absolute value method works on any register but is much
                ; slower:

   or   bx, bx  ; see if number is negative
   jge  notneg  ; if it is negative...
   neg  bx      ; ...make it positive
notneg:         ; jump to here if positive

(flagrantly stolen)

For completeness, if you are dealing with floating point numbers, you can always do something like n * sign(n), where sign is a function that returns +1 if the number is positive, -1 if negative. In C this would be something like copysign(1.0, n) or (n > 0) - (n < 0).

Most machines use IEEE 754 as their floating point format these days, so you can clear the sign bit directly:

float fabs(float x) {
    char *c = &x;
    c[0] &= 7;
    return *(float *)c;
}

Given that the abs function likely does this exact thing, your best bet is to use it when available. If you are lucky the function will be a couple of instructions, and will be inlined.

I wonder, if something is wrong with this solution. There is

• no branching
• no bitwidth dependent shifting
• no bit twiddling
• no architecture dependency
• no compiler dependency
• optionally: no undefined behaviour for INT_MIN

Maybe too much instructions?

My solution

xabs = (x < 0)*(-x) + (x >=0)*x

• 2 integer comparisons
• 2 multiplications

Old solution

xtest = (x < 0)*x;           // xtest = x if is negative, otherwise zero
xabs = (x - xtest) - xtest;  // Order of instructions taken into account

Undefined behaviour of negating INT_MIN

A check against undefined behaviour (negation of INT_MIN) can be added, if your value is not limited in the algorithm somewhere before. But that makes it a little more complicated. Maybe, someone finds a simpler logic.

xabs =   (x < -INT_MAX)*INT_MAX            //  x < -INT_MAX < 0  --> xabs = INT_MAX
       + ((x >= -INT_MAX)&&(x < 0))*(-x)   // -INT_MAX =< x < 0  --> xabs = -x
       + (x >= 0)*x                        // 0 <= x             --> xabs = +x

• 5 integer comparisons
• 3 integer multiplications

Unfortunately, I never did a speed comparison. So I don't know if it is really faster than

if ( x < 0 )
{
  if ( x >= -INT_MAX )
  {
    x = -x;
  }
  else
  {
    x = INT_MAX;
  }
}
     

For a list of negative numbers:

if you have zero stored in memory, simply use 0 - x, where x is the negative number.

Or if you do not have zero stored in memory:

x-x-x, where x is the negative number.

Or, with brackets for clarity:

(x) - (x) - (x) => (-n) - (-n) - (-n), where x = -n

i.e. subtract the negative number from itself to get zero, then subtract it from zero.