模板化无分支int max/min函数 [英] Templatized branchless int max/min function

问题描述

我试图编写一个无分支函数以返回两个整数的MAX或MIN，而不求助于if(或?:).使用没有常用技术，我可以对于给定的单词大小，可以轻松地做到这一点:

I'm trying to write a branchless function to return the MAX or MIN of two integers without resorting to if (or ?:). Using the usual technique I can do this easily enough for a given word size:

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 ) );
}

现在，假设 arguendo 我确实是在用在需要此命令的顺序处理器中，我的问题是是否有一种方法可以使用C ++模板将其推广到所有大小的int.

Now, assuming arguendo that I really am writing the kind of application on the kind of in-order processor where this is necessary, my question is whether there is a way to use C++ templates to generalize this to all sizes of int.

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

The >>31 step only works for int32s, of course, and while I could copy out overloads on the function for int8, int16, and int64, it seems like I should use a template function instead. But how do I get the size of a template argument in bits?

有没有比这更好的方法了?我可以强制对面具T进行签名吗?如果T是无符号的，则掩码移位步骤将不起作用(因为这将是逻辑移位而不是算术移位).

Is there a better way to do it than this? Can I force the mask T to be signed? If T is unsigned the mask-shift step won't work (because it'll be a logical rather than arithmetic shift).

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 );
}

而且，完成上述操作后，是否可以防止将其用于除整数类型之外的任何内容(例如，没有浮点数或类)?

And, having done the above, can I prevent it from being used for anything but an integer type (eg, no floats or classes)?

推荐答案

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

This answer is from before C++11. Since then, C++11 and later has offered make_signed<T> and much more as part of the standard library

通常看起来不错，但是为了100％的可移植性，请使用CHAR_BIT(或numeric_limits<char>::max())替换8，因为不能保证字符为8位.

Generally, looks good, but for 100% portability, replace that 8 with CHAR_BIT (or numeric_limits<char>::max()) since it isn't guaranteed that characters are 8-bit.

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

Any good compiler will be smart enough to merge all of the math constants at compile time.

您可以使用类型特征库强制对其进行签名.通常看起来像(假设您的numeric_traits库称为numeric_traits):

You can force it to be signed by using a type traits library. which would usually look something like (assuming your numeric_traits library is called numeric_traits):

typename numeric_traits<T>::signed_type x;

手动滚动的numeric_traits标头的示例如下所示: http://rafb.net/p/Re7kq478.html (有足够的添加空间，但您知道了).

An example of a manually rolled numeric_traits header could look like this: http://rafb.net/p/Re7kq478.html (there is plenty of room for additions, but you get the idea).

或更妙的是，使用boost:

or better yet, use boost:

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

IIRC，有符号右移不必必须是算术运算.这是很常见的，当然我使用的每个编译器也是如此.但我相信，无论对有符号类型进行右移还是算术运算，该标准都将其留给了编译器.在我的标准草案副本中，写有以下内容:

IIRC, signed right shifts don't have to be arithmetic. It is common, and certainly the case with every compiler I've used. But I believe that the standard leaves it up the compiler whether right shifts are arithmetic or not on signed types. In my copy of the draft standard, the following is written:

E1 >> E2的值为E1 右移E2位位置.如果E1 具有无符号类型或如果E1具有 有符号类型和非负值， 结果的值是 E1商的整数部分 除以数量2 电源E2. 如果E1具有签名类型 和负值，结果 值是实现定义的.

The value of E1 >> E2 is E1 rightshifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 divided by the quantity 2 raised to the power E2. If E1 has a signed type and a negative value, the resulting value is implementation defined.

但是正如我所说，它将在我见过的每个编译器上都可以运行:-p.

But as I said, it will work on every compiler I've seen :-p.

这篇关于模板化无分支int max/min函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！