有没有办法在没有分支的情况下将整数值限制在某个范围内？

Question

只是出于好奇.如果我有类似的东西:

if(x < 0)
    x = 0;
if(x > some_maximum)
    x = some_maximum;

return x;

有没有办法不分支？这是c ++.

附录:我的意思是装配中没有分支指令.这是一个MIPS架构.

Answer 1

有些技巧可以找到两个数字的最小值或最大值,因此您可以使用它们来查找min(max(x, 0), some_maximum).从这里:

y ^ ((x ^ y) & -(x < y)); // min(x, y)
x ^ ((x ^ y) & -(x < y)); // max(x, y)

正如消息来源所说的那样,尽管有分支,但以正常方式执行它可能会更快

Answer 2

这将取决于编译器和处理器,但如果您使用?:它,则可以转换为不使用分支的条件移动(至少在基于Intel的处理器上).

x = x < 0 ? 0 : x; x = x > max ? max : x;

这可以使用该CMOV指令(参见http://www.intel.com/software/products/documentation/vlin/mergedprojects/analyzer_ec/mergedprojects/reference_olh/mergedProjects/instructions/instruct32_hh/vc35.htm),其目的是避免分支(以及分支预测惩罚).

编辑:您可能会对此线程感兴趣.基准测试表明,条件移动只会在不可预测的分支上提供速度增益,而高度可预测的分支(例如长时间循环的分支)更喜欢标准方法.

Answer 3

在 C++17 中你可以使用std::clamp

定义在头文件中<algorithm>

template<class T>
constexpr const T& clamp( const T& v, const T& lo, const T& hi );   (1)   (since C++17)
template<class T, class Compare>
constexpr const T& clamp( const T& v, const T& lo, const T& hi, Compare comp );    (2)    (since C++17)

1. 如果 v 比较小于 lo，则返回 lo；否则，如果 hi 比较小于 v，则返回 hi；否则返回 v。使用运算符< 来比较值。
2. 与 (1) 相同，但使用 comp 来比较值。