有没有一种安全的方法可以获取带符号整数的无符号绝对值，而不会触发溢出？

Question

考虑一个典型的绝对值函数（其中为了讨论最大大小的整数类型是长整型）：

unsigned long abs(long input);

一个天真的实现可能看起来像：

unsigned long abs(long input)
{
    if (input >= 0)
    {
        // input is positive
        // We know this is safe, because the maximum positive signed
        // integer is always less than the maximum positive unsigned one
        return static_cast<unsigned long>(input);
    }
    else
    {
        return static_cast<unsigned long>(-input); // ut oh...
    }
}

由于对的否定可能会导致溢出，从而触发有未定义行为。例如，在二进制补码机器上，std :: numeric_limits<long> :: min()的绝对值将比std :: numeric_limits<long> :: max()大1个单位。

库的作者可以采取什么措施来解决这个问题？

- Billy ONeal

Answer 1

你可以先转换为无符号变量，以避免任何未定义的行为：

unsigned long uabs(long input)
{
    if (input >= 0)
    {
        // input is positive
        return static_cast<unsigned long>(input);
    }
    else
    {
        return -static_cast<unsigned long>(input); // read on...
    }
}

在上面的代码中，我们调用了两个定义良好的操作。将有符号整数转换为无符号整数是由N3485 4.7 [conv.integral] / 2定义的：

如果目标类型是无符号的，则结果值是与源整数同余的最小无符号整数（模2 ^ n，其中n是用于表示无符号类型的位数）。[注：在二进制补码表示中，此转换是概念性的，如果没有截断，则位模式不会改变。— 结束语]

这基本上表示，在进行特定的从有符号到无符号的转换时，可以假设使用无符号样式的环绕。

无符号整数的否定是由5.3.1 [expr.unary.op] / 8定义的：

无符号量的负值通过从2 ^ n（其中n是提升操作数中的位数）减去其值来计算。

这两个要求有效地强制实现像2s补码机器一样运行，即使底层机器是1s补码或有符号幅度机器。

---

C++11的广义版本，返回整数类型的无符号版本：

#include <type_traits>

template <typename T>
constexpr
typename std::make_unsigned<T>::type uabs(T x)
{
    typename std::make_unsigned<T>::type ux = x;
    return (x<0) ? -ux : ux;   // compare signed x, negate unsigned x
}

这段代码可以在Godbolt编译器浏览器上进行编译测试，结果显示在常量传播后，gcc -O3 -fsanitize=undefined在uabs(std::numeric_limits<long>::min());中没有发现UB, 但在std::abs()中却发现了。

进一步的模板操作可以让我们创建一个版本，该版本将返回整数类型的无符号版本，但对于浮点类型，将返回T，如果您想要一个通用替代std::abs。

- Billy ONeal

---

不错的回答，虽然是针对你自己的问题，但我点赞了。 - Bathsheba

你可以将其简洁地写成 return x<0 ? 0UL - x : x;。这使用了在 0UL - x 中隐式转换为无符号类型，而不是你的方式明确记录转换发生的时间。显式的方式可能有助于清晰度，尽管你可以使用 unsigned long ux = static_cast<unsigned long>(x); return x<0 : -ux : ux; 仍将其编写为三元运算符，提示编译器以无分支的方式执行。为了避免重复转换，特别是如果你想要模板化以推断输入类型的无符号版本，因此强制转换更长。 - Peter Cordes

一个像 uabs 或 absu 这样的名称比 abs 更好。我知道 abs 在 C++ 中与 std::abs 不同，但对于人类读者来说，这是一个返回无符号值的函数，对于每个输入都是良好定义的，不像不方便的 std::abs 和 C 的 stdlib.h 中的 abs。 （经常使用 C 和 C++ 的人会倾向于考虑到这一点。） - Peter Cordes

Answer 2

如果是负数，就加上一个。

unsigned long absolute_value(long x) {
  if (x >= 0) return (unsigned long)x;
  x = -(x+1);
  return (unsigned long)x + 1;
}

- ridiculous_fish

---

有趣的事实：编译器足够聪明，可以将其解开为任何目标机器的高效abs()习惯用法。例如，https://godbolt.org/z/34h3v8KrP显示RISC-V的GCC将其编译为无分支bithack，使用`-O2`。而x86的clang则使用`neg`/`cmov`。但我仍然不会以这种方式编写源代码；我更愿意使用无符号操作来避免UB，而不需要额外的操作，我希望编译器将其删除。此外，从可读性和易于验证正确性的角度来看，这需要一点努力，而几乎没有努力。 - Peter Cordes

观察我的答案为什么有效是很有趣的：在二进制补码中，取反意味着按位非，再加1。因此，(-(x+1) + 1) 简化为 (~x + 1)，简化为 -x。不需要编译器的技巧！但我完全同意你关于可读性的观点。 - ridiculous_fish