无需分支的快速无符号整数最大值

Question

我从AGGREGATE Magic找到了一个快速计算最大值的技巧。唯一的问题是，这仅适用于整数，并且尽管我尝试过一些方法，但不知道如何为无符号整数创建一个版本。

inline int32_t max(int32_t a, int32_t b)
{ 
    return a - ((a-b) & (a-b)>>31);
}

有什么建议吗？

编辑

不要使用这个，因为正如其他人所说，它会产生未定义的行为。对于任何现代架构，编译器都能够从 return (a > b) ? a : b 发出一个无分支条件移动指令，这将比所讨论的函数更快。

- plasmacel

---

等一下，你确定这比“return a > b ? a : b”更快吗？ - Frédéric Hamidi

这个函数基本上是无用的。请使用 std::max。 - Bartek Banachewicz

我的建议是不要假设编译器的作者自己不知道这样的技巧。 - interjay

在x86平台上，GCC使用无分支条件移动指令来实现此功能：见此。如果您采用这种方式，我会感到惊讶，如果速度比您的代码慢。 - interjay

当具有未定义行为的代码在不同情况下表现出不同行为时，这并不奇怪 - 这基本上是可以预料的。 - Casey

Answer 1

这段代码的作用是什么？它获取变量a及差值a - b，其中 a - (a - b) 的结果为b。而(a - b) >> 31则会在a - b 为负数时创建一个全1掩码。

但如果在减法操作中出现溢出，则此代码是不正确的。而这一问题同样存在于无符号整数中。因此，如果您可以接受代码无法处理整个值范围的事实，您可以忽略无符号性并使用以下代码：

inline uint32_t umax(uint32_t a, uint32_t b) {
    return (uint32_t)max((int32_t)a, (int32_t)b);
}

- cmaster - reinstate monica