我试图写一个无分支函数来返回两个整数的MAX或MIN,而不需要求助于if(或?:).使用the usual technique我可以很容易地做到这一点,对于给定的单词大小:
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。
当然,>>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 );
}
而且,做了上面的事情,我可以防止它被用于任何东西,但一个整数类型(例如,没有浮点数或类)?
6条答案
按热度按时间nr9pn0ug1#
**编辑:**这个答案来自C11之前。从那时起,C11和更高版本提供了
make_signed<T>
和更多作为标准库的一部分一般来说,看起来不错,但为了100%的可移植性,请将8替换为
CHAR_BIT
(或numeric_limits<char>::max()
),因为不能保证字符是8位的。任何好的编译器都足够聪明,可以在编译时合并所有的数学常量。
您可以使用类型特征库强制对它进行签名。它通常看起来像这样(假设你的numeric_traits库被称为numeric_traits):
一个手动滚动numeric_traits头的例子可能看起来像这样:http://rafb.net/p/Re7kq478.html(有足够的空间添加,但你得到的想法)。
或者更好的是,使用boost:
编辑:IIRC,有符号的右移位不一定是**算术。这是很常见的,我用过的每一个编译器都是如此。但我相信,在有符号类型上,右移是否是算术运算,标准留给编译器决定。在我的标准草案副本中,写有以下内容:
E1 >> E2的值是E1右移E2位位置。如果E1为无符号类型,或者E1为有符号类型且为非负值,则结果的值为E1除以2的E2次幂所得商的整数部分。如果E1具有带符号类型和负值,则结果值是实现定义的。
但正如我所说,它将在我见过的每一个编译器上工作:-p。
vlurs2pr2#
tl;dr
为了实现你的目标,你最好这样写:
长版本
我实现了
max()
的“naive”实现以及您的无分支实现。它们都没有模板化,我使用int 32只是为了保持简单,就我所知,Visual Studio 2017不仅使天真的实现无分支,而且还产生了更少的指令。下面是相关的Godbolt(请检查实现以确保我做对了)。请注意,我使用/O2优化进行编译。
无可否认,我的assembly-fu并不是那么好,所以虽然
NaiveMax()
少了5条指令,也没有明显的分支(老实说,内联我不确定发生了什么),但我想运行一个测试用例来明确地显示天真的实现是否更快。所以我做了一个测试。这是我运行的代码。Visual Studio 2017(15.8.7)带有“default”Release编译器选项。
这是我在机器上得到的输出:
我试了好几次,都得到了类似的结果。为了安全起见,我也改变了我进行测试的顺序,以防万一这是核心加速的结果,扭曲了结果。在所有情况下,我都得到了与上面类似的结果。
当然,根据您的编译器或平台,这些数字可能会有所不同。值得你自己测试一下。
答案
简而言之,编写无分支模板化
max()
函数的最佳方法似乎是 * 可能 * 保持简单:朴素方法还有其他优点:
1.它适用于unsigned类型。
1.它甚至适用于浮动类型。
1.它准确地表达了您的意图,而不需要注解您的代码来描述位旋转正在做什么。
1.这是一个众所周知的可识别模式,因此大多数编译器都知道如何优化它,使其更具可移植性。(这是我的直觉,只有编译器的个人经验才能让我感到惊讶。我愿意承认我错了。)
qkf9rpyu3#
这里有另一种无分支max和min的方法。它的优点是它不使用任何位技巧,你也不需要知道任何类型。
iklwldmw4#
您可能需要查看Boost.TypeTraits库。为了检测一个类型是否有签名,你可以使用is_signed trait。您还可以查看enable_if/disable_if以删除某些类型的重载。
e3bfsja25#
我不知道这个位掩码技巧工作的确切条件是什么,但你可以做一些事情,比如
其他有用的候选者是
std::is_[un]signed
、std::is_fundamental
等。https://en.cppreference.com/w/cpp/typesegdjgwm86#
除了tloch 14的回答“tl; dr”,也可以在数组中使用索引。这避免了“无分支最小/最大”的笨拙的位混洗;它也可以推广到所有类型。