How do you find the absolute value without branching?
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
x >> 31on a negative signed value is implementation-defined (arithmetic on GCC/Clang/Arm, but not guaranteed by the standard).abs(INT32_MIN)cannot be represented; the result isINT32_MINagain, and with the plain-xform 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.