</>EmbeddedInterview

How do you find the absolute value without branching?

MediumBit Manipulation

Short answer: Make a mask that is all ones for negative numbers and zero otherwise (mask = x >> 31), then compute (x + mask) ^ mask. It relies on an arithmetic right shift and fails for INT32_MIN.

#include <stdint.h>

int32_t abs_branchless(int32_t x)
{
    int32_t mask = x >> 31;        /* 0 if x >= 0, -1 (all ones) if x < 0 */
    return (x + mask) ^ mask;
}

Walk-through for x = -5

  • mask = -1 (0xFFFFFFFF)
  • x + mask = -6 (0xFFFFFFFA)
  • -6 ^ -1 = ~(-6) = 5

For x = 5, the mask is 0 and (5 + 0) ^ 0 = 5.

Why it works: for negative x, (x - 1) inverted is -(x - 1) - 1 = -x. Two's complement negation is "invert and add one"; this does "subtract one and invert", which is the same thing.

Limitations

  1. x >> 31 on a negative signed value is implementation-defined (arithmetic on GCC/Clang/Arm, but not guaranteed by the standard).
  2. abs(INT32_MIN) cannot be represented; the result is INT32_MIN again, and with the plain -x form it is undefined behaviour.

Why branchless was used: on older CPUs a mispredicted branch was expensive, and in cryptographic code a branch on secret data leaks timing information.

In practice: write x < 0 ? -x : x or abs(x). GCC and Clang already generate branchless code for it (on Arm, CMP plus a conditional negate or CSNEG on AArch64). Branchless tricks are worth knowing for interviews and constant-time code, not for everyday firmware.