Is there a way to determine mathematically if a value is closer to 0 than another?
For example closerToZero(-2, 3)
would return -2
.
I tried by removing the sign and then compared the values for the minimum, but I would then be assigning the sign-less version of the initial numbers.
a and b are IEEE-754 compliant floating-point doubles (js number)
(64 bit => 1 bit sign 11 bit exponent 52 bit fraction)
min (a,b) => b-((a-b)&((a-b)>>52));
result = min(abs(a), abs(b));
// result has the wrong sign ...
The obvious algorithm is to compare the absolute values, and use that to select the original values.
If this absolutely needs to be branchless (e.g. for crypto security), be careful with ? :
ternary. It often compiles to branchless asm but that's not guaranteed. (I assume that's why you tagged branch-prediction? If it was just out of performance concerns, the compiler will generally make good decisions.)
In languages with fixed-with 2's complement integers, remember that abs(INT_MIN)
overflows a signed result of the same width as the input. In C and C++, abs()
is inconveniently designed to return an int
and it's undefined behaviour to call it with the most-negative 2's complement integer, on 2's complement systems. On systems with well-defined wrapping signed-int math (like gcc -fwrapv
, or maybe Java), signed abs(INT_MIN)
would overflow back to INT_MIN, giving wrong results if you do a signed compare because INT_MIN is maximally far from 0.
Make sure you do an unsigned compare of the abs
results so you correctly handle INT_MIN
. (Or as @kaya3 suggests, map positive integers to negative, instead of negative to positive.)
unsigned absu(int x) {
return x<0? 0U - x : x;
}
int minabs(int a, int b) {
return absu(a) < absu(b) ? a : b;
}
Note that <
vs. <=
actually matters in minabs
: that decides which one to select if their magnitudes are equal.
0U - x
converts x
to unsigned
before a subtract from 0 which can overflow. Converting negative signed-integer types to unsigned is well-defined in C and C++ as modulo reduction (unlike for floats, UB IIRC). On 2's complement machines that means using the same bit-pattern unchanged.
This compiles nicely for x86-64 (Godbolt), especially with clang. (GCC avoids cmov
even with -march=skylake
, ending up with a worse sequence. Except for the final select after doing both absu operations, then it uses cmovbe
which is 2 uops instead of 1 for cmovb
on Intel CPUs, because it needs to read both ZF and CF flags. If it ended up with the opposite value in EAX already, it could have used cmovb
.)
# clang -O3
absu:
mov eax, edi
neg eax # sets flags like sub-from-0
cmovl eax, edi # select on signed less-than condition
ret
minabs:
mov ecx, edi
neg ecx
cmovl ecx, edi # inlined absu(a)
mov eax, esi
mov edx, esi
neg edx
cmovl edx, esi # inlined absu(b)
cmp ecx, edx # compare absu results
cmovb eax, edi # select on unsigned Below condition.
ret
Fully branchless with both GCC and clang, with optimization enabled. It's a safe bet that other ISAs will be the same.
It might auto-vectorize decently, but x86 doesn't have SIMD unsigned integer compares until AVX512. (You can emulate by flipping the high bit to use signed integer pcmpgtd
).
For float / double, abs
is cheaper and can't overflow: just clear the sign bit, then use that to select the original.