时间戳

首页 > 解决方案 > 数学上找到最接近 0 的值

algorithm - 数学上找到最接近 0 的值

问题描述

有没有办法在数学上确定一个值是否比另一个值更接近 0？

例如closerToZero(-2, 3)会返回-2。

我尝试删除符号，然后比较最小值的值，但我会分配初始数字的无符号版本。

a 和 b 是符合 IEEE-754 的浮点双精度数（js 编号）

（64 位 => 1 位符号 11 位指数 52 位小数）

min (a,b) => b-((a-b)&((a-b)>>52));
result = min(abs(a), abs(b));
// result has the wrong sign ...

标签： algorithmmathmicro-optimizationbranch-predictionabsolute-value

解决方案

显而易见的算法是比较绝对值，并使用它来选择原始值。

如果这绝对需要无分支（例如为了加密安全），请小心使用? :三元。它通常编译为无分支汇编，但这并不能保证。（我认为这就是您标记的原因？如果只是出于性能考虑，编译器通常会做出正确的决定。）

在具有 2 的补码整数的固定语言中，请记住abs(INT_MIN)溢出与输入宽度相同的有符号结果。 在 C 和 C++ 中，abs()不方便地设计为返回 anint并且在 2 的补码系统上用最负的 2 的补码整数调用它是未定义的行为。在具有良好定义的包装有符号整数数学的系统上（如gcc -fwrapv，或者可能是 Java），有符号abs(INT_MIN)将溢出回 INT_MIN，如果您进行有符号比较，则会给出错误的结果，因为 INT_MIN 最大程度地远离 0。

确保对结果进行无符号比较，abs以便正确处理INT_MIN. （或者正如@kaya3 建议的那样，将正整数映射到负数，而不是从负数到正数。）

避免未定义行为的安全 C 实现：

unsigned absu(int x) {
    return x<0? 0U - x : x;
}

int minabs(int a, int b) {
    return absu(a) < absu(b) ? a : b;
}

请注意，<vs.<=实际上很重要minabs：如果它们的大小相等，则决定选择哪一个。

0U - x在从 0 中减去可能溢出的之前转换x为。将负有符号整数类型转换为无符号在 C 和 C++ 中被明确定义为模减少（与浮点数不同，UB IIRC）。在 2 的补码机器上，这意味着使用相同的位模式不变。unsigned

这对于 x86-64 ( Godbolt ) 编译得很好，尤其是对于 clang。（GCCcmov甚至避免使用-march=skylake，以更糟糕的序列结束。除了在执行两个 absu 操作之后的最终选择之外，它在 Intel CPU 上使用cmovbe2 uop 而不是 1 cmovb，因为它需要读取 ZF 和 CF 标志。如果它已经在 EAX 中以相反的值结束，它可以使用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

GCC 和 clang 完全无分支，启用优化。可以肯定的是，其他 ISA 将是相同的。

它可能会自动矢量化，但 x86 直到 AVX512 才进行 SIMD 无符号整数比较。（您可以通过翻转高位来模拟使用有符号整数pcmpgtd）。

对于 float / double，abs更便宜且不会溢出：只需清除符号位，然后使用它来选择原始位。

推荐阅读