12

我正在尝试编写一个无分支函数来返回两个整数的 MAX 或 MIN 而不诉诸 if（或？:)。使用通常的技术，对于给定的字长，我可以很容易地做到这一点：

inline int32 imax( int32 a, int32 b )
{
    // signed for arithmetic shift
    int32 mask = a - b;
    // mask < 0 means MSB is 1.
    return a + ( ( b - a ) & ( mask >> 31 ) );
}

现在，假设我真的在必要的有序处理器上编写这种应用程序，我的问题是是否有一种方法可以使用 C++ 模板将其推广到所有大小的 int。

当然，>>31步骤仅适用于 int32，虽然我可以复制 int8、int16 和 int64 函数的重载，但似乎我应该使用模板函数。但是如何以位为单位获取模板参数的大小？

还有比这更好的方法吗？我可以强制对掩码 T 进行签名吗？如果 T 是无符号的，则掩码移位步骤将不起作用（因为它将是逻辑移位而不是算术移位）。

template< typename T > 
inline T imax( T a, T b )
{
    // how can I force this T to be signed?
    T mask = a - b;
    // I hope the compiler turns the math below into an immediate constant!
    mask = mask >> ( (sizeof(T) * 8) - 1 );
    return a + ( ( b - a ) & mask );
}

而且，完成上述操作后，我可以防止它被用于除整数类型以外的任何东西（例如，没有浮点数或类）？

4

6 回答 6

9

编辑：这个答案来自 C++11 之前。从那时起，C++11 及更高版本提供make_signed<T>了更多作为标准库的一部分

一般来说，看起来不错，但为了 100% 的可移植性，请将 8 替换为CHAR_BIT(or numeric_limits<char>::max())，因为不能保证字符是 8 位的。

任何好的编译器都足够聪明，可以在编译时合并所有数学常量。

您可以使用类型特征库强制对其进行签名。这通常看起来像（假设您的 numeric_traits 库称为 numeric_traits）：

typename numeric_traits<T>::signed_type x;

手动滚动 numeric_traits 标头的示例如下所示：http ://rafb.net/p/Re7kq478.html （有很多添加空间，但你明白了）。

或者更好的是，使用 boost：

typename boost::make_signed<T>::type x;

编辑：IIRC，有符号的右移不必是算术的。这很常见，而且我使用过的每个编译器都是如此。但我相信标准将它留给编译器，无论右移是算术还是有符号类型。在我的标准草案副本中，写着以下内容：

E1 >> E2 的值是 E1 右移 E2 位位置。如果 E1 具有无符号类型或 E1 具有带符号类型和非负值，则结果的值是 E1 的商除以数量 2 的 E2 次方的整数部分。如果 E1 具有带符号类型和负值，则结果值是实现定义的。

但正如我所说，它适用于我见过的每个编译器：-p。

于 2009-02-05T03:47:58.807 回答
4

这是无分支最大值和最小值的另一种方法。它的好处是它不使用任何小技巧，而且您不必对类型有任何了解。

template <typename T> 
inline T imax (T a, T b)
{
    return (a > b) * a + (a <= b) * b;
}

template <typename T> 
inline T imin (T a, T b)
{
    return (a > b) * b + (a <= b) * a;
}
于 2012-11-29T02:12:36.437 回答
2

您可能想查看Boost.TypeTraits库。要检测类型是否已签名，您可以使用is_signed特征。您还可以查看enable_if/disable_if以删除某些类型的重载。

于 2009-02-05T03:52:24.523 回答
2

tl;博士

为了实现你的目标，你最好只写这个：

template<typename T> T max(T a, T b) { return (a > b) ? a : b; }

长版

我实现了“幼稚”的实现max()以及您的无分支实现。它们都没有模板化，我使用 int32 只是为了简单起见，据我所知，Visual Studio 2017 不仅使幼稚的实现无分支，而且产生的指令也更少。

这是相关的Godbolt（请检查实现以确保我做对了）。请注意，我正在使用 /O2 优化进行编译。

诚然，我的组装符并不是那么好，所以虽然NaiveMax()少了 5 条指令并且没有明显的分支（并且内联我真的不确定发生了什么），但我想运行一个测试用例来明确显示是否天真的实现是更快与否。

所以我建立了一个测试。这是我运行的代码。带有“默认”版本编译器选项的 Visual Studio 2017 (15.8.7)。

#include <iostream>
#include <chrono>

using int32 = long;
using uint32 = unsigned long;

constexpr int32 NaiveMax(int32 a, int32 b)
{
    return (a > b) ? a : b;
}

constexpr int32 FastMax(int32 a, int32 b)
{
    int32 mask = a - b;
    mask = mask >> ((sizeof(int32) * 8) - 1);
    return a + ((b - a) & mask);
}

int main()
{
    int32 resInts[1000] = {};

    int32 lotsOfInts[1'000];
    for (uint32 i = 0; i < 1000; i++)
    {
        lotsOfInts[i] = rand();
    }

    auto naiveTime = [&]() -> auto
    {
        auto start = std::chrono::high_resolution_clock::now();

        for (uint32 i = 1; i < 1'000'000; i++)
        {
            const auto index = i % 1000;
            const auto lastIndex = (i - 1) % 1000;
            resInts[lastIndex] = NaiveMax(lotsOfInts[lastIndex], lotsOfInts[index]);
        }

        auto finish = std::chrono::high_resolution_clock::now();
        return std::chrono::duration_cast<std::chrono::nanoseconds>(finish - start).count();
    }();

    auto fastTime = [&]() -> auto
    {
        auto start = std::chrono::high_resolution_clock::now();

        for (uint32 i = 1; i < 1'000'000; i++)
        {
            const auto index = i % 1000;
            const auto lastIndex = (i - 1) % 1000;
            resInts[lastIndex] = FastMax(lotsOfInts[lastIndex], lotsOfInts[index]);
        }

        auto finish = std::chrono::high_resolution_clock::now();
        return std::chrono::duration_cast<std::chrono::nanoseconds>(finish - start).count();
    }();

    std::cout << "Naive Time: " << naiveTime << std::endl;
    std::cout << "Fast Time:  " << fastTime << std::endl;

    getchar();

    return 0;
}

这是我在我的机器上得到的输出：

Naive Time: 2330174
Fast Time:  2492246

我已经运行了几次，得到了类似的结果。为了安全起见，我还更改了进行测试的顺序，以防万一它是核心速度加快的结果，从而扭曲了结果。在所有情况下，我都得到与上述类似的结果。

当然，根据您的编译器或平台，这些数字可能都不同。值得自己测试。

答案

max()简而言之，编写无分支模板函数的最佳方法似乎是保持简单：

template<typename T> T max(T a, T b) { return (a > b) ? a : b; }

天真的方法还有其他好处：

  1. 它适用于无符号类型。
  2. 它甚至适用于浮动类型。
  3. 它准确地表达了您的意图，而不是需要注释您的代码来描述位旋转正在做什么。
  4. 这是一种众所周知且可识别的模式，因此大多数编译器将确切地知道如何优化它，使其更具可移植性。（这是我的直觉，只有编译器的个人经验支持，这让我很惊讶。我愿意承认我在这里错了。）
于 2018-11-18T01:08:15.490 回答
0

我不知道这个位掩码技巧起作用的确切条件是什么，但你可以做类似的事情

#include<type_traits>

template<typename T, typename = std::enable_if_t<std::is_integral<T>{}> > 
inline T imax( T a, T b )
{
   ...
}

其他有用的候选人是std::is_[un]signed,std::is_fundamental等。https://en.cppreference.com/w/cpp/types

于 2019-05-15T05:49:33.030 回答
0

除了 tloch14 的回答“tl;dr”之外，还可以使用数组索引。这避免了“无分支最小/最大”的笨拙的比特洗牌；它也可以推广到所有类型。

template<typename T> constexpr T OtherFastMax(const T &a, const T &b)
{
    const T (&p)[2] = {a, b};
    return p[a>b];
}
于 2021-04-01T20:03:33.480 回答